Linked List

What is a Linked List?

• A Linked List is linear colleciton of data elements sequentially linked together by a series of nodes.
• A series of nodes all linked together via their pointers.
  

Linked List 1

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

let node3 = Node(3)
let node2 = Node(2, node3)
let node1 = Node(1, node1)

Linked List2

class LinkList {
    private var head: Node?
        
    func addFront(_ data: Int) {
        let newNode = Node(data)
        newNode.next = head
        head = newNode
    }

    func getFirst() -> Int? {
        if head == nil {
            return nil
        }
        return head!.data

    }

    func addBack(_ data: Int) {
        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? {
        if head == nil {
            return nil
        }
        var node = head!
        
        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() {
        head = head?.next
    }

    func deleteLast() {
        if head?.next == nil {
            head = nil
            return
        }
        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 {
            self.deleteFirst()
            return
        }
        
        var nextNode = head
        var previousNode: Node?
        
        for _ in 0..<position {
            previousNode = nextNode
            nextNode = nextNode?.next
        }
        
        previousNode?.next = nextNode?.next
    }
    
    var isEmpty: Bool {
        return head == nil
    }
    
    func clear() {
        head = nil
    }
    
    func printLinkedList() {
        if head == nil { return }
        
        var result = [Int]()
        var node = head
        result.append(node!.data)
        
        while node?.next != nil {
            result.append(node!.next!.data)
            node = node?.next
        }
        
        print(result)
    }
}

Time Complexity

	addFront	addBack	Insert	Delete
시간복잡도	O(1)	O(n)	O(n)	O(n)

Linked List vs. Array

Advantage	Disadvantage
- Super fast Insert/Delete at front O(1)	No random Access
- Can gron incrementally	Get/set is linear O(n)

No indexes, No fixed capacity