자바 ArrayList와 LinkedList 차이는 자바 입문자도 꼭 한 번은 헷갈리는 주제입니다. 하지만 실전에서는 빅오 한 줄 암기보다 메모리 배치, 인덱스 접근, 순회 패턴, 앞뒤 삽입 여부를 먼저 봐야 더 잘 고를 수 있습니다.
이번 글에서는 `LinkedList`가 왜 이론 설명만큼 자주 이기지 않는지, `ArrayList`가 실제 앱 코드에서 왜 더 기본 선택지가 되는지, 그리고 큐나 스택처럼 앞뒤 삽입과 삭제가 중요할 때는 왜 `ArrayDeque`를 먼저 보게 되는지까지 쉬운 코드 예시로 정리하겠습니다.
한 줄 정리
ArrayList는 배열 기반이라 인덱스로 읽기 좋다LinkedList는 노드 연결 구조라 위치를 찾으려면 링크를 따라가야 한다- 일반적인 조회, 순회, 끝 추가는
ArrayList가 더 자주 유리하다 - 큐와 덱처럼 앞뒤 삽입과 삭제가 중요하면
LinkedList보다ArrayDeque를 먼저 본다
보통의 리스트는 ArrayList, 큐나 스택은 ArrayDeque, 정말 특별한 이유가 있을 때만 LinkedList라고 기억하면 실전에서 크게 틀리지 않습니다.
메모리 배치
`ArrayList`는 내부적으로 resizable array를 기반으로 움직입니다. 그래서 리스트 저장 공간이 한 줄로 이어진 칸처럼 느껴집니다.
반면 `LinkedList`는 doubly-linked list입니다. 각 원소가 노드가 되고, 각 노드는 앞뒤 노드를 가리키는 참조를 함께 들고 있습니다. 즉, 한 덩어리 배열 안에서 바로 꺼내는 구조가 아니라 링크를 따라 이동하는 구조에 가깝습니다.
ArrayList→ 한 줄로 놓인 칸을 인덱스로 바로 찾는 느낌LinkedList→ 여기저기 흩어진 노드를 링크 따라가며 찾는 느낌
이 차이 하나만 이해해도 왜 `ArrayList`는 인덱스 접근이 편하고, 왜 `LinkedList`는 순회 중 포인터를 계속 따라가야 하는지 감이 옵니다.
랜덤 접근
`ArrayList`는 `get(index)`에 강합니다. 배열 기반이기 때문에 원하는 위치를 바로 계산해서 접근할 수 있습니다. Oracle 문서도 `get`, `set`, `iterator` 등이 constant time이라고 설명합니다.
List<String> names = new ArrayList<>();
names.add("Kim");
names.add("Lee");
names.add("Park");
System.out.println(names.get(1)); // Lee반면 `LinkedList`는 `get(1)`처럼 보여도 내부적으로는 그 위치까지 이동해야 합니다. Oracle 문서도 index 기반 연산은 앞이나 뒤에서 더 가까운 쪽부터 순회한다고 설명합니다.
즉, `LinkedList`의 `get(i)`는 배열처럼 바로 찍고 가는 접근이 아닙니다. 중간 어딘가를 읽고 싶을 때마다 결국 링크를 따라 걸어가야 합니다.
for (int i = 0; i < list.size(); i++) {
process(list.get(i));
}이 패턴은 `ArrayList`에서는 자연스럽지만, `LinkedList`에서는 index 접근 비용 때문에 체감 성능이 빠르게 나빠질 수 있습니다.
삽입과 삭제
많이 외우는 문장은 `ArrayList`는 중간 삽입과 삭제가 느리고, `LinkedList`는 링크만 바꾸면 빨라서 유리하다는 것입니다. 이 말은 삽입하거나 삭제할 위치를 이미 손에 쥐고 있다면 어느 정도 맞습니다.
문제는 일반적인 앱 코드에서는 그 위치를 그냥 가지고 있는 경우가 드물다는 점입니다. `LinkedList`는 일단 그 위치까지 가야 하고, 새 노드도 만들고, 앞뒤 링크도 다시 연결해야 합니다.
ArrayList는 위치를 바로 찾지만 뒤 원소를 밀거나 당긴다LinkedList는 밀 필요는 적지만 그 위치까지 먼저 걸어가야 한다- 일반 앱 코드에서는 두 번째 비용이 생각보다 자주 더 크게 느껴진다
그래서 “LinkedList는 삽입이 빠르다”는 말을 그대로 믿고 기본 선택지로 가져가면 오히려 잘못 고를 가능성이 큽니다.
순회 성능
이론만 보면 둘 다 처음부터 끝까지 한 번 도는 것은 선형 시간입니다. 그런데 실제 체감은 꽤 다를 수 있습니다.
`ArrayList`는 저장 공간이 연속적이라 CPU가 다음 원소를 예측하고 가져오기 유리합니다. 반면 `LinkedList`는 노드가 메모리 여기저기에 흩어져 있을 수 있어서 다음 노드를 따라갈 때마다 덜 효율적으로 움직이기 쉽습니다.
이걸 보통 cache locality라고 설명합니다. 어렵게 들리면 그냥 `ArrayList`는 줄 서 있는 물건을 차례로 보는 느낌이고, `LinkedList`는 창고 여기저기에 흩어진 상자를 주소 따라 찾아가는 느낌이라고 이해하면 됩니다.
Oracle `ArrayList` 문서도 다른 연산의 constant factor가 `LinkedList`보다 낮다고 설명합니다. 실무에서 `ArrayList`가 자주 더 가볍게 느껴지는 이유를 이해할 때 이 문장이 꽤 중요합니다.
메모리 사용량
입문 때는 `LinkedList`가 뭔가 단순 연결이라 메모리를 덜 쓸 것처럼 느껴질 수 있습니다. 하지만 실제로는 각 원소가 값만 있는 것이 아니라 노드 객체와 앞뒤 참조를 함께 들기 때문에 오버헤드가 계속 붙습니다.
반면 `ArrayList`는 내부 배열의 여유 공간이 있을 수는 있어도, 원소마다 노드 객체를 따로 만들지는 않습니다. 대량 데이터를 일반적인 리스트로 들고 있을 때 `LinkedList`가 꼭 메모리 친화적이라고 볼 수 없는 이유가 여기 있습니다.
ArrayList가 맞는 경우
- 인덱스로 읽는 일이 있다
- 전체를 순회하는 일이 많다
- 끝에
add()하면서 리스트를 키운다 - 화면 표시 목록, 검색 결과, 설정 목록, 일반 비즈니스 데이터 목록처럼 쓴다
- 특별히 앞쪽 삽입과 삭제가 핵심이 아니다
List<Integer> scores = new ArrayList<>();
scores.add(90);
scores.add(85);
scores.add(100);
for (int score : scores) {
System.out.println(score);
}이런 코드는 `ArrayList`가 가장 기본적이고 읽기도 쉽습니다. 굳이 `LinkedList`를 고를 이유가 거의 없습니다.
LinkedList가 맞는 경우
그렇다고 `LinkedList`가 완전히 쓸모없다는 뜻은 아닙니다. 다만 이기는 장면이 좁습니다.
- 리스트의 맨 앞과 맨 뒤를 자주 넣고 뺀다
- 중간 위치를 iterator로 이미 잡아 둔 상태에서 삽입과 삭제가 매우 자주 일어난다
- 연결 관계를 끊고 잇는 모델이 문제의 핵심이다
하지만 첫 번째 상황, 즉 앞뒤 삽입과 삭제 위주라면 많은 경우 `LinkedList`보다 `ArrayDeque`가 더 좋은 선택입니다.
ArrayDeque를 먼저 보는 이유
많은 사람이 `LinkedList`를 떠올리는 순간은 사실 `List`라기보다 `Queue`, `Deque`, `Stack`처럼 쓰고 싶을 때입니다. BFS, 작업 대기열, 최근 작업 되돌리기 같은 구조가 대표적입니다.
이때는 `LinkedList`도 가능하지만, Oracle `ArrayDeque` 문서는 stack으로는 `Stack`보다 빠를 가능성이 높고 queue로는 `LinkedList`보다 빠를 가능성이 높다고 설명합니다.
Deque<Integer> queue = new ArrayDeque<>();
queue.addLast(1);
queue.addLast(2);
System.out.println(queue.removeFirst()); // 1실무 기준으로 줄이면 일반 목록은 `ArrayList`, 큐와 덱과 스택은 `ArrayDeque`, 특별한 연결 리스트 성질이 정말 필요할 때만 `LinkedList`입니다. 이 규칙이 더 실전적입니다.
자주 하는 오해
LinkedList는 중간 삽입이 무조건 빠르다 → 아니다. 그 위치까지 먼저 가야 한다면 이야기가 달라진다- 순회는 둘 다 O(n)이니 체감도 비슷하다 → 아니다. cache locality 때문에 실제 순회 성능은 꽤 다를 수 있다
- 앞에 넣고 빼기 많으면 무조건
LinkedList다 → 아니다. 많은 경우ArrayDeque가 더 잘 맞는다 LinkedList가 더 고급 자료구조라서 성능도 더 좋다 → 아니다. 앱 코드에서는 단순한 배열 기반 구조가 오히려 더 실용적인 경우가 많다
선택 기준
보통의 리스트
가장 먼저 `ArrayList`를 봅니다. 조회, 순회, 끝 추가가 자연스럽고, 대부분의 화면용 목록과 비즈니스용 목록은 여기서 충분합니다.
큐와 스택
`LinkedList`보다 `ArrayDeque`를 먼저 봅니다. 앞뒤 삽입과 삭제 중심 자료구조라면 이쪽이 더 실용적인 경우가 많습니다.
LinkedList를 고려할 때
이미 순회 중인 위치 근처에서 삽입과 삭제가 아주 잦고, 연결 구조의 장점이 실제로 드러나는지 먼저 확인합니다. 그런 근거가 없으면 `LinkedList`를 기본값으로 두지 않는 편이 낫습니다.
정리
`ArrayList`와 `LinkedList` 차이는 단순히 조회 대 삽입 한 줄로 외우면 실전에서 자주 어긋납니다. 진짜 중요한 것은 메모리 배치, 위치를 어떻게 찾는지, 순회가 많은지, 앞뒤 삽입이 핵심인지를 함께 보는 것입니다.
결론은 꽤 현실적입니다. 일반적인 리스트는 `ArrayList`, 큐나 스택은 `ArrayDeque`, `LinkedList`는 정말 이유가 있을 때만 쓴다고 생각하면 대부분의 애플리케이션 코드에서 좋은 출발점이 됩니다.
관련해서 자바 문자열 조립 선택 기준이 궁금하다면 자바 String, StringBuilder, StringBuffer 차이 글도 함께 보면 좋습니다. 정렬과 순서가 있는 맵 선택이 헷갈린다면 자바 HashMap과 TreeMap 차이 글도 이어서 읽어보면 도움이 됩니다.
공식 문서는 Oracle Java SE 21 ArrayList API, LinkedList API, ArrayDeque API를 참고했습니다.
