개발을 하다 보면 ArrayList를 쓸지, LinkedList를 쓸지 고민할 때가 많다. 특히 데이터를 추가할 때(add), 성능이나 메모리 측면에서 어떤 차이가 있는지 정확하게 이해하고 있으면, 더 좋은 성능을 만들 수 있을 것 같아서 정리해본다.

 

1. ArrayList 

  • 내부적으로 배열(Array) 기반으로 데이터를 저장하는 컬렉션이다.
  • 데이터가 추가되면서 배열 크기를 초과하면, 더 큰 배열을 새로 만들고 기존 데이터를 복사한다.
val arrayList = ArrayList<Int>()
arrayList.add(10) // 배열에 10 추가

 

특징 : 

  • 인덱스를 통한 접근 ( get(index) ) 이 매우 빠름 → O(1)
  • 중간 삽입/삭제는 느림 → O(N) (요소 이동 발생)

 

2. LinkedList

  • 노드(Node) 들이 포인터로 연결된 구조이다.
  • 각각의 노드는 데이터(data)와 다음 노드(next)를 가리키는 포인터를 가지고 있다.
val linkedList = LinkedList<Int>()
linkedList.add(10) // 노드로 10 추가

 

특징 : 

  • 앞/뒤 삽입/삭제가 매우 빠름 → O(1)
  • 인덱스를 통한 접근은 느림 O(N) (앞에서붜 순회 필요)

 

 

3. add 시 시간 복잡도 비교

상황 ArrayList LinkedList
맨 뒤에 추가( add(E e) ) 평균 O(1)
(가끔 O(N) 리사이즈)
항상 O(1)
중간에 추가 ( add(index, E e) ) O(N) (뒤 요소 이동) O(N) (위치 탐색 필요)

 

ArrayList의 경우

  • 맨 뒤에 추가할 때는 평균적으로 O(1) 이지만, 배열 용량이 부족하면 O(N) 리사이즈가 발생한다.
  • 중간에 추가할 경우, 추가 위치 이후의 모든 요소를 한 칸씩 밀어야 하므로 O(N)이다.

LinkedList의 경우

  • 맨 뒤에 추가는 항상 O(1) (tail 포인터 사용).
  • 중간에 추가할 경우, 목표 인덱스까지 노드를 순차적으로 탐색해야 하므로 O(N)이다.
  • 탐색 이후 삽입 자체는 포인터지만 연결하면 되기 때문에 삽입 동작은 O(1)이다.

 

 

4. 메모리 사용량 차이

항목  ArrayList LinkedList
메모리 구조 연속된 배열 분산된 노드 + 포인터 연결
한 요소 저장 시 추가 메모리 없음 (배열 포인터만) next/prev 포인터 2개 추가 필요

 

ArrayList의 경우

  • 요소 크기 * 배열 크기 만큼 메모리 사용.
  • 공간이 부족할 것을 대비해 capacity (버퍼 공간)을 여유롭게 잡기도 한다.
  • 배열이라서 캐시 친화적(cache friendly) 이다.

LinkedList의 경우

  • 각 노드마다 데이터 + next 포인터 + prev 포인터 (더블 링크드 리스트 기준)를 저장한다
  • 포인터 오버헤드 때문에 메모리 사용량이 훨씬 많음.
  • 메모리가 연속적이지 않아 캐시 미스(cache miss)가 자주 발생한다.

정리하면, 메모리 효율은 ArrayList가 압도적으로 좋다.

 

 

 

5. 상황별 추천

상황 추천 자료구조
빠른 랜덤 접근이 필요할 때 ArrayList
삽입/삭제가 매우 빈번할 때 LinkedList
메모리 효율을 중요시할 때 ArrayList
요소 수를 자주 바꿀 때 (초대량 삭제 등) LinkedList (특수 상황)

 

대부분의 일반적인 경우 (조회 + 추가)는 ArrayList가 훨씬 효율적이다. LinkedList는 특정 상황(삽입/삭제가 매우 빈번한 경우) 에만 신중하게 써야 한다.

 

 

+ Recent posts