개발을 하다 보면 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는 특정 상황(삽입/삭제가 매우 빈번한 경우) 에만 신중하게 써야 한다.
'Back-End' 카테고리의 다른 글
기능은 됐는데 성능이 안 나오는 코드의 특징 5가지 (0) | 2025.05.09 |
---|---|
백엔드 개발자도 알아야 하는 브라우저 캐시의 (1) | 2025.04.09 |
FastAPI? (0) | 2024.08.12 |