[Swift] Linked List 구현

Linked List는 Array와 자주 비교되는 대표적인 자료 구조 중 하나이다. 

메모리에 각각의 원소를 순차적으로 저장하는 Array와 달리, Linked List는 데이터와 링크로 구성된 노드를 이용하여 메모리에 저장된 순서와 상관없이 연결된 데이터 구조를 말한다. 

 

Linked List의 구조

각각의 사각형은 Node를 의미한다. Node는 데이터(채색되어 있지 않은 부분)와 링크(채색되어 있는 부분)로 나뉘는데 데이터에는 저장하길 원하는 값을 넣고, 링크에는 다음 노드를 가리키도록 하여 Linked List를 구현할 수 있다. 

 

Array와 Linked List는 각각 대비되는 장점이 존재한다. 

먼저 Array는 사용이 쉽다. Swift를 포함한 대부분의 언어에서 Array를 기본적으로 제공한다. 특히 Swift의 Array는 내장 함수들도 많이 있어, 추가적으로 메서드를 정의할 필요 없이 바로 사용이 가능하다. Extension을 이용해 쉽게 확장도 가능하다. 하지만 삭제나 삽입과 같은 연산 시에는 원소를 빈번히 옮겨야 하기 때문에 비효율적이다. 아래와 같이 두 번째 원소를 지우고 난 이후에 빈 공간을 메꾸기 위해 이후 원소들이 한 칸씩 앞으로 당겨져야 한다. 

 

Array에서의 삭제 연산

반면 Linked List는 Swift에서 따로 제공하는 타입이 없어 구현을 직접 해야 하는 번거로움이 있지만, 삭제 및 삽입 연산 시에 원소의 이동 없이 바로 연산을 수행할 수 있다. 원하는 위치를 찾기 위해 순회를 하기 때문에 시간 복잡도는 O(n)으로 Array와 같지만 원소의 이동이 없어 효율적이다. 아래와 같이 두 번째 원소를 지우기 위해 첫 번째 원소가 가리키는 Node를 세 번째로 바꾸기만 하면 된다. 

 

Linked List에서의 삭제 연산

 

<Array와 Linked List 비교>

Swift에서 Linked List를 구현하기 위해서는 위 그림(Linked List 구조)에 표시된 개별 Node에 대한 타입을 구현해 주어야 한다. Node는 데이터와 링크로 구성되는데, 여기서는 각각에 대응되는 속성을 data와 next로 명명하였다. 

Node에 대한 클래스 다이어그램을 살펴보면, 

Generic을 이용해 타입에 대한 제약이 없도록 하였고, 다음 Node는 있을 수도 있고 없을 수도 있기 때문에 Optional로 선언하였다. 

그리고 해당 Node가 가리키는 노드를 위한 메서드를 추가하였다.

deinit은 인스턴스가 언제 메모리에서 해제되는지 확인하기 위해 추가하였다. 

class Node<T> {
    var data: T
	var next: Node?         // 다음 Node를 가리키기 위한 변수
    
    init(_ data: T) {
        self.data = data
        print("Node with \(data) has been created.")
    }
    
    func getNext() -> Node<T>? {
        return next
    }
    
    func setNext(_ node: Node<T>?) {
        self.next = node
    }
    
    deinit {
        print("Node with \(data) has been expired.")
    }
}

이제 해당 타입을 이용하여 Linked List를 구현해보자. 최대한 Swift에서 기본으로 제공하는 Array와 비슷한 느낌으로 사용할 수 있게 하기 위해 Array 타입에 있는 요소를 차용하였다. 그리고 추후 Queue나 List 등을 구현할 때를 고려하여 프로퍼티와 메서드를 선정하였다. 

LinkedList에 대한 클래스 다이어그램을 살펴보면, 

첫 번째와 마지막 Node를 나타내는 first와 last가 Optional로 선언되어 있고, 원소의 개수를 저장하는 count가 있다. 

subscript를 이용해 원소를 조회/수정 가능하도록 구현하였다. 

class LinkedList<Element> {
    var first: Node<Element>?
    var last: Node<Element>?
    var count: Int              // 원소의 갯수 저장
    
    init() {
        self.count = 0
    }
    
    init(_ node: Node<Element>) {
        self.first = node
        self.last = node
        self.count = 1
    }
}

매개변수에 따라 두 가지로 초기화 가능하도록 구현하였다. 

extension LinkedList {
    subscript(_ index: Int) -> Node<Element>? {
        get {
            guard index >= 0 && index < count else {
                print("Index out of range")
                return nil
            }
            
            var node: Node<Element>? = first
            for _ in 0 ..< index {              // index의 값만큼 다음 Node로 이동
                node = node!.getNext()!
            }

            return node
        }

        set {
            guard index >= 0 && index < count else {
                print("Index out of range")
                return
            }
            
            newValue!.setNext(self[index + 1])	// 대상 Node의 다음 Node 설정
            
            if index == 0 {                     // 첫 번째 원소를 수정하는 경우
                self.first = newValue           // 대상 Node를 first로 설정
            }
            else {                              // 이전 Node의 다음 Node를 대상 Node로 설정
                if index == count - 1 {         // 마지막 원소를 수정하는 경우
                    self.last = newValue
                }
                var node: Node<Element> = first!
                for _ in 0 ..< index - 1 {
                    node = node.getNext()!
                }
                node.setNext(newValue)
            }
        }
    }
}

subscript 부분에서 눈여겨볼 곳은 set 부분이다. 대상 Node의 다음 Node를 설정한 다음, 이전 Node의 다음 Node로 대상 Node를 설정해주어야 한다. 순서를 바꾸게 되면, 이전 Node의 다음 Node를 대상 Node로 설정하는 것은 문제가 없지만, 대상 Node의 다음 Node를 설정하기 위해 순회하는 과정에서 오류가 발생한다. 

extension LinkedList {
    func isEmpty() -> Bool {
        return count == 0 ? true : false
    }
    
    func append(_ node: Node<Element>) {
        if isEmpty() {
            first = node
        }
        else {
            last?.setNext(node)
        }
        last = node
        count += 1
    }
}

가장 기본이 되는 메서드를 구현해 주었다.  

 

해당 타입은 다음과 같이 사용할 수 있다. 

var linkedList: LinkedList = LinkedList<Int>(Node(1))           // Node with 1 has been created.
linkedList.append(Node(2))                                      // Node with 2 has been created.
linkedList.append(Node(3))                                      // Node with 3 has been created.

print(linkedList[0]!.data)                                      // 1
print(linkedList[1]!.data)                                      // 2
print(linkedList[2]!.data)                                      // 3

linkedList[1] = Node(4)                                         // Node with 4 has been created.
                                                                // Node with 2 has been expired.

print(linkedList[0]!.data)                                      // 1
print(linkedList[1]!.data)                                      // 4
print(linkedList[2]!.data)                                      // 3

linkedList [1] = Node(4) 구문이 실행되면 기존에 인스턴스화 된 Node(2)는 메모리에서 해제되는 것을 알 수 있다. 

 

이렇게 간단하게 Linked List를 구현해 보았다. 이제 확장을 통해 원하는 연산을 구현하거나, 상속을 통해 다양한 클래스를 추가로 만들 수 있게 되었다.