LinkedList가 각기 노드를 두고 주소 포인터를 링크하는 식으로 자료를 구성하는 이유는
ArrayList가 배열을 이용하여 요소를 저장함으로써 발생하는 단점을 극복하기 위해 고안되었기 때문이다.
| ArrayList | LinkedList | |
|---|---|---|
| 컬렉션 구성 | 배열을 이용 | 노드를 연결(linked) |
| 데이터 접근 시간 | 모든 데이터 상수 시간 접근 | 위치에 따라 이동시간 발생 |
| 삽입 / 삭제 시간 | 삽입 / 삭제 자체는 상수 시간 | |
| 삽입 / 삭제 시 데이터 이동이 필요한 경우, 추가시간 발생 | 삽입 / 삭제 자체는 상수 시간 | |
| 삽입 / 삭제 위치에 따라 그 위치까지 이동하는 시간 발생 | ||
| 리사이징 필요 | 공간이 부족할 경우 새로운 배열에 복사하는 추가 시간 발생 | - |
| 데이터 검색 | 최악의 경우 리스트에 있는 아이템 수 만큼 확인 | 최악의 경우 리스트에 있는 아이템 수 만큼 확인 |
ArrayList는 배열 공간(capacity)이 꽉 차거나, 요소 중간에 삽입을 행하려 할 때,
기존의 배열을 복사해서 요소를 뒤로 한칸씩 일일히 이동해야 하는 작업이 필요하다.
이런 부가적인 연산은 시스템의 성능 저하로 이어져 삽입/삭제가
빈번하게 발생하는 프로세스의 경우, 치명적일 수 있다.
그리고 자료들이 지속적으로 삭제되는 과정에서 ArrayList에서는 그 공간만큼 낭비되는 메모리가 많아지게 되고
또한 리사이징 처리에서 시간이 소모된다.
