[자료 구조 / Swift] 연결 리스트 구현하기

Linked List

• 데이터들이 순차적으로 연결되어 있는 구조
• 연속적인 메모리에 저장되어 있는 것이 아니다.
• 각 노드에 다음 노드의 주소값을 저장하여 연결된다.

단방향 연결 리스트 구현하기

• 노드 클래스

class NODE<T> {
    var data: T
    var next: NODE?
    
    init(data: T, next: NODE? = nil) {
        self.data = data
        self.next = next
    }
}

• 연결 리스트 클래스 (head 노드 O)

class LinkedList<T: Equatable> {
    private var head: NODE<T>?
    var count: Int
    
    init() {
        head = NODE<T>()
        count = 0
    }
    
    func push_front(data: T) {
        var newNode = NODE(data: data, next: head?.next)
        head?.next = newNode
        count += 1
    }
    func push_back(data: T) {
        var p = head
        while p?.next != nil { p = p?.next }
        p?.next = NODE(data: data)
        count += 1
    }
    func insert(data: T, at index:Int) {
        var p = head
        for _ in 0..<(index-1) { p = p?.next }
        
        var newNode = NODE(data: data, next: p?.next)
        p?.next = newNode
        count += 1
    }
    
    func removeFirst() -> T? {
        let first = head?.next
        head?.next = first?.next
        count -= 1
        return first?.data
    }
    func removeLast() -> T? {
        var p = head
        while p?.next?.next != nil { p = p?.next }
        let last = p?.next
        p?.next = nil
        count -= 1
        return last?.data
    }
    func remove(at index:Int) -> T? {
        var p = head
        for _ in 0..<(index-1) { p = p?.next }
        let tmp = p?.next
        p?.next = p?.next?.next
        count -= 1
        return tmp?.data
    }
    
    func searchNode(data: T) -> NODE<T>? {
        var p = head?.next
        while p != nil {
            if p?.data == data { return p }
            p = p?.next
        }
        
        return nil
    }
    
    func printNode() {
        var p = head?.next
        while p != nil {
            print((p?.data)! as T, terminator: " ")
            p = p?.next
        }
        print()
    }
}

---

양방향 연결 리스트 구현하기

• 노드 클래스

class NODE<T> {
    var data: T?
    var before: NODE?
    var next: NODE?
    
    init(data: T? = nil, before: NODE? = nil, next: NODE? = nil) {
        self.data = data
        self.before = before
        self.next = next
    }
}

• 연결 리스트 클래스 (head, tail 노드 O)

class LinkedList<T: Equatable> {
    private var head: NODE<T>?
    private var tail: NODE<T>?
    var count: Int
    
    init() {
        head = NODE<T>()
        tail = NODE<T>()
        head?.next = tail
        tail?.before = head
        count = 0
    }
    
    func push_front(data: T) {
        var newNode = NODE(data: data, before: head, next: head?.next)
        head?.next?.before = newNode
        head?.next = newNode
        count += 1
    }
    func push_back(data: T) {
        var newNode = NODE(data: data, before: tail?.before, next: tail)
        tail?.before?.next = newNode
        tail?.before = newNode
        count += 1
    }
    func insert(data: T, at index:Int) {
        var p = head
        for _ in 0..<(index-1) { p = p?.next }
        
        var newNode = NODE(data: data, before: p, next: p?.next)
        p?.next?.before = newNode
        p?.next = newNode
        count += 1
    }
    
    func removeFirst() -> T? {
        let first = head?.next
        head?.next = first?.next
        head?.next?.before = head
        count -= 1
        return first?.data
    }
    func removeLast() -> T? {
        let last = tail?.before
        tail?.before = last?.before
        tail?.before?.next = tail
        count -= 1
        return last?.data
    }
    func remove(at index:Int) -> T? {
        var p = head
        for _ in 0..<(index-1) { p = p?.next }
        let tmp = p?.next
        p?.next = p?.next?.next
        p?.next?.before = p
        count -= 1
        return tmp?.data
    }
    
    func searchNode(data: T) -> NODE<T>? {
        var p = head?.next
        while p != nil {
            if p?.data == data { return p }
            p = p?.next
        }
        
        return nil
    }
    
    func printNode() {
        var p = head?.next
        while p?.next != nil {
            print((p?.data)! as T, terminator: " ")
            p = p?.next
        }
        print()
    }
}

---

실행 화면