Linked List

- 선형 자료구조
- 순차적 접근방식 ( O(n) )
- 삽입, 삭제가 빠르다 ( O(1) )
- 다음 노드를 가리키는 주소를 저장할 공간 필요

 

Linked List는 순차적으로 모인 데이터들의 모음이다.
흔히 각각의 데이터를 Node(노드), 각 노드는 다음 차례의 노드의 reference(주소)를 갖고 있다.

대표적으로 두 가지 유형이 있는데,

Singly Linked List: 내 다음 노드(next node)의 주소만을 갖고 있다.

Double Linked List: 내 이전(previous)과 다음의 주소를 갖고 있다.

Linked List를 사용하기 위해서는 시작과 끝의 주소를 알아야 하는데 이를 head와 tail이라 부른다.

 

Performance

Linked List의 대부분의 연산은 O(n)의 시간복잡도를 갖는다. 대부분 배열보다 느리다. 해당 크기만큼 메모리를 미리 잡아야 하는 배열에 비해 리스트는 포인터만 옮겨주면 되기 때문에 훨씬 유연하다.

Linked List의 대부분의 연산이 O(n)인 이유는 특정 노드에 직접 접근할 수 없기 때문인데, 그 노드의 주소를 알고 있지 않다면 head 또는 tail에서 부터 찾아나가야 한다.

하지만 일단 노드를 찾았다면 추가 삭제는 매우 빠르다.(O(1))

Linked List Implementation in Swift 5

 

구현 내용

• head // O(1)
• tail // O(1)
• first // O(1)
• last // O(1)
• isEmpty // O(1)
• node(at index:) // O(n)
• append(_:) // O(1)
• insert(_:at:) // O(1)
• removeAll() // O(1)
• remove(node:) // O(1)
• remove(at:) // O(n)
• description

class LinkedList<T> {
    class Node<T> {
        var value: T
        var next: Node?
        weak var previous: Node?
        
        init(_ value: T) {
            self.value = value
        }
    }
    
    private(set) var head: Node<T>?
    private(set) var tail: Node<T>?
    private(set) var count = 0
    
    var first: T? {
        return head?.value
    }
    
    var last: T? {
        return tail?.value
    }
    
    var isEmpty: Bool {
        return head == nil
    }
    
    func node(at index: Int) -> Node<T>? {
        guard 0..<count ~= index else { return nil }
        
        var node = head!
        var current = 0
        while index > current, let next = node.next {
            node = next
            current += 1
        }
        return node
    }
    
    func append(value: T) {
        let newNode = Node(value)
        guard !isEmpty else {
            head = newNode
            tail = newNode
            count += 1
            return
        }
        if count == 1 {
            head?.next = tail
        }
        
        tail?.next = newNode
        newNode.previous = tail
        tail = newNode
        count += 1
    }
    
    func insert(_ value: T, at index: Int) {
        let node = Node(value)
        if index == 0 {
            node.next = head
            head?.previous = node
            head = node
            count += 1
        } else if index == count {
            append(value: value)
        } else {
            assert(0..<count ~= index, "Out of Index: \(index), range: \(0)..<\(count)")
            let next = self.node(at: index)
            let before = next?.previous
            node.previous = before
            node.next = next
            before?.next = node
            next?.previous = node
            count += 1
        }
    }
    
    func removeAll() {
        head = nil
        tail = nil
        count = 0
    }
    
    @discardableResult
    func remove(node: Node<T>) -> T {
        if node === head, node === tail {
            head = nil
            tail = nil
            return node.value
        } else if node === head {
            defer {
                head = node.next
                head?.previous = nil
            }
            return node.value
        } else if node === tail {
            defer {
                tail?.previous = tail
                tail?.next = nil
            }
            return node.value
        } else {
            let before = node.previous
            let next = node.next
            before?.next = next
            next?.previous = before
            node.next = nil
            node.previous = nil
            count -= 1
            return node.value
        }
    }

    @discardableResult
    func remove(at index: Int) -> T? {
        assert(0..<count ~= index, "Out of Index: \(index), range: \(0)..<\(count)")
        guard let node = node(at: index) else { return nil }
        return remove(node: node)
    }
}

extension LinkedList.Node: CustomStringConvertible {
    var description: String {
        guard let next = next else {
            return "\(value)"
        }
        return "\(value) -> " + "\(next)" + " "
    }
}

extension LinkedList: CustomStringConvertible {
    var description: String {
        guard let head = head else {
            return "List is Empty"
        }
        return "\(head)"
    }
}