Java ArrayList vs LinkedList 완벽 비교

Java ArrayList vs LinkedList 완벽 비교

Java Collection을 공부하면 반드시 등장하는 단골 질문이 바로:

ArrayList vs LinkedList 차이

입니다.

면접에서도 정말 자주 나오고,
실무에서도 컬렉션 성능 문제와 연결됩니다.

초보 시절에는 보통 이렇게 외웁니다.

ArrayList
= 조회 빠름

LinkedList
= 삽입/삭제 빠름

 

하지만 실무에서는 이 설명만 믿으면 오히려 잘못된 선택을 하는 경우가 많습니다.

왜냐하면 실제 성능은:

• CPU Cache
• 메모리 구조
• 객체 포인터 비용
• GC 부담

까지 영향을 받기 때문입니다.

이번 글에서는:

• ArrayList 내부 구조
• LinkedList 내부 구조
• 시간복잡도 함정
• CPU Cache 영향
• 실무에서 뭐가 더 빠른가

까지 깊게 정리해보겠습니다.

---

1. ArrayList란?

ArrayList 는:

내부적으로 동적 배열(Dynamic Array) 기반 List

입니다.

즉:

배열(Array)

 

기반 자료구조.

---

2. ArrayList 내부 구조

실제로 내부는 거의 이런 느낌:

 

Object[] elementData;

 

즉:

객체 reference 배열

 

을 사용.

---

3. 메모리 구조

예:

 

List<String> list =
    new ArrayList<>();

 

메모리:

Array:
[0][1][2][3]

 

연속된 메모리 구조.

---

4. ArrayList 조회가 빠른 이유

예:

 

list.get(3);

 

가능한 이유:

배열 index 접근

 

가능하기 때문.

즉:

O(1)

 

접근 가능.

---

5. ArrayList 삽입 문제

중간 삽입:

 

list.add(1, value);

 

문제:

뒤 요소 전부 이동 필요

 

---

6. 메모리 이동 발생

예:

[A][B][C]

 

중간 삽입:

[A][X][B][C]

 

즉:

B,C 이동

 

필요.

---

7. 그래서 시간복잡도

 

작업	시간복잡도
조회(get)	O(1)
끝 삽입(add)	평균 O(1)
중간 삽입	O(N)
중간 삭제	O(N)

---

8. LinkedList란?

LinkedList 는:

노드(Node) 연결 기반 List

입니다.

---

9. LinkedList 내부 구조

노드 형태:

 

class Node {

    E item;

    Node next;
    Node prev;
}

 

즉:

이전/다음 노드 연결

 

구조.

---

10. 메모리 구조

[A] <-> [B] <-> [C]

 

형태.

---

11. LinkedList 조회 문제

예:

 

list.get(1000);

 

실제로는:

앞에서부터 순차 탐색

 

필요.

즉:

O(N)

 

---

12. LinkedList 삽입 장점

중간 삽입 시:

노드 연결만 변경

 

하면 됨.

즉 이론상:

O(1)

 

가능.

---

13. 그래서 흔히 배우는 비교

작업	ArrayList	LinkedList
조회	빠름	느림
삽입/삭제	느림	빠름

---

14. 그런데 실무에서는 이상한 현상 발생

실제로는:

ArrayList가 대부분 더 빠름

 

인 경우 매우 많음.

왜일까?

---

15. CPU Cache 때문

매우 중요합니다.

현대 CPU는:

연속 메모리 접근 매우 빠름

 

입니다.

---

16. ArrayList 장점

ArrayList는:

메모리 연속 저장

 

구조.

즉 CPU Cache 효율 매우 좋음.

---

17. LinkedList 문제

LinkedList는:

메모리 여기저기 흩어짐

 

가능.

즉:

포인터 따라 이동

 

필요.

---

18. Pointer Chasing 문제

CPU 입장에서는:

다음 노드 주소 찾아가기

 

반복.

즉:

• Cache Miss 증가
• 메모리 접근 비용 증가

---

19. 그래서 실제 성능

이론상:

LinkedList 삽입 O(1)

 

하지만 실제론:

삽입 위치 탐색 비용 O(N)

 

이 더 큼.

---

20. 예시

 

list.add(50000, value);

 

실제로는:

50000번째 노드까지 이동 필요

 

즉 느림.

---

21. ArrayList는 왜 실제로 빠를까?

배열 복사는:

CPU가 매우 잘 최적화

 

합니다.

심지어:

System.arraycopy()

 

같은 네이티브 최적화 사용.

---

22. LinkedList 메모리 오버헤드

노드마다:

prev
next
객체 헤더

 

추가 필요.

즉 메모리 사용량 큼.

---

23. ArrayList 메모리 효율

상대적으로:

배열만 유지

 

하므로 메모리 효율 좋음.

---

24. GC 관점에서도 차이

LinkedList는:

Node 객체 매우 많이 생성

 

됩니다.

즉:

• 객체 수 증가
• GC 부담 증가

가능.

---

25. ArrayList resize 동작

배열 꽉 차면:

더 큰 배열 생성
↓
기존 데이터 복사

 

수행.

---

26. 그래서 초기 크기 중요

실무 팁:

 

new ArrayList<>(10000);

 

미리 크기 지정 가능.

---

27. 왜 중요할까?

resize 반복 시:

배열 복사 비용 증가

 

가능.

---

28. LinkedList 장점이 진짜 발휘되는 경우

대표 사례:

• 중간 삽입 매우 많음
• Iterator 기반 순차 이동
• 양끝 삽입/삭제

---

29. Queue 용도로는?

LinkedList는:

 

Queue
Deque

 

구조로 사용 가능.

---

30. 하지만 현대 Java에서는?

실무 대부분:

ArrayDeque 추천

 

합니다.

LinkedList보다 더 빠른 경우 많음.

---

31. ArrayList 실무 사용 비율

압도적으로 많음.

실무 체감:

거의 대부분 ArrayList

 

사용.

---

32. LinkedList 거의 안 쓰는 이유

실제 서버 성능에서는:

• CPU Cache
• 메모리 locality
• 객체 오버헤드

영향이 매우 큼.

즉:

이론 시간복잡도만 보면 안 됨

 

---

33. Random Access 차이

ArrayList:

Random Access 매우 강함

 

LinkedList:

Random Access 매우 약함

 

---

34. Iterator 성능 차이

순차 탐색은:

둘 다 괜찮음

 

하지만 일반적으로 ArrayList 우세 많음.

---

35. 멀티스레드 환경

둘 다:

Thread-safe 아님

 

입니다.

필요 시:

 

Collections.synchronizedList()

 

또는 concurrent 컬렉션 사용.

---

36. 시간복잡도 함정

면접식 정답:

작업	ArrayList	LinkedList
중간 삽입	O(N)	O(1)

하지만 실제론:

탐색 비용 포함하면 LinkedList도 느림

 

---

37. 실무 선택 기준

매우 중요.

---

ArrayList 추천 상황

대부분 상황

 

---

LinkedList 고려 가능 상황

양끝 삽입/삭제 매우 빈번

 

---

38. Java 공식 문서 느낌도 비슷

실제로도:

ArrayList 사용 우선

 

경향 매우 강함.

---

39. 실무에서 자주 하는 실수

1) LinkedList가 삽입 빠르다고 무조건 선택

실제론 대부분 느림.

---

2) 초기 용량 지정 안 함

resize 반복 비용 가능.

---

3) 시간복잡도만 믿음

CPU Cache 영향 매우 큼.

---

40. 핵심 흐름 요약

ArrayList
= 배열 기반
= 조회 매우 빠름

LinkedList
= 노드 연결 기반
= 이론상 삽입 유리

 

---

41. 가장 중요한 핵심 한 줄

실무에서는 대부분
LinkedList보다 ArrayList가 더 빠른 경우가 많다

 

입니다.

---

42. 정리

ArrayList vs LinkedList는 단순 자료구조 비교가 아닙니다.

실제로는:

• CPU Cache
• 메모리 구조
• GC 부담
• 객체 오버헤드
• 실제 런타임 성능

전체와 연결되는 중요한 성능 주제입니다.

특히 실무에서는:

• ArrayList 내부 배열 구조
• LinkedList Node 구조
• Cache Locality
• resize 비용

까지 이해하는 것이 매우 중요합니다.

다음 글에서는:

HashMap 내부 구조

를 hashCode(), bucket, resize, TreeNode, JDK8 최적화까지 포함해서 깊게 정리해보겠습니다.