<java> ArrayDeque vs LinkedList

ArrayDeque vs LinkedList

ArrayDeque

1. 내부구현

• 배열을 기반으로 한 데크(Double-Ended Queue) 구현체
• 크기를 동적으로 조절할 수 있어서 큐에 요소를 추가하거나 제거할 때 크기를 변경할 필요가 없다.

2. 성능

• 큐의 크기를 동적으로 조절할 수 있으므로, 큐의 앞 또는 뒤에서의 요소 추가 및 제거가 상수 시간(O(1)) 이다.

3. 접근 시간

• 배열을 사용하기 때문에 인덱스를 통한 빠른 접근이 가능하다.

4. 메모리 사용

• 각 요소는 배열에 저장되므로 메모리 사용이 연속적이다.
• 고정된 크기의 배열을 사용하는 것이 아니라 동적으로 크기가 조절되므로 메모리 사용이 효율적이다.

LinkedList

1. 내부구현

• 이중 연결 리스트를 기반으로 한 데크 구현체
• 각 요소는 이전 요소와 다음 요소를 가리키는 링크로 연결된다.

2. 성능

• 큐의 앞에서 또는 뒤에서의 추가 또는 삭제는 O(1)
• 내부 내용 O(n)의 시간이 소요됩니다. -> 노드를 이동시켜야 하기 때문

3. 접근 시간

• 임의의 위치에서 요소에 접근하기 위해선 첫 요소부터 순차적으로 탐색해야 하므로 더 느리다.
• 요소들이 연결 리스트로 연결되어 있어서 중간에 요소를 삽입하거나 삭제할 때 빠르다.

3. 메모리 사용

• 비연속적인 메모리를 사용한다.
• 각 요소에 대한 추가적인 링크 정보가 필요하므로 메모리 사용이 더 많을 수 있다.

어떤 것을 사용할까?

ArrayDeque

• 큐의 앞이나 뒤에서 빈번하게 요소를 추가하거나 제거해야 하는 경우에 유용하다.
• 요소의 삽입, 삭제, 접근이 많이 일어나는 경우에 효율적이다.

LinkedList

• 중간에 요소를 추가하거나 삭제해야 하는 경우에 유용하다.
• 맨 앞이나 맨 뒤가 아닌 위치에 요소를 추가하거나 삭제하는 경우에도 효율적이다.