ArrayList vs LinkedList 특징 비교

LinkedList가 각기 노드를 두고 주소 포인터를 링크하는 식으로 자료를 구성하는 이유는

ArrayList가 배열을 이용하여 요소를 저장함으로써 발생하는 단점을 극복하기 위해 고안되었기 때문이다.

ArrayList LinkedList
컬렉션 구성 배열을 이용 노드를 연결(linked)
데이터 접근 시간 모든 데이터 상수 시간 접근 위치에 따라 이동시간 발생
삽입 / 삭제 시간 삽입 / 삭제 자체는 상수 시간
삽입 / 삭제 시 데이터 이동이 필요한 경우, 추가시간 발생 삽입 / 삭제 자체는 상수 시간
삽입 / 삭제 위치에 따라 그 위치까지 이동하는 시간 발생
리사이징 필요 공간이 부족할 경우 새로운 배열에 복사하는 추가 시간 발생 -
데이터 검색 최악의 경우 리스트에 있는 아이템 수 만큼 확인 최악의 경우 리스트에 있는 아이템 수 만큼 확인

ArrayList의 문제점

ArrayList는 배열 공간(capacity)이 꽉 차거나, 요소 중간에 삽입을 행하려 할 때,

기존의 배열을 복사해서 요소를 뒤로 한칸씩 일일히 이동해야 하는 작업이 필요하다.

이런 부가적인 연산은 시스템의 성능 저하로 이어져 삽입/삭제가

빈번하게 발생하는 프로세스의 경우, 치명적일 수 있다.

그리고 자료들이 지속적으로 삭제되는 과정에서 ArrayList에서는 그 공간만큼 낭비되는 메모리가 많아지게 되고

또한 리사이징 처리에서 시간이 소모된다.

Untitled