"Deque 인터페이스의 구현체인 LinkedList와 ArrayDeque에 대해서 정리해보고자 한다."
Deque
- 원소의 추가와 삭제를 앞, 뒤 양방향에서 지원하는 선형 컬렉션이다.
- 큐, 스택 기능을 모두 가지고 있어 원하는대로 사용 가능하다.
- 대부분의 Deque 구현체는 Deque가 포함하고 있는 원소의 수 제한이 없다.
- But, Deque 인터페이스는 고정 사이즈 제한을 가진 것과 똑같이 용량 제한 Deque를 지원한다.
- insert(추가), remove(제거), reverse(뒤집기) 등등 많은 메소드를 지원한다.
- 어느 방향에서나 동일한 O(1)성능으로 Deque의 양쪽에서 스레드 안전, 메모리에 효율적인 추가 및 제거를 지원한다.
LinkedList
- 컬렉션 프레임워크의 일부로써, List와 Deque 인터페이스의 양방향 링크 리스트의 구현체이다.
- 데이터가 연속된 위치에 저장되지 않고 모든 데이터가 데이터 부분과 주소 부분을 별도로 가지고 있다.(데이터는 포인터와 주소를 사용해서 연결함!!)
- 각 데이터는 노드라고 부르고, 배열에서 자주 삽입 삭제가 이루어질 때 용이하다.
- null요소를 추가할 수 있다.
- 반복중에 현재 요소를 제거하는 것이 효율적이다.
- ArrayDeque보다 더 많은 메모리를 소모한다.
- 다만, ArrayList보다 검색에 있어서 느리다.
- 위와 같은 형태인데 양방향이니까 아래와 같이 설명할 수 있을 것 같다.
ArrayDeque
- Deque 인터페이스의 사이즈 조정이 가능한 Array의 구현체이며, 용량 제한이 없다.
- null 요소를 추가할 수 없다.
- 양쪽 끝에서 추가, 제거가 효율적이다.
- LinkedList보다 적은 메모리를 소모한다.
정리
- 메모리 소모량이 적을 때는 반복효율이 좋은 ArrayDeque를 사용하고 스택의 사이즈가 커지거나 심한 변동이 예상될 때는 즉각적인 메모리 공간 확보를 위해 LinkedList를 사용한다.
- ArrayDeque는 다음 노드에 초가적인 reference를 유지할 필요가 없기 때문에 LinkedList보다 메모리 효율적
