[Swift 자료구조] 3. Linked List 연결 리스트 (Singly Linked List)

Data Structure in Swift (Linked List) - Part 2

기본적으로 위 문서를 번역해 정리한 문서이며,

Data Structures & Algorithms in Swift, Chapter 6: Linked List

이 문서를 함께 참조했습니다.

Linked List 연결 리스트

• 노드를 기본 단위로 하는 선형 데이터 구조.
• 노드 : 데이터 + 포인터
  • 데이터 : 해당 노드에 저장된 값
  • 포인터 : 다음 노드의 위치에 대한 참조값
• 메모리상에 연속적으로 저장되지 않는다.
  • 배열처럼, 서브스크립트로 요소에 임의접근할 수 없다. (list[0] - 불가능)
• 연결 리스트는 여러 종류가 있다
  • Singly Linked List 단방향 연결 리스트 (단일 연결 리스트)
    • 각 항목이 다음 노드에 대한 참조만 가짐
  • Doubly Linked List 양방향 연결 리스트
    • 각 항목이 앞, 뒤 노드에 대한 참조를 모두 가짐
  • Circular Linked List 원형 연결 리스트

⭕️ 이럴 때 연결 리스트를 사용한다

• 데이터의 크기를 미리 알 수 없는 경우

❌ 이럴 때 연결 리스트를 사용하지 않는다

• 많은 양의 데이터에 탐색 연산을 해야 하는 경우
• 데이터 순회를 자주 해야 하는 경우

Singly Linked List 구현

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

• node 노드 : 연결 리스트의 하나의 요소를 말함. value 와 next로 구성
  • value : 노드가 담는 데이터 값
  • next : 다음 노드에 대한 포인터
• head : 연결 리스트의 시작 노드를 참조하는 포인터
• tail : 연결 리스트의 끝 노드를 참조하는 포인터

❗️ Swift는 기본 자료구조로 연결리스트를 지원하지 않으므로, 직접 구현해야 한다.

주석이 없는 전체 구현 코드는 여기에 있습니다.

Node

단일 연결 리스트는 노드로 구성되어 있다.

Node 클래스에서는 의 데이터를 담는 노드를 만든다.

각 노드는 자신의 데이터 값과 포인터를 가지고 있다.

// 요소에 대한 데이터를 담는 클래스
class Node<T>: CustomStringConvertible, Equatable {

    var value: T
    var next: Node?

    // required conforms to CustomStringConvertible
    var description: String {
        guard let next = next else { return "\(value)" }
        return "\(value) -> " + String(describing: next)
    }

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

    // required conforms to Equatable
    static func ==(lhs: Node, rhs: Node) -> Bool {
        return lhs.next == rhs.next
    }
}

• 어떤 종류의 데이터든 담을 수 있게 제네릭 사용
• 두 노드를 비교하기 위해 == 연산자를 오버로드함

LinkedList

모든 노드를 담는 구조체인 LinkedList를 만든다.

// A struct to hold the information of all the nodes
struct LinkedList<T>: CustomStringConvertible {

    // to hold the starting point of list
    var head: Node<T>?

    // to hold the ending point of list
    var tail: Node<T>?

    init() { }

    // if head is nil simply list is empty right now
    var isEmpty: Bool {
        return head == nil
    }

    // required conforms to CustomStringConvertible
    var description: String {
        guard let head = head else { return "Empty list" }
        return String(describing: head)
    }
}

• head : 시작 노드를 참조함
• tail : 끝 노드를 참조함

❓ LinkedList에서 head와 tail을 왜 사용하는가?

→ 모든 노드들은 참조에 의해 연결되어 있다. 따라서 리스트를 순회하거나 연산을 수행하기 위해 시작점과 끝점을 붙잡고 있어야 한다.

🔍 Search 탐색

node(at:) : 리스트의 특정 위치의 노드 찾기. O(i)

O(i) 의 i 는 인덱스를 의미한다.

// node(at:) : O(i), i=index. 특정 인덱스의 노드를 찾기
func node(at index: Int) -> Node<T>? {
    // if list is empty then simply return nil
    if isEmpty {
        return nil
    }

    var currentNode = head
    var currentIndex = 0
    while currentNode != nil && currentIndex < index {
        currentNode = currentNode?.next
        currentIndex += 1
    }
    return currentNode
}

• 만약 리스트가 비어 있다면, 찾는 노드가 당연히 없으므로 nil 반환
• head의 인덱스를 0으로 하고, head부터 연결된 노드를 차례로 탐색

count() : 리스트의 노드의 수 반환. O(n)

// get number of nodes in the list
func count() -> Int {
    var currentNode = head
    var count = 0
    while currentNode != nil {
        currentNode = currentNode?.next
        count += 1
    }
    return count
}

• head부터 시작해 count를 하나씩 세며 tail에 도달할 때까지 반복.

➕ Insertion 삽입

push(_:) : 리스트의 맨 앞에 노드 삽입. O(1)

// push(_:) : O(1), 맨 앞에 삽입 head-first insertion
mutating func push(_ value: T) {

    // create a new node and passing head (starting point) as a next node
    let newNode = Node(value: value, next: head)

    // change the head to the new node because head will hold the starting node
    head = newNode

    // if tail (ending node) is nil, it means head and tail pointing the same node as it is first node
    if tail == nil {
        tail = head
    }
}

• 새 노드를 만들어 값을 넣고, 포인터는 기존 head로 설정한다.
• 새 노드를 리스트의 head로 만든다.
• 만약 tail이 nil이면 현재 넣는 값이 첫 노드임을 의미한다.
  • 원소가 1개뿐인 링크드리스트에서, 리스트의 첫 요소는 head 이자 tail 이므로 tail에 head를 할당한다.

append(_:) : 리스트의 맨 뒤에 노드 삽입. O(1)

// append(_:) : O(1), 맨 뒤에 삽입 tail-end insertion
mutating func append(_ value: T) {

    // if list is empty then simply perform push operation
    if isEmpty {
        self.push(value)
        return
    }

    // create new node and assign it to tail's next because tail will always point the last node
    tail?.next = Node(value: value)

    // replace the tail with tail's next because before doing it tail's next pointing the last node
    tail = tail?.next
}

• 리스트가 비어있다면 append() == push() 이므로 push()로 처리한다.
• 지금 맨 뒤에 삽입하려는 노드가 마지막 노드가 되어야 하므로, tail의 next에 새로운 값으로 노드를 만들어 붙인다.
• 새로 설정한 tail의 next가 새로운 tail이 된다.

insert(_:after:) : 리스트의 특정 인덱스에 노드 삽입. O(n)

특정 위치를 찾아서(탐색) 노드를 삽입해야 하므로 시간이 더 걸린다.

O(n) 의 n은 삽입 인덱스에 해당한다.

// insert(_:after:) : O(n), 주어진 인덱스 뒤에 삽입
mutating func insert(_ value: T, after index: Int) {

    // if given index is not valid as per current list, it will be added in last
    if index < 0 || index >= self.count() {
        self.append(value)
        return
    }

    // if node not found just before to given insert index, perform push operation
    if let beforeNode = self.node(at: index), let tail = tail {

        // if insert index ie equal to last, simply append new node at last
        if beforeNode == tail {
            self.append(value)
        } else {
            // create new node and assign as a next node for the before node
            beforeNode.next = Node(value: value, next: beforeNode.next)
        }
    } else {
        self.push(value)
    }
}

• (이 구현에서는) 주어진 인덱스가 현재 리스트에 유효하지 않으면 그냥 append로 처리한다.
• node(at:) 를 활용해 삽입하려는 위치의 노드를 찾는다
  • 만약 삽입하려는 위치의 노드가 tail이라면, 그냥 맨 끝에 삽입하는 것과 같으므로 append로 처리한다.
  • 그렇지 않으면 기존 노드의 next로 새 노드를 만들어 삽입하고, 새 노드의 next는 기존 노드의 next로 설정해 이어붙여 준다.

➖ Remove 삭제

pop() : 리스트의 맨 앞의 노드 삭제. O(1)

// pop() : O(1). 맨 앞에서 제거.

@discardableResult
mutating func pop() -> T? {

    defer { // 함수 종료 직전에 실행
        head = head?.next
        if isEmpty {
            tail = nil
        }
    }
    return head?.value
}

• @discardableResult: pop() 이후 리턴값을 사용하지 않아도 컴파일러가 경고를 표시하지 않도록 함.
• defer { … }: 함수가 종료되기 직전에 실행되는 코드블럭.
  • 왜 썼는가? defer 내부 코드가 먼저 실행되고 return하면 head의 값이 달라져 있기 때문
  • pop된 값이 먼저 반환되고, 그 다음 defer 블록이 실행된다.
  • 즉, 기존 head값을 반환한 다음에 기존 head값을 삭제하기 위해 defer를 사용한 것임.
• pop은 맨 앞 노드를 삭제하는 것 = head를 삭제하는 것
  • head를 head의 다음 노드로 바꿔준다 (삭제)
  • 삭제 후에 만약 리스트가 비어있다면 (head가 nil이라면) 빈 리스트가 된 것이므로, tail에도 nil을 할당해 준다

removeLast() : 리스트의 맨 뒤의 노드 삭제. O(n)

//removeLast() : O(n). 맨 뒤에서 제거.
@discardableResult
mutating func removeLast() -> T? {

    // if head is nil, means no node exists.
    guard let head = head else { return nil } // <- isEmpty로 대체 가능

    // if head is not have any reference of next node, it means we have only one node in list.
    guard head.next != nil else { return pop() }

    // first we have to traverse to reach at last two nodes.
    var currentNode = head
    var previousNode = head

    while let next = currentNode.next {
        previousNode = currentNode
        currentNode = next
    }
    // 여기에 도달하면 currentNode가 마지막 노드가 된다. 마지막 노드에 대한 참조를 없애 삭제한다.
    // disconnected the next of last previous node
    previousNode.next = nil
    tail = previousNode
    return currentNode.value
}

• head가 nil이면 리스트가 비어있다는 뜻이므로, 삭제할 게 없으니 nil반환
• head가 있지만 head.next가 없다면 요소가 1개뿐이므로 pop으로 처리
• currentNode와 previousNode를 저장하며 리스트의 맨 끝으로 이동
• 맨 끝 노드의 previousNode.next를 nil로 만들고, previousNode를 tail로 지정
• 삭제한 맨 끝 노드의 값을 반환

remove(after:) : 리스트의 특정 인덱스의 노드 삭제. O(n)

O(n) 의 n은 삭제 인덱스에 해당한다.

삭제 노드의 앞 노드와 뒷 노드를 이어붙여준다.

특정 위치를 찾아서(탐색) 노드를 삭제해야 하므로 시간이 더 걸린다.

// remove(after:) : O(n). 특정 인덱스 뒤의 노드를 삭제
mutating func remove(after index: Int) -> T? {

    if index < 0 || index >= self.count() {
        return nil
    }

    if let beforeNode = self.node(at: index) {
        defer {
            if beforeNode.next == tail {
                tail = beforeNode
            }
            beforeNode.next = beforeNode.next?.next
        }
        return beforeNode.next?.value
    }
    return nil
}

• insert(after:)와 비슷하게, 인덱스가 유효한지 먼저 검사한다
  • 유효하지 않으면 nil 반환
• 주어진 인덱스에 위치한 노드를 찾는다
  • 없으면 nil반환
• defer블록은 함수 종료 직전에 호출되므로, return beforeNode.next?.value 가 실행되게 된다.
  • 노드가 삭제되기 전에 그 값을 반환하기 위함
• 만약 찾은 노드가 tail 직전의 노드라면, 노드 삭제 전에 tail을 업데이트해주어야 한다.
  • tail을 tail직전 노드로 바꿔 준다
• 찾은 노드의 next는, 찾은 노드의 다다음 노드와 연결해 준다
  • 참조가 사라진 노드는 사라지게 된다.

removeAll() : 리스트의 모든 노드 삭제. O(1)

// to remove all the nodes from the list
mutating func removeAll() {
    head = nil
    tail = nil
}

• 참조를 없애 노드들이 삭제되도록 head와 tail을 모두 nil로 만든다.

구현 - 동작 예시

var integerLinkedList = LinkedList<Int>()
integerLinkedList.push(1) // 앞에 추가 : 1
integerLinkedList.append(2) // 뒤에 추가 : 1 -> 2
integerLinkedList.push(0) // 0 -> 1 -> 2
integerLinkedList.insert(3, after: 2) // 인덱스2 뒤에 추가 : 0 -> 1 -> 2 -> 3

integerLinkedList.pop() // 앞에서 삭제 : 1 -> 2 -> 3
integerLinkedList.removeLast() // 뒤에서 삭제 : 1 -> 2
integerLinkedList.remove(after: 0) // 인덱스0 뒤 요소 삭제 : 1
integerLinkedList.removeAll() // 모든 요소 삭제 : Empty list

LinkedList 구현 전체 코드

주석이 없는 버전은 여기에 있습니다.

// 요소에 대한 데이터를 담는 클래스
class Node<T>: CustomStringConvertible, Equatable {

    var value: T
    var next: Node?

    // required conforms to CustomStringConvertible
    var description: String {
        guard let next = next else { return "\(value)" }
        return "\(value) -> " + String(describing: next)
    }

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

    // required conforms to Equatable
    static func ==(lhs: Node, rhs: Node) -> Bool {
        return lhs.next == rhs.next
    }
}

// A struct to hold the information of all the nodes
struct LinkedList<T>: CustomStringConvertible {

    // to hold the starting point of list
    var head: Node<T>?

    // to hold the ending point of list
    var tail: Node<T>?

    init() { }

    // if head is nil simply list is empty right now
    var isEmpty: Bool {
        return head == nil
    }

    // required conforms to CustomStringConvertible
    var description: String {
        guard let head = head else { return "Empty list" }
        return String(describing: head)
    }
}

// Common Methods
extension LinkedList {
    // node(at:) : O(i), i=index. 특정 인덱스의 노드를 찾기
    func node(at index: Int) -> Node<T>? {
        // if list is empty then simply return nil
        if isEmpty {
            return nil
        }

        var currentNode = head
        var currentIndex = 0
        while currentNode != nil && currentIndex < index {
            currentNode = currentNode?.next
            currentIndex += 1
        }
        return currentNode
    }

    // get number of nodes in the list
    func count() -> Int {
        var currentNode = head
        var count = 0
        while currentNode != nil {
            currentNode = currentNode?.next
            count += 1
        }
        return count
    }

    // push(_:) : O(1), 맨 앞에 삽입 head-first insertion
    mutating func push(_ value: T) {

        // create a new node and passing head (starting point) as a next node
        let newNode = Node(value: value, next: head)

        // change the head to the new node because head will hold the starting node
        head = newNode

        // if tail (ending node) is nil, it means head and tail pointing the same node as it is first node
        if tail == nil {
            tail = head
        }
    }

    // append(_:) : O(1), 맨 뒤에 삽입 tail-end insertion
    mutating func append(_ value: T) {

        // if list is empty then simply perform push operation
        if isEmpty {
            self.push(value)
            return
        }

        // create new node and assign it to tail's next because tail will always point the last node
        tail?.next = Node(value: value)

        // replace the tail with tail's next because before doing it tail's next pointing the last node
        tail = tail?.next
    }

    // insert(_:after:) : O(n), 주어진 인덱스 뒤에 삽입
    mutating func insert(_ value: T, after index: Int) {

        // if given index is not valid as per current list, it will be added in last
        if index < 0 || index >= self.count() {
            self.append(value)
            return
        }

        // if node not found just before to given insert index, perform push operation
        if let beforeNode = self.node(at: index), let tail = tail {

            // if insert index ie equal to last, simply append new node at last
            if beforeNode == tail {
                self.append(value)
            } else {
                // create new node and assign as a next node for the before node
                beforeNode.next = Node(value: value, next: beforeNode.next)
            }
        } else {
            self.push(value)
        }
    }

    // pop() : O(1). 맨 앞에서 제거.

    @discardableResult
    mutating func pop() -> T? {

        defer { // 함수 종료 직전에 실행
            head = head?.next
            if isEmpty {
                tail = nil
            }
        }
        return head?.value
    }

    //removeLast() : O(n). 맨 뒤에서 제거.
    @discardableResult
    mutating func removeLast() -> T? {

        // if head is nil, means no node exists.
        guard let head = head else { return nil } // <- isEmpty로 대체 가능

        // if head is not have any reference of next node, it means we have only one node in list.
        guard head.next != nil else { return pop() }

        // first we have to traverse to reach at last two nodes.
        var currentNode = head
        var previousNode = head

        while let next = currentNode.next {
            previousNode = currentNode
            currentNode = next
        }
        // 여기에 도달하면 currentNode가 마지막 노드가 된다. 마지막 노드에 대한 참조를 없애 삭제한다.
        // disconnected the next of last previous node
        previousNode.next = nil
        tail = previousNode
        return currentNode.value
    }

    // remove(after:) : O(n). 특정 인덱스 뒤의 노드를 삭제
    mutating func remove(after index: Int) -> T? {

        if index < 0 || index >= self.count() {
            return nil
        }

        if let beforeNode = self.node(at: index) {
            defer {
                if beforeNode.next == tail {
                    tail = beforeNode
                }
                beforeNode.next = beforeNode.next?.next
            }
            return beforeNode.next?.value
        }
        return nil
    }

    // to remove all the nodes from the list
    mutating func removeAll() {
        head = nil
        tail = nil
    }
}