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

import Foundation

class LinkedList<T> {
    
    public class LinkedListNode<T> {
        var value: T
        var next: LinkedListNode?
				// 상호참조를 막기 위해 weak 사용.
        weak var previous: LinkedListNode?
        
        public init(value: T) {
            self.value = value
        }
    }
    
    typealias Node = LinkedListNode<T>
    private var head: Node?
    
    public var isEmpty: Bool {
        return head == nil
    }
    
    public var first: Node? {
        return head
    }
    
    public var last: Node? {
        guard var node = head else {
            return nil
        }
        
        while let next = node.next {
            node = next
        }
        return node
    }
    
    public func append(value: T) {
        let newNode = Node.init(value: value)
        
        if let lastNode = last {
            newNode.previous = lastNode
            lastNode.next = newNode
        } else {
            head = newNode
        }
    }
    
    public var count: Int {
        guard var node = head else {
            return 0
        }
        
        var count = 0
        while let next = node.next {
            node = next
            count += 1
        }
        return count
    }
    
    public func node(at index: Int) -> Node {
        if index == 0 {
            return head!
        } else {
            var node = head!.next
            for _ in 1..<index {
                node = node?.next
                if node == nil {
                    break
                }
            }
            
            return node!
        }
    }
    
    public func insert(_ node: Node, at index: Int) {
        let newNode = node
        if index == 0 {
            newNode.next = head
            head?.previous = newNode
            head = newNode
        } else {
            let prev = self.node(at: index-1)
            let next = prev.next
            
            newNode.previous = prev
            newNode.next = next
            prev.next = newNode
            next?.previous = newNode
        }
    }
    
    public func removeAll() {
        head = nil
    }
    
    public func remove(node: Node) -> T {
        let prev = node.previous
        let next = node.next
        
        if let prev = prev {
            prev.next = next
        } else {
            head = next
        }
        next?.previous = prev
        
        node.previous = nil
        node.next = nil
        return node.value
    }
    
    public func removeLast() -> T {
        return remove(node: last!)
    }
    
    public func remove(at index: Int) -> T {
        let n = node(at: index)
        return remove(node: n)
    }
}