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

글은 책 '뇌를 자극하는 알고리즘' 에서 배운 내용을 적극 참고하고 있습니다.
또한, 모든 자료구조 및 알고리즘은 Swift로 구현하고 있음을 먼저 알립니다.

뇌를 자극하는 알고리즘

 

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

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

 

0. 서론

리스트 처음에 노드를 삽입하거나 삭제하는 것 처럼, 리스트 끝에 있는 노드를 추가하거나 삭제할 때 O(1)의 상수시간으로 처리될 수 있다면 많은 비용을 줄일 수 있을것 같다는 생각이 든 적은 없으신가요?
이전 포스팅의 Vitamin 문제에서 다뤘던 '리스트 역순 출력' 같은 경우에도, 마지막 노드까지 접근해야 하는 비용이 발생합니다!
(스택을 사용하지 않는다는 전제 하에 말씀 드리고 있습니다,,)

이제 때가 도래하였습니다.
리스트의 head 프로퍼티 처럼, 마지막 노드를 가리키는 tail 프로퍼티에 대해 생각해볼 때가!

혹시 우로보로스를 알고 계시나요? 자신의 꼬리를 삼키고 있는 모양이 마치 오늘 알아볼 환형 링크드 리스트 같군요!

전설의 뱀 우로보로스

1. 구조정의

첫 노드가 마지막 노드가 첫 노드와 연결돼있고, 그 반대도 마찬가지인 형태를 띄고 있습니다.
첫 노드를 head, 마지막 노드를 tail이라고 하고 나머지는 이중 링크드리스트에서 그대로 가져와도 무방하겠군요!

2. 구현

class CircularLinkedList<T>{
    fileprivate var head: DoublyNode<T>?
    fileprivate weak var tail: DoublyNode<T>?
    deinit {
        var currentNode = self.head
        while(currentNode != nil){
            currentNode?.nextNode = nil
            currentNode = currentNode?.prevNode
        }
    }
}

deinit 메소드 내부의 코드는 메모리 누수를 해결하려고 넣은 코드입니다.

3. 삽입

    ///리스트의 처음에 노드 추가
    func inertAtFirst(_ newNode: DoublyNode<T>){
        if self.head == nil{
            self.head = newNode
            self.tail = newNode
            return
        }

        self.head?.prevNode = newNode
        self.tail?.nextNode = self.head?.prevNode
        newNode.prevNode = self.tail
        newNode.nextNode = self.head
        self.head = newNode

    }
    //리스트의 특정 위치에 노드 삽입
    @discardableResult
    func insertAt(_ idx: Int, _ newNode: DoublyNode<T>)->DoublyNode<T>?{
        if self.head == nil {return nil}
        
        var currentNode = self.head
        for _ in 0..<idx{
            if currentNode == nil {return nil}
            currentNode = currentNode?.nextNode
        }
        
        currentNode?.prevNode?.nextNode = newNode
        currentNode?.prevNode = currentNode?.prevNode?.nextNode

        newNode.prevNode = currentNode?.prevNode
        newNode.nextNode = currentNode
        
        return newNode
    }
    ///리스트의 마지막에 노드 추가
    func insertAtLast(_ newNode: DoublyNode<T>){
        if self.head == nil {
            self.head = newNode
            self.tail = newNode
//            head?.prevNode = newNode
//            tail?.nextNode = newNode
            return
        }
        newNode.prevNode = self.tail //prevNode는 weak라 rf 증가 안한다
        newNode.nextNode = self.tail?.nextNode //rf 1 증가, newNode.nextNode = self.head시 head에 대한 rf가 증가함
        self.tail!.nextNode = newNode //새 노드의 rf 1 증가
        self.tail = newNode //tail은 weak라 rf 증가 안한다
    }

별다를게 없는 코드 입니다만,,
이제 tail 프로퍼티를 통해 리스트의 마지막 노드에 직접 접근할 수 있어 마지막에 노드를 추가하는 비용이 O(n)에서 O(1)로 절약됐음을 알수 있습니다!

4. 삭제

    ///리스트의 처음 노드를 삭제
    @discardableResult
    func removeFirst()->DoublyNode<T>?{
        if self.head == nil{
            return nil
        }
        var removeNode = self.head
        self.head = self.head?.nextNode
        self.head?.prevNode = self.tail
        self.tail?.nextNode = self.head
        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
        }
        removeNode?.nextNode?.prevNode = removeNode?.prevNode
        removeNode?.prevNode?.nextNode = removeNode?.nextNode
        return removeNode
    }

삽입과 마찬가지로 마지막 노드 삭제 또한 O(1)의 비용으로 수행할 수 있습니다.

5. 탐색

    ///리스트내 특정 위치의 노드 반환
    @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
    }

더이상 드릴 수 있는 말이 없습니다. 처음, 끝 노드를 반환하는 메소드를 직접 제작해보시길 바랍니다!

6. 링크드 리스트와 Swift의 배열 비교

자, 링크드 리스트와 통상적으로 알려진 간단히 비교해보았습니다.

	링크드 리스트	배열
메모리에 연속적으로 저장되어 있는가?	X	O
다음 자료를 가리키기 위한 추가적인 메모리가 필요한가?	O	X
특정 위치의 자료를 얻기 위한 비용은 얼마인가?	평균적으로 O(n), 경우에 따라 O(1)	O(1)
요소를 추가/삭제함에 따라 발생하는 빈 공간의 관리가 용이한가?	O	X

비교할거리는 더 많겠습니다만, 각 자료구조에 따라 장단점이 있다는 것을 알 수 있습니다.

그런데 말입니다, 혹시 여러분은 C, C++와 Swift에서 배열을 사용해 본 경험이 있으신가요? 저는 있답니다!
일반적으로 배열은 그 크기를 소스코드 레벨에서 지정하거나, C계열의 경우에 malloc 등으로 필요한 크기의 메모리를 할당해 사용합니다.
그러나 Swift에서는 배열을 사용하기 위해 메모리 할당 등의 작업을 한 기억은 없군요. 어떻게 된 일일까요?

//type var_name[demension], c++의 Array 생성
int arr[10];
//var var_name: [Element] = [], Swift의 Array 생성
var arr: [Int] = []

자자, 다른곳 기웃거릴 필요 없이 공식문서를 살피며 확인해볼까요?
(Swift의 공식문서와 Apple의 공식문서 두곳에서 확인할 수 있는데, Apple쪽 문서의 설명이 더 적합하다고 판단하였습니다.)

해당 문서에서 유일하게 예제코드 없이 말로만 설명하고 있는 부분이기도 합니다.

Every array reserves a specific amount of memory to hold its contents. When you add elements to an array and that array begins to exceed its reserved capacity, the array allocates a larger region of memory and copies its elements into the new storage. This exponential growth strategy means that appending an element happens in constant time, averaging the performance of many append operations. Append operations that trigger reallocation have a performance cost, but they occur less and less often as the array grows larger.

Swift에서 모든 배열은 컨텐츠를 저장하기 위해 특정한 크기의 메모리를 가지며, 새 요소를 append 할 때 기존 크기를 넘어서면 그 크기의 두배의 새 공간을 확보한 후 이곳으로 기존 배열을 복사합니다. 이러한 기하급수적 증가 전략은, 평균적으로 요소의 추가 상수시간 안에 일어나는것을 뜻하며, 메모리 재할당에 대한 수행비용은 발생하나 배열이 커감에 따라 줄어듭니다.

요컨대, 배열이 꽉 차면 스스로가 메모리 재할당을 수행하며 크기를 계속 늘려나가는 메커니즘을 취하고 있군요.
그렇다면 삽입, 삭제 등이 통상의 배열보다 용이할 수 있겠네요?
맞습니다! 공식 문서를 보고 오셨다면 이미 아시겠지만, Swift의 배열은 마치 링크드 리스트처럼 삽입, 삭제 등의 기능을 제공하고 있습니다!

var array:[Int] = []

let first = array.first!
let last = array.last!
array.append(1)
array.removeLast()
array.insert(1, at: 1)
array.remove(at: 1)
array.removeAll()

더 자세한 Swift 배열의 내용은 별도의 포스팅을 작성하여 배열에 대해 알아보는것으로 이쯤 마무리 짓겠습니다.
흠... Swift에서는 굳이 링크드리스트를 구현할 필요가 없어 보이는군요... T_T
손가락 아팠던 지금까지의 공부는 의미가 없던 걸까요?

7. 마무리

링크드 리스트를 손수 구현하고, 삽입이나 삭제등의 연산을 직접 고안해보면서 링크드 리스트가 어떤 방식으로 메모리 추가/삭제가 배열보다 용이하도록 고안되었고 동작하는지, 탐색/삽입/삭제 등의 연산이 왜 통상적으로 O(n)의 시간복잡도를 가지며 특정 경우에서 O(1)의 상수시간을 가지는지 알 수 있었습니다.
Xcode를 사용하다 보면 오른쪽 Quick Help창을 자주 보실텐데요! 이곳에 그동안 공부했던 내용이 도움이 될 때가 있습니다.
Swift의 배열에서 insert나 remove 함수의 문서를 마지막까지 읽어 보면, Complexity로 해당 함수의 비용을 안내하고 있습니다.

링크드 리스트를 공부하며 자주 보았던 O(n)을 Swift 배열의 Complexity에서도 볼 수 있군요!
이제 O(n)의 비용이 드는 이유를 조금 알것 같습니다! 비록 내부적인 구현이 어떻게 이루어져 있는지 알 수 없지만 말이죠

읽어주셔서 감사합니다. 다음에 또 만나요!