Kotlin의 ArrayDeque는 빠르고 효율적인 양방향 큐(Deque) 자료 구조로, Stack과 Queue의 기능을 모두 활용할 수 있어 다양한 상황에서 사용됩니다. 배열 기반으로 구현되어 있어 성능이 좋고, 일반적인 LinkedList 기반 Deque보다 더 효율적인 경우가 많습니다.
ArrayDeque
ArrayDeque는 Kotlin에서 제공하는 배열 기반의 양방향 큐(Deque) 자료구조입니다. Deque는 앞과 뒤 양쪽에서 요소ㅠ를 추가하거나 삭제할 수 있는 자료구조이며, ArrayDeque는 이를 배열로 구현하여 빠른 성능을 제공합니다.
먼저 ArrayDeque를 Queue처럼 사용한 경우 예시입니다.
val deque = ArrayDeque<Int>()
deque.addLast(1) // 뒤에 추가
deque.addLast(2)
deque.addFirst(0) // 앞에 추가
println(deque) // [0, 1, 2] 출력
val first = deque.removeFirst()
val last = deque.removeLast()
println(first) // 0 출력
println(last) // 2 출력
println(deque) // [1] 출력이번에는 ArrayDeque를 push와 pop을 이용하여 Stack처럼 사용해보겠습니다. 배열 기반이라 LinkedList보다 Stack으로 사용하기에 더 효율적입니다.
val stack = ArrayDeque<String>()
stack.push("A")
stack.push("B")
stack.push("C")
println(stack) // [C, B, A] 출력
val top = stack.pop()
println(top) // C 출력
println(stack) // [B, A] 출력💡 ArrayDeque VS LinkedList 기반 Deque
ArrayDeque는 내부적으로 배열 기반 원형 버퍼 구조를 사용하기 때문에, LinkedList 기반 Deque보다 더 빠르고 효율적인 경우가 많습니다. 이는 메모리 구조와 접근 방식에서 비롯됩니다.
연속된 배열 기반 메모리 구조
배열은 메모리 상에서 값들이 연속적으로 배치됩니다. 따라서 CPU 캐시를 활용할 수 있어 요소 접근 속도가 빠릅니다. 반면, LinkedList는 노드가 여기저기 흩어져 저장되며 포인터로 이어지기 때문에 캐시 효율이 떨어집니다.
단순한 인덱스 계산
ArrayDeque는 head와 tail의 이동이 단순한 인덱스 연산으로 이루어지지만, LinkedList는 노드의 next/prev 포인터를 관리해야해서 연산 비용이 크게 발생합니다.
불필요한 Node 객체가 없음
LinkedList의 각 요소는 value, next, prev 노드 객체를 생성하지만, ArrayDeque는 해당 구조 없이 값만 저장하므로 객체 생성 비용, 메모리 사용량이 적습니다.
🎯 결론
ArrayDeque는 배열 기반의 원형 버퍼 구조를 사용하기 때문에, 메모리 접근 효율성과 단순한 연산 구조 측면에서 LinkedList 기반 Deque보다 대부분의 상황에서 뛰어난 성능을 제공합니다.
특히
- 연속된 메모리 배치로 인한 빠른 접근 속도
- 불필요한 노드 객체 생성 없이 값만 저장하는 구조
- 인덱스 기반의 O(1) 연산
이러한 이유 때문에 일반적인 컬렉션 작업에서 성능과 효율성을 고려한다면, LinkedList 기반 Deque보다 ArrayDeque를 우선적으로 사용하는 것이 좋습니다.
