ArrayList vs LinkedList

구조적 차이

출처: https://javagoal.com/difference-between-arraylist-and-linkedlist/#google_vignette

 

ArrayList의 구조 (배열 기반)

 

• 연속된 메모리 블록에 데이터를 저장
• 인덱스로 직접 접근 가능 (O(1))
• 중간 삽입/삭제 시 데이터를 이동해야 해서 비용이 큼 (O(N))
  • 배열은 연속된 메모리 공간에 데이터를 저장하므로, 특정 위치에 데이터를 삽입하거나 삭제하려면 해당 위치 이후의 모든 데이터를 이동시켜야 합니다.

 

LinkedList의 구조 (이중 연결 리스트)

 

• 각 요소가 "노드"로 저장되며, 노드는 next와 prev 포인터를 가짐
• 메모리가 연속적이지 않음 (임의의 위치에 저장됨)
• 중간 삽입/삭제는 빠름 (O(1)) (포인터만 변경하면 됨)
• 검색(get(index)) 시 처음부터 탐색해야 해서 느림 (O(N))

 

시간복잡도 차이

연산	ArrayList	LinkedList
접근	O(1)	O(n)
처음 위치에 삽입/삭제	O(n) (데이터 이동)	O(1)
중간 위치에 삽입/삭제	O(n) (데이터 이동)	O(n) (중간까지 탐색 필요)
마지막 위치에 삽입/삭제	O(1) / O(n)	O(1)

 

💡ArrayList 에서 마지막 위치에 원소 삽입시 시간복잡도가 O(n)인 경우

ArrayList는 내부적으로 동적 배열 (Dynamic Array)을 사용하는데, 초기 크기를 지정하지 않으면 기본 크기(10)로 배열이 생성되며, 요소가 추가되면서 공간이 부족해지면 자동으로 크기가 증가하는 구조입니다. 이 때 크기가 증가할 때 배열의 크기가 꽉 차면 새로운 배열을 생성합니다. 이 과정에서 기존 배열의 모든 요소를 새로운 배열로 복사하고, 기존 배열을 버리고 새로운 배열을 사용하는 형식으로 진행이 됩니다. 따라서 ArrayList의 끝에 원소를 삽입할 경우 평균적으로는 O(1)의 시간복잡도가 소요되지만, 배열이 꽉 차면 위와 같은 이유로 O(N)이 소요될 수 있습니다.

 

---

대부분의 경우 ArrayList를 써야 되는 이유

자바 컬렉션 프레임워크 설계 및 구현에 큰 기여를한 조슈아 블로치 또한 linkedList를 쓰지 않는다고 했는데.. 자료구조 수업이나 강의를 들으며 삽입 / 삭제가 많으면 LinkedList를, 요소 접근이 많으면 ArrayList를 사용하면 된다고 배운 기억이 있을 것입니다.

출처: https://x.com/joshbloch/status/583813919019573248

 

하지만 실제 성능(실험 결과)에서는 ArrayList가 대부분 더 빠르고 LinkedList는 거의 사용되지 않는 것을 볼 수 있습니다. 그 이유에 대해서 알아보겠습니다. 

 

1️⃣ LinkedList의 삽입/삭제가 생각보다 느립니다.

 

• LinkedList는 삽입/삭제 시 노드 탐색(O(N))이 필요합니다.
• 노드가 많아질수록 탐색 시간이 길어져 성능이 급격히 떨어집니다.
• 노드 할당 시 객체 생성 비용이 큽니다. (new Node() 때문에)

2️⃣ LinkedList의 메모리 낭비

 

• LinkedList는 각 요소마다 이전/다음 노드를 저장하는 포인터(주소) 필요
  → 추가 메모리 사용 (배열에 비해서 데이터만 저장하는 것이아니라, 참조자 next, prev 때문에 ArrayList보다 2배 이상 큼).
• GC(Garbage Collection) 비용 증가
  → 연결 리스트는 노드 단위로 메모리를 할당하고 해제 하므로, 노드가 많아질수록 GC 작동 빈도 증가 → 비용 증가

 

3️⃣ ArrayList의 공간 지역성(Locality of Reference) 

CPU는 메모리보다 훨씬 빠른 속도로 데이터를 처리할 수 있지만, 메모리 접근은 상대적으로 느리기 때문에 CPU와 메모리 사이에 캐시(Cache)라는 고속 메모리를 사용합니다. 캐시 지역성은 이러한 캐시의 효율성을 극대화하는 데 중요한 역할을 합니다.

 

캐시 지역성 중 '공간성 지역성'은 프로그램이 메모리를 접근할 때, 그 주변 메모리도 곧 접근할 가능성이 높다는 원리를 의미합니다.

 

• ArrayList는 연속된 메모리 블록에 저장되므로 높은 공간 지역성을 보여줍니다.
• 반면, LinkedList는 노드가 메모리 여기저기에 흩어져 있어 캐시 효율이 낮습니다.

 

참고자료

캐시 지역성

Why Arrays have better cache locality than Linked list? - GeeksforGeeks