Linked Lists

단일 연결 리스트

기존 배열은 원소가 고정된 거리에 따라 배치되어 있기 때문에 임의의 원소를 삽입하거나 삭제하는 작업 비용 존재

• 원소가 메모리 내 어디에서나 위치 가능
• 원소 접근 → 리스트 내 다음 원소의 위치 또는 주솟값을 가지고 있음

import Foundation

public class Node<T> {
    var data: T
    var next: Node?
    
    init(data: T, next: Node? = nil) {
        self.data = data
        self.next = next
    }
}

public struct LinkedList<T> {
    var head:  Node<T>?
    var tail: Node<T>?
    
    var isEmpty: Bool {
        return head == nil
    }
    
    mutating func push(_ data: T) {
        head = Node(data: data, next: head)
        if tail == nil {
            tail = head
        }
        // 스택의 push
    }
    
    mutating func append(_ data: T) {
        guard !isEmpty else {
            push(data)
            // 모두 비었다면 push === append
            return
        }
        tail!.next = Node(data: data)
        tail = tail!.next
        // 큐의 enqueue
    }
    
    func node(at index: Int) -> Node<T>? {
        var curNode = head
        var curIndex = 0
        while curNode != nil && curIndex < index {
            curNode = curNode!.next
            curIndex += 1
        }
        return curNode
    }
    
    func printList() {
        guard !isEmpty else { return }
        var curNode = head
        while curNode != nil {
            print(curNode!.data, terminator: " ")
            curNode = curNode!.next
        }
    }
    
    @discardableResult
    mutating func insert(_ data: T, after node: Node<T>) -> Node<T> {
        guard tail !== node else {
            append(data)
            return tail!
        }
        node.next = Node(data: data, next: node.next)
        return node.next!
    }
    
    @discardableResult
    mutating func pop() -> T? {
        defer {
            head = head?.next
            if isEmpty {
                tail = nil
            }
        }
        return head?.data
    }
    
    @discardableResult
    mutating func removeLast() -> T? {
        guard let head = head else {
            return nil
        }
        
        guard head.next != nil else {
            return pop()
        }
        
        var prev = head
        var cur = head
        
        while let next = cur.next {
            prev = cur
            cur = next
        }
        
        prev.next = nil
        tail = prev
        return cur.data
    }
    
    @discardableResult
    mutating func remove(after node: Node<T>) -> T? {
        defer {
            if node.next === tail {
                tail = node
            }
            node.next = node.next?.next
        }
        return node.next?.data
    }
}

var linkedList = LinkedList<Int>()
linkedList.append(1)
linkedList.append(2)
linkedList.printList()
// 1 2
linkedList.push(3)
linkedList.push(4)
linkedList.printList()
// 4 3 1 2
linkedList.pop()
linkedList.pop()
linkedList.printList()
// 1 2
linkedList.removeLast()
linkedList.printList()
// 1
linkedList.push(0)
linkedList.push(1)
linkedList.push(2)
linkedList.push(3)
linkedList.push(4)
linkedList.printList()
// 4 3 2 1 0 1
if let node = linkedList.node(at: 2) {
    // Node: data 2, index 2
    linkedList.remove(after: node)
    linkedList.printList()
    // 4 3 2 0 1
}

연결 리스트를 통한 스택과 큐

• 위 연결 리스트의 push, append, removeLast, pop 등을 사용할 때 연결 리스트를 통한 스택과 큐를 구현할 수 있다.

다항식

• 다항식을 표현하는 자료구조로 연결 리스트를 응용할 수 있다.

public class PolynomialNode {
    var coef: Int
    var expon: Int
    var next: PolynomialNode?
    
    init(coef: Int, expon: Int, next: PolynomialNode? = nil) {
        self.coef = coef
        self.expon = expon
    }
}

• 노드 클래스의 프로퍼티가 각각 다항식의 지수, 계수 등을 표현할 수 있다면 연결 리스트를 통해 사용할 수 있다.
• 연결 리스트 하나를 통해 다항식 하나를 표현할 수 있다면, 이 연결 리스트를 head에서 비교하면서 다항식의 수식(덧셈, 뺄셈 등)을 계산할 수 있다.

이중 연결 리스트

• 단일 연결 리스트가 "다음" 차례의 노드를 담고 있었다면, 이중 연결 리스트는 이전 차례의 노드 역시 가지고 있기 때문에 순회가 보다 편리하다.

import Foundation

public class Node<T> {
    var prev: Node?
    var data: T
    var next: Node?
    
    init(data: T, prev: Node? = nil, next: Node? = nil) {
        self.data = data
        self.prev = prev
        self.next = next
    }
}

public struct LinkedList<T> {
    var head: Node<T>?
    var tail: Node<T>?
    
    var isEmpty: Bool {
        return head == nil
    }
    
    mutating func push(_ data: T) {
        head = Node(data: data, prev: nil, next: head)
        if tail == nil {
            tail = head
        }
    }
    
    mutating func append(_ data: T) {
        guard !isEmpty else {
            push(data)
            return
        }
        tail?.next = Node(data: data, prev: tail, next: nil)
        tail = tail?.next
    }
    
    func printList() {
        guard !isEmpty else { return }
        var curNode = head
        while curNode != nil {
            print(curNode!.data)
            curNode = curNode!.next
        }
    }
    
    mutating func pop() -> T? {
        defer {
            head = head?.next
            if isEmpty {
                tail = nil
            }
        }
        return head?.data
    }
    
    mutating func removeLast() -> T? {
        guard let removed = tail else { return nil }
        if head?.next == nil {
            head = nil
            tail = nil
        }
        
        tail?.prev?.next = tail?.next
        tail = tail?.prev
        
        return removed.data
    }
}

var linkedList = LinkedList<Int>()
linkedList.push(1)
linkedList.push(2)
linkedList.push(3)
linkedList.printList()
// 3 2 1
linkedList.append(4)
linkedList.append(5)
linkedList.append(6)
linkedList.printList()
// 3 2 1 4 5 6
linkedList.pop()
linkedList.pop()
linkedList.printList()
// 1 4 5 6
linkedList.removeLast()
linkedList.removeLast()
linkedList.printList()
// 1 4

• tail, head 포인터의 이전/이후 포인터를 상황에 따라 연결/해제하는 게 이중 연결 리스트를 구현하는 데 있어서 핵심이다.