[자료구조] 단방향 LinkedList 구현해보기

LinkedList를 Queue 타입으로 구현해보자! 

 

먼저 Queue 타입이 뭘까? 

Queue는 컴퓨터의 기본적인 자료구조로 먼저 들어온 순서대로 처리를 해주게 된다. 

(선입선출, FIFO - First In First Out으로 대기열을 구현하는 것이다)

 

만약 Queue 타입에 데이터를 넣게 되면 아래 그림처럼 가장 마지막에 들어오게 된다. 

11번째 데이터처럼 가장 마지막에 들어오게 되는 것이다. 

 

Queue에서 데이터를 빼주게 되면 처음 들어온 것이 가장 처음 나가게 된다. 

즉, 가장 먼저 들어 온 1번 데이터가 가장 먼저 나가게 되는 것이다. 

 

 

그럼 이런 Queue 타입을 위한 LinkedList를 구현해보자. 

일단 LinkedList의 경우 Array List와는 다르게 요소(Node)와 요소(Node) 간의 연결을 통해 리스트를 구현한 것을 의미한다. 

 

그렇다면 Array는 어떤 특징을 가지고 있을까?

Array의 경우 데이터의 인덱스가 정해져있다. 

따라서 배열의 Count를 계산하거나, Array[index]를 통해 직접 인덱스에 해당하는 값에 접근하거나, isEmpty인지 확인할 때 같은 경우에는 O(1)의 시간복잡도를 가지게 된다. 

 

또한 배열의 마지막 값에 접근하거나, 삭제를 해줄 때에도 O(1)의 시간복잡도를 가지게 된다. 

 

하지만 첫 번째 값을 삭제해줄 때에는 이야기가 달라진다. 

아래 그림처럼 첫 번째 Element를 지우고 다른 Element들의 index를 하나씩 뒤로 미뤄야 한다. 

따라서 이 경우 O(n)의 시간 복잡도를 가지게 된다. 

배열이 가지고 있는 Element가 많아지면 많아질수록 시간 복잡도는 이에 비례해서 늘어나게 되는 것이다. 

 

append 메서드의 경우 배열의 가장 뒤에 새로운 Element를 추가하게 되는데 평균적으로는 O(1)의 시간 복잡도를 가지나, 배열에 할당해놨던 메모리가 부족하게 되어 그대로 이를 복사해 메모리에 재할당해줘야 하는 경우 O(n)의 시간 복잡도를 가질 수 있다. 

 

Because arrays increase their allocated capacity using an exponential strategy, appending a single element to an array is an O(1) operation when averaged over many calls to the append(_:) method. When an array has additional capacity and is not sharing its storage with another instance, appending an element is O(1). When an array needs to reallocate storage before appending or its storage is shared with another copy, appending is O(n), where n is the length of the array.

Apple Developer Documentation 'Array' 참조

 

즉, 요약해보자면 Array의 경우 값에 접근하거나, 마지막 값을 제거할 때에는 시간복잡도 측면에서 우위에 있지만 값을 삽입하거나, 마지막 값 이외의 값을 제거할 때에는 시간복잡도 면에서 단점을 가지고 있다.

 

 

그렇다면 LinkedList의 경우 어떠할까?

일단 그림으로 LinkedList가 어떻게 구현되어 있는지 살펴보자

위 그림은 단방향 LinkedList이다. 

Data와 Next로 구성된 사각형이 하나의 Node라고 볼 수 있다. 

Data의 경우 해당 노드가 가지고 있는 값을 가지고 있고 Next에는 다음 노드에 대한 주소값을 가지고 있다. 

이처럼 Head 부터 시작해서 쭉 연결되서 List를 구성하고 있는 것을 볼 수 있다. 

 

따라서 값에 접근할 때에는 처음부터 타고타고 접근해야 해서 시간 복잡도에서 단점을 가지고 있다. 

하지만 Head의 값을 빼주는 경우 시간 복잡도가 O(1)이 된다. 

 

 

그렇다면 이러한 LinkedList를 어떻게 구현하면 좋을까?

일단 LinkedList를 구성하고 있는 Node를 구현해보자. 

class Node<Type> {
    var data: Type
    var next: Node?
    
    init(data: Type) {
        self.data = data
    }
}

단방향 LinkedList인 만큼 previous는 따로 구현하지 않고 next만 구현했다. 

또한 Node는 구조체가 아닌 Class로 구현했다. 

 

일단 next의 경우 Node 타입으로 만들어 다음 Node를 가리킬 수 있도록 구현해야 하는데 구조체로 구현할 경우 저장 프로퍼티에 재귀적으로 자신의 타입을 적어줄 수 없었다. 

Value type 'Node<Type>' cannot have a stored property that recursively contains it

(위는 구조체로 구현했을 때 발생하는 컴파일 에러이다)

 

그리고 LinkedList의 데이터를 추가하고 빼주는 메서드 or 연산 프로퍼티들의 경우 Queue 타입을 위한 것이기 때문에 다음과 같이 구성했다. 

• isEmpty(): 값이 비어있는지 확인하는 연산 프로퍼티
• enqueue(): List의 마지막에 데이터를 추가하는 메서드
• dequeue(): List의 첫 번째 데이터를 제거하는 메서드
• peek(): List의 첫 번째 데이터를 반환해주는 메서드 (제거는 하지 않음)
• clear(): List의 모든 데이터를 제거하는 메서드

struct LinkedList<Type> {
    
    // Node는 next의 주소값이 필요하기 때문에 구조체가 아닌 클래스로 구현
    class Node<Type> {
        var data: Type
        var next: Node?
        
        init(data: Type) {
            self.data = data
        }
    }
    
    var head: Node<Type>?
    var tail: Node<Type>?
    
    var isEmpty: Bool {
        head == nil
    }
    
    mutating func enqueue(_ data: Type) {
        let node = Node(data: data)
        
        if let nextNode = tail {
            nextNode.next = node
            tail = nextNode.next
        } else {
            head = node
            tail = node
        }
    }
    
    @discardableResult
    mutating func dequeue() -> Type? {
        let firstData = head?.data
        head = head?.next
        
        return firstData
    }
    
    func peek() -> Type? {
        return head?.data
    }
    
    mutating func clear() {
        head = nil
        tail = nil
    }
}