[Data Structures] Queue - Doubly Linked List based Implementation

Queue

요번에는 Doubly Linked List를 기반으로 구현한 코드를 살펴본다. Doubly Linked List 코드는 참고 링크 를 확인했다.

Doubly Linked List로 Queue 구현해보기

class QueueLinkedList<T>: Queue {
    private var linkedList = DoublyLinkedList<T>()
    
    var isEmpty: Bool {
        linkedList.isEmpty
    }
    
    var peek: T? {
        linkedList.first?.value
    }
    
    init() {}
    
    func enqueue(_ element: T) -> Bool {
        linkedList.append(element)
        return true
    }
    
    func dequeue() -> T? {
        guard !linkedList.isEmpty, let element = linkedList.first else {
            return nil
        }
        return linkedList.remove(element)
    }
}

앞 포스팅에서 만들어둔 Queue 프로토콜을 채택한 뒤 요구 사항에 맞게 구현했다. Doubly Linked List가 없었다면 구현할 수 없을…

실행 결과 및 복잡도 정리

• 실행 결과

• 복잡도

QueueArray는 큐에서 element를 제거하는 데 O(n)의 시간이 걸렸었지만 링크드리스트로 구현한다면 O(1)로 줄일 수 있다. (배열은 앞으로 한칸식 땡겨야되지만 링크드리스트는 노드만 해제하면 되니까.)

하지만 링크드리스트는 인스턴스 내부에서 prev와 next를 참조해야하기 때문에 오버헤드가 높은 편이다. 거기에 element를 추가할 때마다 인스턴스를 생성하므로 Array에 비해 비용이 많이 드는 동적 할당이 필요하다.

원래는 이것때문에 링버퍼를 살펴봐야 하지만… 바쁘므로 그냥 바로 스택 두개로 구현하는 걸 알아보러 간다.