• 이해를 위한 배경 지식

컬렉션 프레임 워크 구조를 간단하게 살펴보자. 알고 있다면 본론으로 바로 넘어가자!

[1] List - #순서 있음, #중복 요소 허용, #인덱스 접근
[2] Queue - #FIFO, #Enqueue, Dequeue로 삽입 삭제
[3] Set - #중복 요소 허용X, #요소들의 순서가 없음(LinkedHashSet예외)
[4] Map - #Key-Value쌍 #키는 유일함



---

본론

백준 14442 벽 부수고 이동하기2 문제를 풀고나서, 싸피 인피케이님께서 다음과 같은 말을 해주셨다.

LinkedList보다 ArrayDeque가 더 성능좋아요. 한번 구현체를 갈아끼워서 성능 한번 비교해보세요!

ArrayDeque가 더 성능이 좋다고 들은 적은 있었지만, LinkedList로 작성하는게 습관이 되어서 고치지 않고 있었다. 사실, 어느 정도의 성능차이가 있는지 와닿지 않아서 고치지 않고 있었다.

그래서 이번 기회에 성능을 비교해보았고, 아래 사진처럼 유의미한 성능 차이를 보이는 것을 확인하였다.

---

그래서 왜 ArrayDeque를 쓰라는건가요?

우선 각 구현체가 어떤 인터페이스의 구현체인지 먼저 살펴보자.

• Queue의 하위 인터페이스 Deque를 구현한 것이 ArrayDeque
• List와 Queue를 구현한 것이 LinkedList

둘의 결정적인 차이는 ArrayDeque는 배열처럼 연속적인 메모리에 데이터가 저장되고, LinkedList는 다음 노드를 포인터로 가리키는 것을 보면 알 수 있듯이 불연속적인 메모리에 데이터들이 저장된다.

이전 게시글에서도 red-black tree가 인덱스 방식으로 사용되지 못한 이유로

배열의 인덱스 기반 데이터 접근이 포인터 기반 접근 방식보다 훨씬 빠르다!

는 말을 했었다.


이 개념은 여기서도 적용된다. LinkedList도 삽입/삭제 연산 성능은 우수하지만, 특정 노드에 접근 할 때 성능은 ArrayDeque에 비해 떨어진다.

또한, ArrayDeque는 배열 기반이기에 다음 노드에 대한 참조를 관리할 필요가 없기 때문에 더 적은 메모리를 사용한다.

위에 백준 메모리 사용한 정도와 실행시간 모두 최근 제출한 코드(ArrayDeque 구현체로 갈아끼운 코드)가 더 성능이 우수하다는 것을 볼 수 있었다!

결론은?

ArrayDeque가 LinkedList보다 속도, 메모리 측면에서 더 좋은 성능을 보인다!

단, Thread-Safe 해야하는 개발환경이라면 다른 구현체를 사용해야한다. Array Deque는 자체는 Thread-Safe 하지 않음.

알고리즘 풀 때는 멀티쓰레드를 전혀 고려하지 않아도 되므로 스택, 큐 모두 ArrayDeque 구현체를 쓰자!