[JCF] ArrayList와 LinkedList의 차이

List인터페이스는 중복을 허용하면서 저장순서가 유지되는 컬렉션을 구현할 때 사용한다.
ArrayList와 LinkedList는 List인터페이스의 구현체이다. 이 둘의 차이는 어떤 것들이 있을까?

구조적인 차이

ArrayList :
내부적으로 Object 배열을 생성하여 인덱스 방식으로 데이터에 접근한다.

LinkedList :
리스트의 요소는 데이터와 다음 요소에 대한 참조를 가지고 있다. 이 요소를 노드 라고 한다. 다음 노드에 대한 참조를 계속 참조하여 데이터에 접근한다.
(참고 : 실제로 LinkedList 클래스는 낮은 접근성을 높이기 위해 DoublieLinkedList로 구현되어 있다.)

크기 변경에 대한 오버헤드

ArrayList :
배열은 크기를 정하여 크기 만큼의 공간을 할당하고 초기화를 한다. 따라서 공간이 부족하면 더 큰 배열을 만들어서 배열의 요소들을 복사한다. 기존에 존재하던 배열을 버리고 새로운 배열을 생성하고 요소를 복사하는 과정 때문에 크기 변경에 의한 오버헤드가 크다.

LinkedList :
새로운 노드를 만들어서 이전 노드의 참조가 새로 만든 노드를 가리키도록 한다. ArrayList와 달리 노드를 생성하여 이를 연결만 하기 때문에 크기 변경에 대한 오버헤드가 적다.

데이터 조회

ArrayList :
인덱스를 바로 접근하기 때문에 조회가 빠르다.

LinkedList :
순차적으로 다음 노드에 대한 참조를 반복하며 탐색하기 때문에 느리다.

데이터 삽입, 삭제

ArrayList :
배열로 구현되어있기 때문에 배열의 마지막에 데이터를 추가하는 것은 빠르다. 하지만 중간에 데이터를 추가하려면 데이터들을 한 칸씩 뒤로 밀어서 삽입을 해야 한다. 배열의 요소들을 재배치 해야 하기 때문에, 데이터를 중간에 추가하는 경우에는 느리다. (삭제는 그 반대의 과정이다.)

LinkedList :
삽입 과정은 삽입할 위치의 다음 노드를 참조하는 노드를 생성하고 이전 노드가 참조하도록 한다. 각 노드간의 연결만 변경하기 되기 때문에 중간에 데이터를 추가하더라도 빠르다. (삭제는 삭제할 노드의 이전 노드가 삭제할 노드의 다음 노드를 참조하도록 한다.)

그럼 언제 어떤 List를 사용해야 하는가?

ArrayList :
데이터를 리스트의 뒤에서부터 순차적으로 삭제하는 경우, 순차적으로 데이터를 초기화 하는 경우, List의 크기가 정적일 경우 사용하는 것이 좋다.

LinkedList :
중간에 데이터를 추가/삭제하는 경우, List의 크기가 동적일 경우 사용하는 것이 좋다.