PS tip: 그래프 탐색의 자료구조 - ArrayDeque

PS를 하다보면 그래프 탐색도 문제 많이 풀게 되죠. 그래서 저는 거의 공식처럼 외우고 있는 내용이 있어요.

DFS할 때는 Stack || ArrayList || 재귀, BFS할 때는 LinkedList로 구현된 Queue.

저만 생각하는 부분은 아닐거에요.😀

근데 혹시 Deque로 구현하면 어떨까요?

예를 들어, Stack 자료구조의 문서로 가보면 이런 설명이 있습니다. : "Stack보다는 Deque 인터페이스를 우선적으로 사용하세요. 그게 더 빠릅니다"

 

저의 경우에는 그 문구를 보고 나서부터 Deque를 사용하게 되었어요.

그런데 습관적으로, 이렇게 사용했습니다.

 

Deque<Integer> deque = new LinkedList<>();

'앞 뒤로 remove가 일어나니까 ArrayList는 적합하지 않을 것 같아' 정도의 단순한 생각으로 LinkedList를 사용하게 되었어요.

 

그런데! Deque를 위한 적절한 구현체가 따로 존재한다는 사실을 오늘 알게되었습니다. 😃

바로 제목에 있는 ArrayDeque class입니다.

 

ArrayDeque도 자바 표준 자료구조(Collections)에 포함되어 있습니다.

Queue의 확장이에요(그래서 stack 자료구조의 pop과 같은 동작이 pollLast와 같은 이름으로 정의되어있죠).

기본적인 동작도 FIFO지만, LIFO처럼도 동작할 수 있습니다.

그렇지만 FIFO를 Stack보다 빠르게 동작하고, LIFO를 LinkedList로 구현된 Queue보다 빠르게 동작할 수 있습니다.

 

ArrayDeque의 대부분 작업은 상수 시간에 실행됩니다. 탐색, iterator를 통한 작업 등 몇 가지 작업이 예외적으로 선형 시간에 실행되고요.

그리고 이니셜 버퍼 만큼씩 크기가 확장되기 때문에 input이 빠릅니다.

마지막으로, PS와는 상관이 없겠지만, fail-fast로 동작합니다.

 

만약 Deque가 익숙치 않거나, ArrayDeque 구현체를 사용해보신 적이 아직 없으시다면 이번 기회에 한 번 사용해 보세요!