array의 단점

• 맨앞에 insert할때 시간이 오래걸린다
  맨앞에 insert하려면 모든 원소를 복사해야한다.

• array는 사용하지않는 저장 공간을 낭비하고 생성할때 마다 우리는 size를 명시해줘야한다.

linked list란

노드들이 순차적으로 연결된 데이터 원소의 linear collection, 다음 노드를 가르키는 포인터를 갖고있다.

head: 첫번째 노드
tail: 마지막 노드, nil을 가르킨다.

linked list advantage

• 첫번째 원소 insert / delete가 빠르다 O(1)
• 메모리를 낭비하지않고 한칸씩 늘려갈 수 있다.

linked list disadvantage

• random access 불가능하다.
• get / set 하는데 O(n)시간이 걸린다.

linked list 구현

class Node {
    var data: Int
    var next: Node?
    
    init(_ data: Int, _ next: Node? = nil) {
        self.data = data
        self.next = next
    }
}

class LinkList {
    private var head: Node?
        
    func addFront(_ data: Int) {    // O(1)
        let newNode = Node(data, head)
        head = newNode
    }

    func getFirst() -> Int? {
        return head?.data
    }

    func addBack(_ data: Int) {     // O(n)
        let newNode = Node(data)
        
        if head == nil {
            head = newNode
            return
        }
        
        var node = head!
        while node.next != nil {
            node = node.next!
        }
        node.next = newNode
    }

    func getLast() -> Int? {
        guard var node = head else { return nil }
        while node.next != nil {
            node = node.next!
        }
        return node.data
    }

    func insert(position: Int, data: Int) {
        if position == 0 {
            addFront(data)
            return
        }
        
        let newNode = Node(data)
        var currentNode = head
        
        for _ in 0..<position - 1 {
            currentNode = currentNode?.next
        }
        newNode.next = currentNode?.next
        currentNode?.next = newNode
    }
    
    func deleteFirst() {        // O(1)
        head = head?.next
    }

    func deleteLast() {
        var nextNode = head
        var previousNode: Node?
        while nextNode?.next != nil {
            previousNode = nextNode
            nextNode = nextNode?.next
        }
        
        previousNode?.next = nil
    }
    
    func delete(at position: Int) {
        if position == 0 {
            deleteFirst()
            return
        }
        
        var previousNode: Node?
        var currentNode = head
        for _ in 1...position {
            previousNode = currentNode
            currentNode = currentNode?.next
        }
        previousNode?.next = currentNode?.next
    }
    
    var isEmpty: Bool {
        return head == nil
    }
    
    func clear() {
        head = nil
    }
    
    func printLinkedList() {
        guard var node = head else { return }
        
        var result = [Int]()
        result.append(node.data)
        
        while node.next != nil {
            result.append(node.next!.data)
            node = node.next!
        }
        
        print(result)
    }
}