[Swift] (자료구조) 링크드 리스트 / Linked List

Node

import Foundation
 
class Node<T: Equatable> {
    let id: Int
    let data: T
    var next: Node?
    
    init(id: Int, data: T, next: Node? = nil) {
        self.id = id
        self.data = data
        self.next = next
    }
}

---

LinkedList

struct LinkedList<T: Equatable> {
    var head: Node<T>?
    var tail: Node<T>?
   
    func showList() {
        var now = head
        print("===== Linked List ======")
        while now != nil {
            now?.next == nil
            ? print("id: \(now?.id) | data: \(now?.data)")
            : print("id: \(now?.id) | data: \(now?.data) -> ")
            now = now?.next
        }
        print("========================")
    }
}

---

func add : O(1)

mutating func add(node: Node<T>) {
    // head node does not exist
    if head == nil {
        head = node
        tail = node
        return
    }
 
    // search for last node and attatch new
    tail?.next = node
    tail = node
}

---

func searchNode : O(N)

func searchNode(with data: T) -> Node<T>? {
    var now = head
    while now?.data != data && now != nil {
        now = now?.next
    }
    return now
}

---

func insert
목표 노드까지 탐색이 선행된 경우 : O(N)
Head, Tail의 앞뒤에 꽂히는 경우 : O(1)

mutating func insert(node: Node<T>, after id: Int) {
    var now = head
    while now?.id != id && now?.next != nil {
        now = now?.next
    }
 
    node.next = now?.next
    now?.next = node
}
 
mutating func insert(node: Node<T>, before id: Int) {
    var now = head
 
    if now?.id == id {
        head = node
        node.next = now
        return
    }
 
    while now?.next?.id != id && now?.next != nil {
        now = now?.next
    }
 
    node.next = now?.next
    now?.next = node
}

---

func delete
목표 노드까지 탐색이 선행 : O(N)
Head, Tail : O(1)

mutating func delete(node: Node<T>) -> Bool {
    var now = self.head
 
    // if target node is at head
    if now === node {
        if self.head === self.tail { self.tail = nil }
        self.head = now?.next
        return true
    }
 
    while now?.next !== node && now?.next != nil {
        now = now?.next
    }
 
    // no matching node to delete
    if now == nil { return false }
 
    if now?.next === tail {
        tail = now
    }
 
    // delete node
    now?.next = now?.next?.next
    return true
}