Queue 타입 구현: Linked List / Double Stack

Lily·2021년 12월 23일
0

📇 Queue

특징

  • 선형 자료 구조
  • 자료의 삽입, 삭제 방식 : 선입선출, FIFO(First In First Out)

구현 방법

Linked List와 Double Stack으로 구현하는 방법을 자료의 탐색, 삽입, 삭제의 효율성 측면에서 비교해보았다.

1. Double Stack

  • 스위프트에서는 두개의 array(배열)로 더블 스택을 구현할 수 있다.
    스위프트 array 시간복잡도

    • 삽입(append) : O(1), 메모리 재할당해야하는 경우는 O(n)
    • 삭제(remove(at:)) : O(n)
    • 탐색(index) : O(1)
  • enqueue 스택, dequeue 스택

  • Double Stack Queue에서 enqueue, dequeue를 할 때 array의 append(), removeLast()reversed()를 사용해서 시간 복잡도는 각 O(1)이다. ( 반면, 하나의 Queue 사용할 때 dequeue를 할 때는 removeFirst()를 사용해서 O(n)이다 )

  • 큐의 중간에 데이터를 추가/삭제할 때는 링크드리스트보다 좀 더 여러 단계를 거쳐서 비용이 많이 든다. 추측으로는 O(n)

  • array는 탐색이 O(1)이어서 중간요소를 접근하는데는 효율적이지만, enqueue, dequeue방식으로 중간요소를 추가하거나 삭제하려면 O(n)의 비용이 들거라 생각한다.

  • 추가적으로 append()를 실행할 때 새로운 메모리를 할당해야할 경우에는 O(n)이 될 수도 있다. (흔하지는 않은 경우지만)

2. Linked List

  • 단방향에서 양방향, 원형 링크드리스트로 수정이 가능하고, 확장에 열려있다.
  • 추가, 삭제의 시간복잡도는 O(1)이지만 탐색은 O(n)이므로 결국 탐색을 고려하면 시간복잡도는 O(n)이 된다. 하지만 tail을 구현해주면 O(1)이 가능하다.
  • Queue에서 enqueue, dequeue를 할 때, enqueue는 tail을 구현해주었기 때문에 결론적으로는 O(1), dequeue는 O(1)의 시간복잡도를 가질 것이다.
  • 큐의 중간에 데이터를 추가/삭제할 때는 중간의 노드를 탐색하려면 찾으려는 노드의 index만큼 순회를 해줘야한다. 추측으로는 O(n)
struct LinkedList<Element> {
    final class Node<Element> {
        var data: Element?
        var next: Node?
        
        init(data: Element?, next: Node? = nil) {
            self.data = data
            self.next = next
        }
    }
    
    private var head: Node<Element>?
    private var tail: Node<Element>?
    var isEmpty: Bool {
        return head == nil
    }
    var first: Element? {
        return head?.data
    }
    
    init() { }
    
    init(data: Element?) {
        self.head = Node(data: data, next: nil)
        self.tail = head
    }
    
    func node(at index: Int) -> Node<Element>? {
        if index == 0 {
            return self.head
        } else {
            var node = head?.next
            for _ in 1..<index {
                node = node?.next
                if node == nil {
                    break
                }
            }
            return node
        }
    }
   
    mutating func insert(_ newNodeData: Element, at index: Int) {
        if index == 0 {
            let newNode = Node(data: newNodeData, next: nil)
            newNode.next = head
            head = newNode
            return
        }
        let previousNode = node(at: index - 1)
        let newNode = Node(data: newNodeData, next: nil)
        
        guard let nextNode = previousNode?.next else {
            previousNode?.next = newNode
            tail = newNode
            return
        }
        previousNode?.next = newNode
        newNode.next = nextNode
    }
    
    mutating func remove(at index: Int) -> Element? {
        if index == 0 {
            let presentNode = head
            head = head?.next
            return presentNode?.data
        }
        let previousNode = node(at: index - 1)
        let presentNode = previousNode?.next
        guard let nextNode = previousNode?.next?.next else {
            previousNode?.next = nil
            tail = previousNode
            return presentNode?.data
        }
        previousNode?.next = nextNode
        return presentNode?.data
    }
    
    mutating func append(_ data: Element) {
        let nextNode = Node(data: data, next: nil)
        if isEmpty {
            head = nextNode
            tail = head
            return
        }
        tail?.next = nextNode
        tail = nextNode
    }
    
    mutating func removeAll() {
        head = nil
        tail = nil
    }
}

👩🏻‍⚖️ 결론

더블스택, 링크드리스트 모두 enqueue, dequeue의 시간복잡도는 O(1)이고,
중간 자료에 대한 삽입, 삭제도 시간복잡도가 O(n)으로 동일할 것이라 판단했다.

단, 링크드리스트가 더블 스택보다 절차가 더 간편해서 공간복잡도가 낮지 않을 까 생각된다.

하지만 링크드리스트는 node를 클래스(참조 타입)로 구현하고, 더블 스택은 구조체(값 타입)인 array를 사용하는 점에서는 성능상으로는 더블스택이 우월하지 않을까🤔

profile
i🍎S 개발을 합니다

0개의 댓글