[Java] Queue를 ArrayList가 아닌 LinkedList로 구현해야 하는 이유

ArrayList와 LinkedList 의 차이점

ArrayList는 중복을 허용하고 순서를 유지하며 인덱스로 원소들을 관리한다는 점에서 배열과 상당히 유사합니다. 배열은 크기가 지정되면 고정되지만 ArrayList는 클래스이기 때문에 배열을 추가, 삭제 할 수 있는 메소드들도 존재합니다.

하지만 추가했을 때 배열이 동적으로 늘어나는 것이 아니라 용량이 꽉 찼을 경우 더 큰 용량의 배열을 만들어 옮기는 작업을 하게 됩니다.

LinkedList는 내부적으로 양방향의 연결 리스트로 구성되어 있어서 참조하려는 원소에 따라 처음부터 순방향으로 또는 역순으로 순회할 수 있습니다. (배열의 단점을 보완하기 위해서 링크드 리스트(Linked list)라는 자료구조가 고안되었습니다.)

배열의 단점은 아래와 같습니다.

크기를 변경할 수 없다.
- 크기를 변경할 수 없으므로 새로운 배열을 생성해서 복사해야 합니다.
- 실행속도를 향상시키기 위해서는 충분히 큰 용량을 미리 정해놔야 하는데 이것이 메모리 낭비가 될 수 있습니다.
비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다.
- 차례대로 데이터를 추가하고 마지막에서부터 데이터를 삭제하는 것은 빠릅니다.
- 배열의 중간에 데이터를 추가하거나, 삭제하면 빈공간을 만들기 위해 데이터 이동이 필요하고, 빈공간을 채우기 위해 데이터 이동이 빈번할 것입니다.

순차적으로 추가하기
- ArrayList: 순차적으로 추가하면 배열 원소들의 이동이 없이 추가만 하면 되기 때문에 쉽게 할 수 있습니다.
- LinkedList: LinkedList는 순차적으로 추가하면 그 추가하고자 하는 곳으로 계속 탐색해서 가야 합니다. 하지만 내부적으로 양방향으로 되어 있기 때문에 ArrayList와 큰 차이가 나지는 않습니다.
중간에 추가하기
- ArrayList: 중간에 추가하게 되면 빈 공간을 만들어야 하기 때문에 원소들의 이동이 필요하기 때문에 상당히 비효율적입니다.
- LinkedList: 중간에 추가할 때는 추가하고자 하는 원소 앞 or 노드로 가서 가리키고 있는 주소만 추가해주면 되기 때문에 금방 할 수 있습니다.
중간에서 삭제하기
- ArrayList: 중간에서 삭제하는 것도 마찬가지로 중간에 빈 공간이 생기기 때문에 채우기 위해서 원소들의 이동이 일어나므로 시간이 오래 걸립니다.
- LinkedList: 중간에서 삭제하는 것도 추가하는 것과 마찬가지의 과정입니다.
순차적으로 삭제하기
- ArrayList: 순차적으로 마지막 원소를 삭제할 때는 원소들의 이동이 필요 없기 때문에 시간이 오래 걸리지 않습니다.
- LinkedList: LinkedList는 내부적으로 양방향 연결리스트로 되어 있기 때문에 ArrayList와 큰 차이가 없는 것을 볼 수 있습니다.

순차적으로 추가/삭제하는 경우에는 ArrayList가 LinkedList보다 빠르다.
- 단순히 저장하는 시간만을 비교할수록 하기 위해서 ArrayList에서 배열 재배치가 일어나는 상황은 제외하였습니다. 그렇다면 순차적으로 삭제한다는 것은 마지막 데이터부터 삭제할 경우 각 요소들의 재배치가 필요하지 않기 때문에 상당히 빠릅니다.
중간 데이터를 추가/삭제하는 경우에는 LinkedList가 ArrayList보다 빠르다.
- 중간 요소를 추가 또는 삭제하는 경우, LinkedList는 각 요소간의 연결만 변경해주면 되기 때문에 처리속도가 상당히 빠릅니다. 반면에 ArrayList는 각 요소들을 재배치하여 추가할 공간을 확보하거나 빈 공간을 채워야하기 때문에 처리속도가 느립니다.

큐의 구조는 한쪽에서는 삽입만 일어나고 한쪽에서는 삭제만 하는 자료구조 입니다. 즉, 먼저 들어간 것이 먼저 나오는 FIFO 구조입니다. (예시로는 줄서기, 프린터 출력 같은 것이 있습니다.)

즉, 큐는 항상 첫 번재 저장된 데이터를 삭제하므로, ArrayList와 같은 배열 기반의 자료구조를 사용하게 되면 빈공간을 채우기 위해서 데이터의 복사가 발생하므로 매우 비효율적입니다.

그래서 Queue는 ArrayList보다 데이터의 추가/삭제가 쉬운 LinkedList로 구현하는 것이 적합합니다.

reference