Today I Learned

오늘은 BFS 문제를 풀면서 의문을 가졌던 큐의 구현체에 대해 정리해보려 한다.

참고사이트 : tech-monster

ArrayDeque?

Stack<Integer> st1 = new Stack<>();
Stack<Integer> st2 = new ArrayDeque<>();

Quque<Integer> q1 = new LinkedList<>();
Queue<Integer> q2 = new ArrayDeque<>();

This class(ArrayDeque) is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.

• 자바 공식문서에서는 위처럼 스택 클래스와 링크드리스트 클래스를 쓰는것 보다 더 빠를 수 있다고 명시해두고 있다.

• BFS 문제를 풀고나서 여러 사람들의 풀이과정을 참고해보면 큐를 구현하는 방식이 크게 2가지 방법이있었다. LinkedList와 ArrayDeque. 두 경우가 어떻게 차이가 있는지 궁금했다.(추가로 스택도)

• http://yjacket.tistory.com/48 해당 블로그에서 테스트를 진행한 결과를 참고해보면 ArrayDeque이 LinkedList보다 삽입과 삭제 측면에서 약 2배가량 빨랐다.

Stack < ArrayDeque인 이유

• Stack클래스는 Vector를 상속해 구현하고 있어 LIFO 구조에 특화되어있지 않고 중간에서 데이터 삽입 삭제가 가능하다.
  모든 메서드에 synchronized가 있기때문에 단일 스레드 환경에서는 성능이 떨어진다.
  초기 용량을 설정할 수 없다.

• ArrayDeque은 위와 같은 문제를 해결하면서도 ThreadSafe하게 설계도 가능하다.

• 단, search() 메서드로 특정 값의 인덱스 위치를 알고싶다면 stack을 사용해야한다.

LinkedList < ArrayDeque인 이유

• ArrayDeque은 배열 기반이라 LinkedList에 비해 cache-locality에 더 친숙해 연산 속도가 더 빠르다. (LinkedList는 다음 노드가 있는 곳으로 가려고 다른 간접적인 경로를 거쳐간다.)

• 배열기반이라 특정 원소의 random access가 가능해 조회 속도가 더 빠르다.

• LinkedList와 달리 다음 노드에 대한 참조(포인터)의 유지가 필요없어 더 적은 메모리를 사용한다.

• 단 크기 조정과 삽입/삭제가 잦을경우 LinkedList가 더 유리할 수 있다. 하지만 일반적으로 큐는 양 끝에만 삽입 삭제가 일어나므로 ArrayDeque이 더 권장되는 것.

• ArrayDeque은 크기 조정이 가능하다.

• 단, null을 요소로 추가할 수 없다.