[Java] ArrayList VS LinkedList

“검색은 `ArrayList`가 빠르고, 삽입/삭제는 `LinkedList`가 빠르다.” ?

 

1. 공통점

• 선형 자료구조
• 순서가 있다.
• 인덱스 기반 접근이 가능하다. (List 인터페이스 구현)
• 중복 허용
• 동기화 X (Vector 제외)

 

하지만 내부 구조는 완전히 다르다고 한다.

 

 

2. 내부 구조 차이

📦 ArrayList

• 내부는 동적 배열 (Dynamic Array)
• 연속된 메모리 공간
• 인덱스로 바로 접근 가능

ArrayList<Integer> list = new ArrayList<>();
list.add(10);
list.get(0);  // O(1)

 

🔗 LinkedList

• 내부는 이중 연결 리스트 (Doubly Linked List)
• 노드가 서로 포인터로 연결
• 메모리 비연속

LinkedList<Integer> list = new LinkedList<>();
list.add(10);
list.get(0);  // O(n)

 

3. 시간 복잡도 비교

연산	ArrayList	LinkedList
조회(get)	O(1)	O(n)
맨 뒤 추가	O(1)*	O(1)
중간 삽입	O(n)	O(n)
중간 삭제	O(n)	O(n)

* `ArrayList`는 capacity 초과 시 재할당 발생 → `O(n)`

 

4. “LinkedList가 삽입/삭제가 빠르다” ?

이론적으론 그렇지만, 실제로는 꼭 그렇지만도 않은 듯 하다.

`LinkedList`가 빠르려면 이미 해당 노드의 위치를 알고 있어야 한다.

 

하지만 실제로는?

list.remove(5000);

• `LinkedList`는 5000번째까지 순회 → `O(n)`
• 그 다음 삭제 → `O(1)`

결과적으로 `O(n)`

 

즉, 대부분의 실무 케이스에서 `LinkedList`는 삽입/삭제도 느리다.

 

 

5. CPU 캐시 관점

ArrayList는 왜 실제로 빠를까?

• 연속된 메모리
• CPU cache friendly
• prefetch 최적화 가능

 

LinkedList는 왜 느릴까?

• 노드가 흩어져 있음
• pointer chasing 발생
• cache miss 증가

 

6. 성능 비교

샘플 코드

int size = 1_000_000;

List<Integer> arrayList = new ArrayList<>();
List<Integer> linkedList = new LinkedList<>();

long start = System.nanoTime();
for (int i = 0; i < size; i++) {
    arrayList.add(i);
}
long end = System.nanoTime();
System.out.println("ArrayList add: " + (end - start));

start = System.nanoTime();
for (int i = 0; i < size; i++) {
    linkedList.add(i);
}
end = System.nanoTime();
System.out.println("LinkedList add: " + (end - start));

실제로 돌려보면 대부분의 환경에서:

• `ArrayList`가 더 빠름
• 특히 순회(iteration)는 압도적으로 빠름

 

 

7. 메모리 사용량 비교

ArrayList

• 데이터만 저장
• capacity 여유 공간 있음

LinkedList

• 각 노드마다:
  • prev 포인터
  • next 포인터
  • 데이터

→ 메모리 오버헤드 훨씬 큼

 

대량 데이터에서는 `LinkedList`가 메모리를 훨씬 많이 사용함.

 

8. 언제 쓰는가?

ArrayList를 쓰는 경우 (대부분)

• 조회가 많을 때
• 순회가 많을 때
• 일반적인 CRUD
• 99%의 비즈니스 로직

→ 기본 선택은 `ArrayList`

LinkedList를 쓰는 경우

• Queue 구현
• Deque 구현
• 중간 노드를 이미 참조하고 있는 경우
• 빈번한 앞쪽 삽입/삭제

 

하지만… 요즘은 `LinkedList` 대신 `ArrayDeque`를 쓴다고 한다.

💡 ArrayDeque: 
ArrayDeque는 배열 기반의 Deque(Double-Ended Queue) 구현체로 앞/뒤 양쪽에서 삽입·삭제가 모두 빠른 자료구조이다.

 

9. 결론

• “삽입/삭제 많으면 `LinkedList`”를 사용하는 건 이론적
• 하지만 실제로 크게 차이 나지 않음
• 실무에서는 거의 `ArrayList`를 많이 사용함
• `LinkedList`는 메모리 + 캐시 측면에서 손해가 큼

 

10. 한 줄 요약

그냥 `ArrayList`를 써도 괜찮다고 한다. 정말 필요할 때만 `LinkedList`를 쓰면 될 것 같다. 그마저도 `ArrayDeque` 사용을 고려해보자.

 

다음에 코드 리팩토링 할 때 해당 사례가 있으면 추가해보도록 하겠음 총총