Linked List와 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)이 될 수도 있다. (흔하지는 않은 경우지만)
tail
을 구현해주면 O(1)이 가능하다. 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를 사용하는 점에서는 성능상으로는 더블스택이 우월하지 않을까🤔