리스트 - ArrayList vs LinkedList

이현빈·2025년 2월 24일

자료구조 & Java 컬렉션 프레임워크 공부

목록 보기

7/19

1. 데이터 접근 시간

ArrayList

시간복잡도는 $O(1)$

인덱스가 N인 데이터 주소 = 배열 시작 주소 + 데이터 타입의 크기 * N
: 배열의 시작 주소, 데이터 타입의 크기, 접근하려는 인덱스 값을 알면 접근하려는 데이터의 위치를 계산 가능

LinkedList

최악의 경우 시간복잡도는 $O(n)$
: 메모리상으로는 불연속적으로 위치한 데이터 노드들이 이전/다음 노드의 주소값을 가리키는 방식으로 연결되므로, 가장 시간이 오래 걸리는 경우에서는 처음부터 n번째 데이터까지 차례대로 탐색해야 원하는 데이터에 접근 가능

저장해야 하는 데이터의 개수가 많아질수록 접근 시간이 증가

2. 데이터 탐색 시간

ArrayList와 LinkedList 모두 최악의 경우에서의 시간복잡도는 $O(n)$
: 특정 데이터를 탐색할 시 항상 첫번째 요소부터 순차적으로 비교해 가면서 탐색해야 하기 때문

3. 데이터 추가/삭제 시간

cf) 데이터 탐색 시간을 제외한, 순수하게 데이터 추가/삭제 작업에 소요되는 시간만 고려

순차적으로 데이터 추가/삭제

cf) '순차적 삭제' : 마지막 데이터부터 역순으로 삭제

ArrayList

시간복잡도는 $O(1)$

마지막 데이터의 바로 다음에 새로운 데이터를 추가하거나, 마지막 데이터를 null로 변경
: 마지막 데이터를 삭제하는 작업 이외의 추가 작업이 불필요

LinkedList

시간복잡도는 $O(1)$

리스트의 마지막 노드와의 연결을 끊는 작업만 수행

중간 데이터 추가/삭제

ArrayList

최악의 경우 시간복잡도는 $O(n)$

데이터 추가/삭제를 수행하는 위치를 기준으로 그 이후의 요소들을 1칸씩 이동시키는 추가 작업이 요구됨

LinkedList

시간복잡도는 $O(1)$

추가/삭제할 노드의 앞뒤 노드 간 연결만 변경할 뿐, 별도의 추가 작업을 요구하지 않음

3. 메모리 사용

ArrayList

정적 할당
: 사용 이전에 크기를 미리 선언해야 하고, 한번 선언한 배열의 크기는 변경 불가

저장할 데이터의 개수가 많을수록 메모리 낭비 증가
: 다루고자 하는 데이터 개수가 거의 변하지 않을 때 주로 활용

LinkedList

동적 할당
: 사용 이전에 크기를 미리 확정지을 필요가 없고, 프로그램 실행 도중 저장된 데이터의 개수가 변동될 수 있음

저장할 데이터의 개수가 많을수록 배열보다 효율적으로 메모리 사용 가능
: 다루고자 하는 데이터 개수의 변경이 잦을 때 주로 활용