[DataStructure] 이중 링크드 리스트를 Swift로 구현하기

https://m.hanbit.co.kr/store/books/book_view.html?p_code=B3450156021
이 글은 책 '뇌를 자극하는 알고리즘' 에서 배운 내용을 적극 참고하고 있습니다.
또한, 모든 자료구조 및 알고리즘은 Swift로 구현하고 있음을 먼저 알립니다.

* 이전 포스팅과 이어집니다!

[DataStructure] 링크드 리스트를 Swift로 구현하기

 

0. 서론

Single Linked List는 특정 노드의 이전 노드들에 대한 접근이 불편하였습니다.
이로 인해 노드의 삽입이나 삭제기능을 구현하는것도 조금 답답한 면이 있었지요.
예를들어 n번째 노드를 삭제하고 싶다면, n-1번째 노드에 접근하여 nextNode로 n번째 노드를 삭제하는 등 말이죠!
이런 단점을 어떻게 해소할 수 있을까요? 이전 노드를 가리키는 프로퍼티를 추가함으로써 해결할 수 있을것 같지 않나요?

1. 구조정의

이중 링크드 리스트(Doubly Linked List)의 각 노드들은 이전 노드를 가리키는 프로퍼티 Prev를 통해 이전 노드에 접근할 수 있습니다.
그리고 이 노드들을 또다시 주렁주렁 연결하여 Linked List를 형성하는 것으로, 더블리 링크드 리스트가 완성됩니다.
이제 이 구조와 삽입 - 삭제 - 탐색을 Swift로 구현하도록 하죠.

2. 구현

이전 노드를 가리키는 프로퍼티를 가진 새로운 클래스를 정의로 시작해보겠습니다.

class DoublyNode<T>{
    var prevNode: DoublyNode<T>?
    var nextNode: DoublyNode<T>?
    var data: T?
    init(prevNode: DoublyNode<T>? = nil, nextNode: DoublyNode<T>? = nil, data: T? = nil) {
        self.prevNode = prevNode
        self.nextNode = nextNode
        self.data = data
}

prevNode 프로퍼티는 이전 노드를 가리킵니다.
그리고 각 프로퍼티를 초기화하는 생성자도 만들어 두었습니다.

3. 삽입

///리스트의 처음에 노드 추가
    @discardableResult
    func insertAtFirst(_ newNode: DoublyNode<T>)->DoublyNode<T>{
        if self.head == nil{
            self.head = newNode
            return newNode
        }
        self.head?.prevNode = newNode
        newNode.nextNode = self.head
        self.head = newNode
        return newNode
    }
    ///리스트내 특정 위치에 노드 추가
    @discardableResult
    func InsertNodeAt(_ newNode:DoublyNode<T>, _ idx: Int) -> DoublyNode<T>?{
        if self.head == nil { return nil}
        var currentNode = self.head
        for _ in 0..<idx{
            if currentNode == nil {return nil}
            currentNode = currentNode?.nextNode
        }
        if currentNode?.prevNode == nil{
            self.head = newNode
        }
        currentNode?.prevNode = newNode
        newNode.nextNode = currentNode
        newNode.prevNode = nil
        return newNode
    }
    ///리스트의 가장 마지막에 노드를 추가
    @discardableResult
    func appendNode(_ newNode: DoublyNode<T>)->DoublyNode<T>{
        if self.head == nil {
            self.head = newNode
            return newNode
        }
        var tail = self.head
        while(tail?.nextNode != nil){
            tail = tail?.nextNode
        }
        newNode.nextNode = tail?.nextNode
        newNode.prevNode = tail
        tail?.nextNode = newNode
        return newNode
    }

추가할 위치까지 반복문을 통해 도달한 뒤, 해당 위치의 노드를 새 노드의 nextNode에, 이전 노드를 prevNode에 저장합니다.

3. 삭제

///리스트의 가장 마지막의 노드를 삭제
    @discardableResult
    func removeLast()->DoublyNode<T>?{
        if self.head == nil {
            return nil
        }
        var tail = self.head
        while(tail?.nextNode != nil){
            tail = tail?.nextNode
        }
        tail?.prevNode?.nextNode = nil
        tail?.prevNode = nil
        return tail
    }
    ///리스트의 처음 노드를 삭제
    @discardableResult
    func removeFirst()->DoublyNode<T>?{
        if self.head == nil{
            return nil
        }
        var removeNode = self.head
        self.head = self.head?.nextNode
        self.head?.prevNode = nil
        return removeNode
    }
    ///리스트의 특정 위치 노드를 삭제
    @discardableResult
    func removeAt(_ idx: Int)->DoublyNode<T>?{
        if self.head == nil {return nil}
        var removeNode = self.head
        for _ in 0..<idx{
            if removeNode?.nextNode == nil {return nil}
            removeNode = removeNode?.nextNode
        }
        if removeNode?.prevNode == nil { self.head = removeNode?.nextNode}
        removeNode?.prevNode?.nextNode = removeNode?.nextNode
        removeNode?.nextNode?.prevNode = removeNode?.prevNode
        removeNode?.prevNode = nil
        removeNode?.nextNode = nil
        return removeNode
    }

 특정 노드까지 이동한 후 노드의 프로퍼티를 비워주고, 이전 노드와 다음 노드의 저장을 끊어주면 ARC맨이 처리해줍니다!

4. 탐색

///리스트내 특정 위치의 노드 반환
    @discardableResult
    func getNodeAt(_ idx: Int) -> DoublyNode<T>?{
        if self.head == nil { return nil}
        var currentNode = self.head
        for _ in 0..<idx{
            if currentNode == nil {return nil}
            currentNode = currentNode?.nextNode
        }
        return currentNode
    }

 

5. 결론

저의 코드가 여전히 모든 작업에서 n번의 반복을 수행하고 있는것을 눈치채셨나요?
싱글이나 더블이나, 링크드 리스트는 O(n)의 한계에서 벗어나지 못하는군요,,
코딩 고수분들이 작성한 라이브러리 속 리스트는 어떻게 구현되어있는지 살펴보는것도 좋을 것 같습니다!
해당 내용은..! 다음 포스팅에서 다룰 링크드 리스트 시리즈의 마지막, 환형 링크드 리스트에서 알아보도록 하겠습니다.

6. 부록

이번 부록에서는,,!
책의 'Vitamin Quiz, 더블 링크드 리스트의 데이터를 역순으로 출력하는 함수를 작성해 보세요'를 구현해 보도록 하겠습니다.
저는 반복문을 사용해서 구현해보려고 해요! 이것이 정답은 아니며, 방법은 여러가지가 있을 수 있겠습니다.

데이터의 출력은 노드에 접근하여 data 프로퍼티에 접근함으로써 해결할 수 있습니다.
그리고 다시 이전 노드로 되돌아가고, 상기 행동을 첫 노드까지 반복 수행하면 데이터를 모두 출력할 수 있겠군요!
현재 DoublyLinkedList 클래스는 마지막 노드에 대한 정보를 직접적으로 가지고 있지 않다는 점도 참고해야 할 사항입니다.
이를 토대로, 함수의 로직을 순서대로 나열하면,

1. 리스트의 마지막 노드를 반복문으로 접근한다.
2. 현재 노드의 데이터를 출력한다.
3. 현재 노드의 이전 노드를 현재 노드로 변경한다.
4. 이전 노드가 nil이 아니라면, 과정 2로 돌아간다.
   (후에 포스팅할 스택을 사용한다면 1의 과정에서 데이터를 쌓고, 이를 출력하면 간단히 해결할 수 있다는 스포일러를 잠시 ㅎㅎ..)

위 과정을 코드로 구현하면 다음과 같습니다.

    ///리스트 내의 노드를 역순으로 각 노드의 데이터를 출력
    func printReverse(){
        if self.head == nil{
            print("\(type(of: self)) is empty")
        }
        var currentNode = self.head
        while currentNode?.nextNode != nil{
            currentNode = currentNode?.nextNode
        }
        while currentNode != nil{
            print("\(currentNode?.data)",terminator: " ")
            if currentNode?.prevNode != nil{
                print("->", terminator: " ")
            }
            currentNode = currentNode?.prevNode
        }
    }

 

소스코드 전문

//
//  DoublyLinkedList.swift
//  Swift-Practice
//
//  Created by Yune gim on 2024/03/21.
//
///더블 링크드 리스트, 특정 노드는 이전 노드와 이후 노드의 정보를 가지고 있다.
class DoublyLinkedList<T:Equatable>{
    var head: DoublyNode<T>?
    ///리스트의 처음에 노드 추가
    @discardableResult
    func insertAtFirst(_ newNode: DoublyNode<T>)->DoublyNode<T>{
        if self.head == nil{
            self.head = newNode
            return newNode
        }
        self.head?.prevNode = newNode
        newNode.nextNode = self.head
        self.head = newNode
        return newNode
    }
    ///리스트내 특정 위치에 노드 추가
    @discardableResult
    func InsertNodeAt(_ newNode:DoublyNode<T>, _ idx: Int) -> DoublyNode<T>?{
        if self.head == nil { return nil}
        var currentNode = self.head
        for _ in 0..<idx{
            if currentNode == nil {return nil}
            currentNode = currentNode?.nextNode
        }
        if currentNode?.prevNode == nil{
            self.head = newNode
        }
        currentNode?.prevNode = newNode
        newNode.nextNode = currentNode
        newNode.prevNode = nil
        return newNode
    }
    ///리스트의 가장 마지막에 노드를 추가
    @discardableResult
    func appendNode(_ newNode: DoublyNode<T>)->DoublyNode<T>{
        if self.head == nil {
            self.head = newNode
            return newNode
        }
        var tail = self.head
        while(tail?.nextNode != nil){
            tail = tail?.nextNode
        }
        newNode.nextNode = tail?.nextNode
        newNode.prevNode = tail
        tail?.nextNode = newNode
        return newNode
    }
    ///리스트의 가장 마지막의 노드를 삭제
    @discardableResult
    func removeLast()->DoublyNode<T>?{
        if self.head == nil {
            return nil
        }
        var tail = self.head
        while(tail?.nextNode != nil){
            tail = tail?.nextNode
        }
        tail?.prevNode?.nextNode = nil
        tail?.prevNode = nil
        return tail
    }
    ///리스트의 처음 노드를 삭제
    @discardableResult
    func removeFirst()->DoublyNode<T>?{
        if self.head == nil{
            return nil
        }
        var removeNode = self.head
        self.head = self.head?.nextNode
        self.head?.prevNode = nil
        return removeNode
    }
    ///리스트의 특정 위치 노드를 삭제
    @discardableResult
    func removeAt(_ idx: Int)->DoublyNode<T>?{
        if self.head == nil {return nil}
        var removeNode = self.head
        for _ in 0..<idx{
            if removeNode?.nextNode == nil {return nil}
            removeNode = removeNode?.nextNode
        }
        if removeNode?.prevNode == nil { self.head = removeNode?.nextNode}
        removeNode?.prevNode?.nextNode = removeNode?.nextNode
        removeNode?.nextNode?.prevNode = removeNode?.prevNode
        removeNode?.prevNode = nil
        removeNode?.nextNode = nil
        return removeNode
    }
    ///리스트내 특정 위치의 노드 반환
    @discardableResult
    func getNodeAt(_ idx: Int) -> DoublyNode<T>?{
        if self.head == nil { return nil}
        var currentNode = self.head
        for _ in 0..<idx{
            if currentNode == nil {return nil}
            currentNode = currentNode?.nextNode
        }
        return currentNode
    }
    ///리스트 내의 노드 수를 반환
    func getNodeCount()->Int{
        if self.head == nil {return 0}
        var count = 0
        var currentNode = self.head
        while(currentNode != nil){
            print("\(currentNode!.data!)",terminator: "")
            count += 1
            currentNode = currentNode?.nextNode
            if currentNode != nil { print(" -> ",terminator: "")}
        }
        print()
        return count
    }
    ///리스트 내의 노드를 역순으로 각 노드의 데이터를 출력
    func printReverse(){
        if self.head == nil{
            print("\(type(of: self)) is empty")
        }
        var currentNode = self.head
        while currentNode?.nextNode != nil{
            currentNode = currentNode?.nextNode
        }
        while currentNode != nil{
            print("\(currentNode?.data)",terminator: " ")
            if currentNode?.prevNode != nil{
                print("->", terminator: " ")
            }
            currentNode = currentNode?.prevNode
        }
    }
}