[Swift] 연결리스트 LinkedList, 양방향 연결리스트 DoublyLinkedList

연결 리스트란

연결 리스트는 각 요소가 노드로 되어 있는 연속된 데이터들이다.

• node 노드 : 연결 리스트의 하나의 요소를 말함
• head : 연결 리스트의 시작 노드를 참조하는 포인터
• tail : 연결 리스트의 끝 노드를 참조하는 포인터

유형

• 단방향 연결 리스트 singly linked list : 각 항목이 다음 노드에 대한 참조만 가짐
• 양방향 연결 리스트 doubly linked list : 각 항목이 앞, 뒤 노드에 대한 참조를 모두 가짐

단방향 연결 리스트 구현하기 (Swift)

https://www.raywenderlich.com/books/data-structures-algorithms-in-swift/v3.0/chapters/6-linked-list

프로토콜 채택하는 부분 이전까지 정리했습니다.

Node

단방향 연결 리스트는 노드로 구성되어 있으며, 각 노드는 value, next를 지닌다.

• value : 노드가 담는 값
• next : 다음 노드에 대한 포인터

public class LinkedListNode<T> {
    public var value: T
    public var next: LinkedListNode?

    public init(value: T, next: LinkedListNode? = nil) {
        self.value = value
        self.next = next
    }
}

LinkedList

public struct LinkedList<T> {

    public typealias Node = LinkedListNode<T>

    public var head: Node?
    public var tail: Node?

    public init() {}

    public var isEmpty: Bool {
        head == nil
    }

    // node(at:) : O(i), i=index. 특정 인덱스의 노드를 찾기
    public func node(at index: Int) -> Node? {
        var currentNode = head
        var currentIndex = 0

        while currentNode != nil && currentIndex < index {
            currentNode = currentNode!.next
            currentIndex += 1
        }
        // 목록이 비어있거나 인덱스를 넘어가면 nil 반환
        return currentNode
    }

    // MARK: Adding 삽입

    // push : O(1), 맨 처음에 삽입 head-first insertion
    public mutating func push(_ value: T) {
        head = Node(value: value, next: head)
        if tail == nil { // 빈 연결리스트에 넣은 경우 첫 요소가 head 이자 tail임
            tail = head
        }
    }

    // append: O(1), 맨 뒤에 삽입 tail-end insertion
    public mutating func append(_ value: T) {
        if isEmpty { // 비어 있는 배열에 넣을 때는 push == append
            push(value)
            return
        }

        tail!.next = Node(value: value)
        tail = tail!.next
    }

    @discardableResult // 리턴값을 사용하지 않더라도 컴파일러가 경고를 보내지 않게 함
    // insert(_:after:) : O(1), 해당 노드 뒤에 삽입.
    public mutating func insert(_ value: T, after node: Node) -> Node {
        guard tail !== node else { // 참조 비교
            // node가 tail인 경우 insert == append
            append(value)
            return tail!
        }

        node.next = Node(value: value, next: node.next)
        return node.next!
    }

    // MARK: Removing 삭제

    // pop : O(1). 맨 앞에서 제거.
    @discardableResult
    public mutating func pop() -> T? {
        defer { // 함수 종료 직전에 실행
            head = head?.next // head 제거 - 참조가 없으므로
            if isEmpty {
                tail = nil
            }
        }
        return head?.value
    }

    // removeLast() : O(n). 맨 뒤에서 제거.
    @discardableResult
    public mutating func removeLast() -> T? {
        guard let head = head else { // 비어있을 때
            return nil
        }

        guard head.next != nil else { // 노드가 1개뿐일때
            return pop()
        }

        // 노드가 2개이상일때 : 맨 끝 노드를 찾아야 함
        var prev = head
        var current = head
        while let next = current.next { // next가 nil이 아니면 반복
            prev = current
            current = next
        }
        // 여기에 도달하면 current가 마지막 노드가 된다.
        // 마지막 노드에 대한 참조를 없애 삭제한다
        prev.next = nil // 메모리에서 해제
        tail = prev
        return current.value
    }

    // remove(after:) : O(1). 특정 위치의 특정 노드를 삭제
    // 삭제 노드의 앞 노드와 뒷 노드를 이어붙여준다
    @discardableResult
    public mutating func remove(after node: Node) -> T? {
        // node == 삭제할 노드의 앞 노드
        defer {
            if node.next === tail { // tail 앞 노드 삭제 시
                tail = node
            }
            node.next = node.next?.next
        }
        return node.next?.value
    }
}

extension LinkedListNode: CustomStringConvertible {

    public var description: String {
        guard let next = next else {
            return "\(value)"
        }
        return "\(value) -> " + String(describing: next) + " "
    }
}

extension LinkedList: CustomStringConvertible {

  public var description: String {
    guard let head = head else {
      return "Empty list"
    }
    return String(describing: head)
  }
}

양방향 연결 리스트 구현하기 (Swift)

https://www.raywenderlich.com/947-swift-algorithm-club-swift-linked-list-data-structure

Node

양방향 연결 리스트는 노드로 구성되어 있으며, 각 노드는 value, next, previous를 지닌다.

• value : 노드가 담는 값
• next : 다음 노드에 대한 포인터
• previous : 이전 노드에 대한 포인터

public class DoublyLinkedListNode<T> {
    var value: T
    var next: DoublyLinkedListNode<T>? // 마지막 노드의 next는 nil이 되므로
    weak var previous: DoublyLinkedListNode<T>? // 순환참조 방지
    // weak 없으면 A-B일 때 A는 next로 B를, B도 previous로 A를 참조하게 되어 순환참조 발생

    init(value: T) {
        self.value = value
    }
}

DoublyLinkedList

연결 리스트의 시작과 끝을 추적하는 역할이다.

• append(value:) : 연결 리스트에 새 노드 추가
• nodeAt(index: Int) -> Node? : 연결 리스트의 해당 인덱스에 있는 노드를 가져옴
• removeAll() : 연결 리스트의 모든 노드 삭제
• remove(node: Node) -> String : 연결 리스트의 해당 노드 삭제
  • 첫 노드 삭제하는 경우 : head와 previous 포인터 수정 필요
  • 중간 노드 삭제하는 경우 : previous와 next 포인터 수정 필요
  • 마지막 노드 삭제하는 경우 : tail과 next 포인터 수정 필요
• extension LinkedList: CustomStringConvertible : 출력(print) 형태 지정

public class DoublyLinkedList<T> { // 양방향 연결 리스트

    public typealias Node = DoublyLinkedListNode<T>

    fileprivate var head: Node?
    private var tail: Node?

    public var isEmpty: Bool {
        return head == nil
    }

    public var first: Node? {
        return head
    }

    public var last: Node? {
        return tail
    }

    public func append(value: T) {
        // 1. value를 갖는 새 노드 생성
        let newNode = Node(value: value)
        // 2-1. tailNode가 nil이 아님 = 링크드리스트에 무언가 있음. 따라서 기존의 tail 뒤에 새 노드를 추가.
        if let tailNode = tail {
            newNode.previous = tailNode
            tailNode.next = newNode
        // 2-2. 링크드리스트에 아무것도 없음. 새 노드가 head가 됨
        } else {
            head = newNode
        }
        // 3. 두 경우 모두 newNode를 tail로 지정하게 됨
        tail = newNode
    }

    public func nodeAt(index: Int) -> Node? {
        // 특정 인덱스의 노드를 반환
        if index >= 0 { // index가 음수일 때 무한루프 방지
            var node = head
            var i = index
            while node != nil { // 해당 인덱스의 노드에 도달할 때 까지 반복
                if i == 0 {
                    return node
                }
                i -= 1
                node = node!.next
            }
        }
        return nil // index가 음수이거나 연결리스트의 항목보다 클 때
    }

    public func removeAll() {
        head = nil
        tail = nil
    }

    // MARK: 비정상 동작
    public func remove(node: Node) -> T {
        let prev = node.previous
        let next = node.next

        if let prev = prev { // prev가 있다면 첫 노드가 아닌 것이므로 prev의 next 수정
            prev.next = next
        } else { // prev가 없다면 head이므로 다음 노드를 head로 지정
            head = next
        }
        next?.previous = prev // next의 previous를 삭제되는 노드의 prev로 지정.
        if next == nil { // next가 없는 tail인 경우 tail을 수정
            tail = prev
        }


        node.previous = nil
        node.next = nil // 삭제하는 노드를 참조하는 previous와 next에 nil 할당 (메모리 해제)

        return node.value
    }
}

extension DoublyLinkedListNode: CustomStringConvertible {
    public var description: String {
        return "\(value)"
    }
}

extension DoublyLinkedList: CustomStringConvertible {
    public var description: String {
        var text = "["
        var node = head
        while node != nil {
            text += "\(node!.value)"
            node = node!.next
            if node != nil {
                text += ", "
            }
        }
        return text + "]"
    }
}