LiskedList vs ArrayDeque vs 배열

// 원형 배열의 경우
realIndex = (head + index) % array.length;
element = array[realIndex];

// 일반 배열의 경우
element = array[index];

Queue의 구조는 한쪽에서는 삽입만 일어나고 한쪽에서는 삭제만 하는 자료구조 입니다. 즉, 먼저 들어간 것이 먼저 나오는 FIFO 구조입니다. 

앞과 뒤 전부에서 삽입 삭제가 가능한 Deque도 있습니다. 

Queue와 Deque의 인터페이스를 구현하는 대표적인 두 가지 클래스는 LinkedList와 ArrayDeque가 있습니다.

---

 

LinkedList

• 앞, 뒤 노드를 참조하고 있어 배열, ArrayDeque보다 상대적으로 오버헤드가 있음
• 요소들이 연속적으로 메모리 할당이 되어있지 않음

 

ArrayDeque

• 원형버퍼(배열)로 구성되어있다.
• 요소들이 연속적으로 메모리 할당 되어있음   <---배열에 의한 효과
• JVM이 최적화 해줌                                         <---배열에 의한 효과
• 배열보다는 약간의 오버헤드가 있음 
  • 앞(head), 뒤(tail) 포인터 가지고 있음
  • 경계검사

 

ArrayDeque는 배열이 아닌 원형배열로 구현된 이유?
만약 배열로 구현되어 있다면, poll()이 일어날 때마다 모든 요소들이 앞으로 한 칸씩 밀려나는 작업이(O(n)) 필요하다. 그래서 개선되기 위해서 도입된게 원형배열이다. 원형배열일 경우 head, tail의 포인터만 움직이면 되기 때문에 시간 복잡도 O(1)만 소요된다.

무조건 배열보다 원형배열이 좋을까?

아니다. 원형배열에 인덱스를 접근하기 위해서는  일반 배열보다 추가적인 연산이  필요하다. 그래서 랜덤액세스가 빈번한 경우에는 일반 배열이 더 적합하다.

// 원형 배열의 경우
realIndex = (head + index) % array.length;
element = array[realIndex];

// 일반 배열의 경우
element = array[index];

Deque의 크기가 변하지 않을 때 어떤 ADT를 사용해야 할까?
ArrayDeque는 원형버퍼 즉, 배열로 구성되어있다. 연속적으로 메모리가 할당된 배열은 엑세스하는 데 효율적이다. 또한 JVM은 배열에서 반복적인 작업은 최적화해주기 때문에 LinkedList보다 빠르다. 또한 LinkedList는 앞,뒤 노드들을 참조하기 때문에 메모리를 더 많이 사용한다. 객체 생성, 참조 비용 때문에 배열인 ArrayDeque를 사용하는 것이 더 좋다. 

 

결론

 

• ArrayDeque를 사용할 때:
  • 덱의 크기가 고정되고 양 끝에서 효율적인 삽입과 삭제가 필요할 때.
• LinkedList를 사용할 때:
  • 덱의 크기가 자주 그리고 크게 변하고, 삽입과 삭제가 자주 발생할 때.
• 일반 배열을 사용할 때:
  • 덱의 크기가 고정될 때