스위프트로 구현하는 자료구조 4: 더블 링크드 리스트(Doubly Linked List)

더블 링크드 리스트(Doubly Linked List)

 

더블 링크드 리스트는 링크드 리스트와 개념은 같지만 각 노드가 자신의 이전 노드까지 알고있다는 점에서 다릅니다. 기존 링크드 리스트는 각 노드가 바로 다음 노드의 참조 값만 알고 있지만, 이번에는 자신의 양쪽의 노드를 모두 참조하기 때문에 삭제나 삽입 연산의 구현이 조금 더 쉬워집니다.

 

뼈대 만들기

Node

import Foundation

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

 

데이터를 저장하고 리스트를 구성할 노드는 각자 자신의 id, 저장할 데이터, 이전 노드에 대한 참조값과 다음 노드에 대한 참조값을 가집니다.

 

Doubly Linked List

struct DoublyLinkedList<T: Equatable> {
    var head: Node<T>?
    var tail: Node<T>?
    
    var front: Node<T>? {
        return head
    }
    
    var back: Node<T>? {
        return tail
    }
    
    func showAll() {
        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("========================")
    }
}

링크드 리스트는 head 와 tail 프로퍼티를 가집니다. head 는 현재 링크드 리스트에서 가장 앞에 있는 노드를 가리키고, tail은 가장 뒤에 있는 노드를 가리킵니다.

 

front, back 은 head와 tail 프로퍼티를 통해서 가장 앞 노드와 마지막 노드의 참조 값을 반환하고, 링크드 리스트의 노드 목록을 순서대로 확인할 수 있는 showAll 메서드를 구현했습니다.

 

추가 (add) - O(1)

새로운 노드를 리스트 가장 끝에 추가하는 연산은 tail 포인터를 이용해서 O(1)에 수행할 수 있습니다. 두 가지 경우가 있을 수 있는데요,

 

1) 링크드 리스트에 아무 노드도 없는 경우

이 경우에는 새로운 노드를 head와 tail이 가리키게 하는 것으로 쉽게 노드를 추가할 수 있습니다.

 

2) 링크드 리스트에 노드가 존재하는 경우

이미 리스트에 노드가 존재하는 경우에는 tail이 가리키던 다음 노드를 새로운 노드로 지정하고, 새로운 노드의 이전 노드를 tail이 가리키는 노드로 지정합니다. 

그리고 이제 마지막 노드가 변경되었기 때문에 tail도 한 칸 오른쪽으로 이동시켜줍니다.

 

어떤 경우든지 tail을 사용해 마지막 노드를 바로 참조할 수 있기 때문에 항상 O(1)이 보장됩니다. 위 로직을 구현하면 이렇게 되겠죠!

    mutating func add(node: Node<T>) {
        if self.head == nil {
            self.head = node
            self.tail = node
            return
        }
        
        self.tail?.next = node
        node.prev = self.tail
        self.tail = node
    }

 

탐색 (search) - O(N)

특정한 노드를 탐색하기 위해서는 리스트의 첫 노드인 head부터 마지막 노드인 tail 까지 모든 노드를 검사해보아야 원하는 노드를 탐색할 수 있습니다. 이를 위해서 현재 노드를 가리키는 커서인 now 포인터를 사용하면 다음 노드로 계속 이동할 수 있습니다.

now 를 이동시키려면 재귀적으로, 혹은 반복문을 통해서 현재 노드의 다음 노드를 now로 변경해주면 됩니다. 그리고 새로운 now 가 가리키는 노드가 원하는 노드라면 해당 노드를 그대로 반환해주면 되겠죠. 탐색은 최악의 경우에는 전체 노드를 다 돌아봐야 하기 때문에 O(N)의 시간복잡도가 요구되고, 이중으로 연결된 리스트가 그다지 도움이 되지는 않습니다.

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

 

삽입 (insert) - O(1) or O(N)

이중으로 연결된 덕분에 삽입이 조금 더 쉬워졌습니다. 삽입 연산은 경우에 따라서 O(1)에 끝날 수도 있고, O(N)이 걸릴 수도 있습니다.

 

1) 삽입할 위치가 head나 tail일 때 - O(1)

새로운 노드를 삽입할 위치가 head 나 tail의 앞뒤라면 별도의 탐색과정없이 곧바로 삽입이 가능하기 때문에 시간복잡도가 O(1)이 됩니다.

4번과 5번 노드 사이에 새 노드를 끼워 넣고 싶다고 해보겠습니다.

우리는 마지막 노드가 tail이라는 정보를 가지고 있기 때문에 tail의 이전 노드를 참조해 그 다음 노드를 새로운 노드로 지정하고, 

새로운 노드의 이전 노드를 tail의 이전 노드로 지정합니다.

이제 이전노드와 새 노드의 연결은 끝났으니 마지막 노드인 tail의 이전노드를 새 노드로, 새 노드의 다음 노드를 tail로 지정해주면 새로운 노드의 삽입이 완성됩니다.

 

2) 삽입할 위치가 head나 tail이 아닐 때 - O(N)

삽입할 위치가 head나 tail이 아니라면 해당 위치를 탐색을 통해 찾아주어야 합니다. 때문에 위치를 탐색하는 시간 O(N)과 1번 처럼 실제 삽입을 진행하는 과정 O(1) 이 요구되어서 시간 복잡도는 O(N)이 됩니다. 탐색 + 삽입이 실제로 요구되는 것이죠.

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

 

삭제(delete) - O(1) or O(N)

삭제 연산은 기본적으로 삽입과 동일하게 특정한 노드까지의 탐색이 필요하고 이후에 삭제가 진행됩니다. 따라서 삭제할 노드가 head나 tail일 경우는 탐색이 필요없으니 O(1)이 되고, 그 외의 노드들은 O(N)이 됩니다.

 

삭제하는 과정은 아래와 같습니다.

 3번 노드를 삭제한다고 해볼게요!

삭제할 노드의 다음 노드가 삭제할 노드의 이전 노드를 가리키게 합니다.

그리고 삭제할 노드의 이전 노드가 삭제할 노드의 다음 노드를 가리키게 합니다. 그림에서 볼 수 있듯이 이제 3번 노드는 now 포인터에 의해서만 참조가 되는데요, now 포인터는 삭제 함수가 종료되면 함께 사라지는 변수이기 때문에 ARC에 의해 함수가 종료되면서 3번 노드는 사라지게 됩니다.

위 과정을 구현하면 이렇게 되겠죠?

    mutating func deleteNode(with id: Int) -> Node<T>? {
        var now = self.head
        
        if id == self.tail?.id {
            now = self.tail
        } else {
            while now?.id != id && now != nil {
                now = now?.next
            }
        }
        
        let deleted = now
        deleted?.next?.prev = deleted?.prev
        deleted?.prev?.next = deleted?.next
        
        if deleted === head {
            self.head = deleted?.next
        }
        
        if deleted === tail {
            self.tail = deleted?.prev
        }
        
        return deleted
    }

 

리스트 뒤집기 - O(N)

마지막으로 일반 링크드 리스트에서는 할 수 없고 더블 링크드 리스트에서만 할 수 있는 반전 연산을 소개하고 마치려고 합니다! 각 노드들은 자신의 이전과 다음 노드 정보를 가지고 있기 때문에 이전을 다음으로, 다음으로 이전으로 변경해주면 됩니다.

이렇게 있던 리스트를 next와 prev를 반전시켜서 뒤집으면,

이렇게 되겠죠? 하지만 아직 head 와 tail은 이전 상태의 양끝을 가리키고 있기 때문에 이대로 출력을 하면 1번 노드를 출력한 이후에 곧바로 nil이 반환됩니다. head 와 tail도 교환해줍시다!

이제 완벽하게 뒤집어진 링크드 리스트가 되었습니다!

 

위 과정에 대한 구현은 이렇습니다.

    mutating func reverse() {
        var now = head
        while now != nil {
            let nowNext = now?.next
            now?.next = now?.prev
            now?.prev = nowNext
            now = now?.prev
        }
        let nowHead = self.head
        self.head = self.tail
        self.tail = nowHead
    }

 

전체 코드

 

GitHub - jeonyeohun/Data-Structures-In-Swift: 👷🏻‍♂️ STL 왜 없어.. 스위프트로 구현하는 자료구조

자료구조 시리즈의 코드들은 이 레포에서 모두 확인할 수 있어요!