[Swift] Linked List를 이용한 List 구현

Queue나 Stack과 같은 자료구조가 끝 단에서 원소를 입출력할 수 있는 것과 달리 List는 임의의 순서의 데이터를 삽입 또는 삭제할 수 있는 자료 구조이다. 

Queue와 마찬가지로 List도 다양한 방법으로 구현할 수 있지만, 이번 포스팅에서는 Linked List를 이용하여 List를 구현해 보려고 한다. Linked List에 관한 포스팅(https://taeminator1.tistory.com/36)에서 설명한 바와 같이 Linked List를 이용할 경우, 삽입/삭제 연산 시 자료의 이동이 없어 효율적이기 때문이다. 

 

Linked List를 이용한 List의 삽입 연산

 

Linked List를 이용한 List의 삭제 연산

Linked List를 이용하여 Queue를 구현했을 때와 마찬가지로 LinkedList의 기능을 포함하므로 상속을 통해 구현해 주었다. 

클래스 다이어그램에서 알 수 있듯이, insert 함수는 삽입하고자 하는 Node와 index를 매개변수로 받고, remove 함수는 index를 매개변수로 받고 Node?를 반환한다. 

 

먼저 insert 함수의 실제 코드를 살펴보자. 

class List<Element>: LinkedList<Element> {
    func insert(_ node: Node<Element>, at index: Int) {
        guard index >= 0 && index <= count else {
            print("Index out of range")
            return
        }
        
        if index == self.count {        // 리스트의 마지막에 원소 추가
            append(node)
        }
        else {
            if index == 0 {             // 가장 앞에 추가되므로 추가 될 노드를 가리키는 노드 없음
                node.setNext(first)
                first = node
            }
            else {
                let tmpNode: Node = self[index - 1]!
                node.setNext(tmpNode.getNext())
                tmpNode.setNext(node)
            }
            count += 1
        }
    }
}

Node를 삽입하려는 위치가 List의 마지막이라면, 해당 연산은 LinkedList에서 구현해준 append와 동일하기 때문에, 조건절을 통해 삽입하려는 위치가 끝인지 아닌지를 먼저 확인하였다. 삽입하려는 위치가 끝이 아닌 경우에는 다시 처음인지 아닌지로 나뉘게 된다. 처음일 경우 List의 처음을 나타내는 first를 삽입되는 Node로 바꿔줘야 하기 때문이다. 

 

다음은 remove 함수이다. 

extension List {
    func remove(at index: Int) -> Node<Element>? {
        guard index >= 0 && index < self.count else {
            print("Index out of range")
            return nil
        }
        
        let result: Node = self[index]!
        if index == 0 {
            if count == 1 {         // List에 원소가 하나일 때
                first = nil
                last = nil
            }
            else {
                first = self[1]     // self[0]가 어디서도 참조되지 않으면 자동으로 메모리에서 해제 됨
            }
        }
        else {
            let tmpNode: Node = self[index - 1]!
            if index == self.count - 1 {        // 마지막 원소 삭제
                tmpNode.setNext(nil)
                last = tmpNode
            }
            else {                  // self[index]가 어디서도 참조되지 않으면 자동으로 메모리에서 해제 됨
//                self[index - 1]!.setNext(self[index + 1])
                tmpNode.setNext(tmpNode.getNext()!.getNext())
            }
        }
        count -= 1
        
        return result
    }
}

삭제 연산이기 때문에 삽입 연산과 반대로, 삭제 위치가 처음인지 아닌지를 가장 먼저 확인하였다. 삭제 위치가 처음이면, 원소의 개수에 따라 동작을 달리 해주었고, 삭제 위치가 처음이 아니라면, 삭제 위치가 마지막인지 아닌지에 따라 동작을 달리 해주었다. 삭제 위치가 처음도 아니고 마지막도 아닌 경우에 tmpNode.setNext(tmpNode.getNext()!.getNext())의 다소 기괴한(?) 코드를 살펴보자. 이것이 정확히 위에 삭제 연산의 그림을 설명하는 코드이다. 간단하게 self[index - 1]!.setNext(self[index + 1])라고 구현해도 되지만, subscript를 사용할 때마다 해당 인덱스를 찾기 위한 순회가 필요하므로 tmpNode를 이용해 순회를 최소화하였다. 

 

해당 클래스의 동작을 확인하기 위해 다음과 같이 실행하였다. 

var list: List = List<Int>()
list.insert(Node(0), at: 0)                                     // 빈 리스트에 원소 삽입

list.insert(Node(1), at: 0)                                     // list의 가장 앞에 삽입
list.insert(Node(2), at: 2)                                     // list의 가장 끝에 삽입
list.insert(Node(3), at: 1)                                     // list의 중간에 삽입

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

var tmpNode: Node<Int>?
tmpNode = list.remove(at: 1)                                    // list의 중간 삭제
print(tmpNode!.data)                                            // 3
                                                                // Node with 3 has been expired.
tmpNode = list.remove(at: list.count - 1)                       // list의 마지막 삭제
print(tmpNode!.data)                                            // 2
                                                                // Node with 2 has been expired.
tmpNode = list.remove(at: 0)                                    // list의 첫 번째 삭제
print(tmpNode!.data)                                            // 1
                                                                // Node with 1 has been expired.
tmpNode = list.remove(at: 0)                                    // list의 원소가 하나일 때 삭제
print(tmpNode!.data)                                            // 0

tmpNode = nil                                                   // Node with 0 has been expired.

앞에서 구현한 반복문이 전부 실행되도록 예제 코드를 구성하였다. 위의 실행 결과를 살펴보면, list의 마지막 원소가 삭제될 때 해당 원소에 해당하는 인스턴스가 메모리에서 해제되지 않는다. 그 이유는 출력을 위해 tmpNode가 해당 원소를 참조하고 있기 때문이다. 마지막 문장과 같이 tmpNode에 임의로 nil을 할당해주면 그제야 메모리에서 해제되는 것을 확인할 수 있다. 

 

끝으로 Array의 insert와 시간적으로 얼마나 차이가 나는지 확인해 보았다. 

 

먼저 마지막 위치에 원소를 삽입하는 경우이다. 100000번 반복할 때, Array와 List 모두 비슷한 시간에 완료되었다. 

 

다음은 처음 위치에 원소를 넣는 경우다. 마찬가지로 100000번 반복하였다. Array의 경우, 처음에 넣게 되면 데이터 이동을 해야 하므로 List에 비해 시간이 오래 걸리는 것으로 보인다. 

 

마지막으로 Array와 List에 10개의 원소를 미리 넣고, 100000번 동안 10번 위치에 원소를 넣는 경우다. Array의 경우 큰 차이는 없지만, List의 경우 1초가량이 늘었다. 해당 시간은 삽입 위치가 커지면 소요되는 시간도 커지는 걸로 봐서 subscript를 통해 삽입할 위치를 찾는 것이 오래 걸리는 모양이다. 

 

결론적으로 List의 경우 연산하려는 위치가 커질수록 시간이 오래 걸린다. 하지만 subscript 없이 List의 양 끝단에서 연산이 이루어질 경우, 빠른 속도를 보여 주었다. 해당 결과로 미루어 보아, Linked List로 구현한 Queue subscript 없이 양 끝 단에서 연산이 이루어지므로 Array로 구현한 Queue 보다 빠를 것이라고 예측할 수 있다.