Queue 구현 시, LinkedList보다 ArrayDeque를 추천하는 이유

Q를 쓸 때는 LinkedList보단 ArrayDeque를 쓰도록 하자

사유는 ArrayDeque가 메모리 사용 & 속도 면에서 더 효율적이기 때문이다

---

- Q는 인터페이스고 이것을 구현하는 구현체가 LinkedList & ArrayDeque가 있음

- 근데 ArrayDeque가 메모리 사용 & 속도 면에서 더 효율적이라고 함 (오늘의 핵심)

- LinkedList는 참조 객체 관리 비용 때문에 메모리 사용이 높다고...

참조 객체 관리 비용이란?

 

한줄 요약 : 각 노드가 누구를 가리키고 있는지 기억해둬야고, 이것 자체가 관리 비용이라는 것

 

LinkedList는 각 노드(Node)가 다음/이전 노드를 가리키는 "참조(Reference)"를 저장하는 방식으로 연결됨

이것 자체가 추가적인 메모리와 CPU 비용이 발생하는 것

즉, 각 노드는 데이터뿐만 아니라 '이전 노드'와 '다음 노드'를 가리키는 두 개의 참조(포인터)를 추가로 저장해야 하고, 이 두 개의 포인터를 따로 저장하는 것 자체가 비용이라는 것임

LinkedList는?

(1) FIFO(First In, First Out) 방식
(2) 양방향 연결 리스트로 삽입 & 삭제가 O(1) (중간 접근은 느림)

ArrayDeque는?

(1) 배열 기반의 Deque로, 양쪽에서 삽입 & 삭제가 빠름 (O(1))
(2) LinkedList보다 메모리 효율 & 속도 면에서 더 좋음

 

추가로 PQ는?

(1) 우선순위 큐로, 원소가 정렬된 상태로 관리
(2) 삽입 & 삭제가 O(log N)