Java

[Java] LinkedList vs. ArrayList : 메모리와 캐시로 이해하기

👀 들어가기 전에

Java에는 배열이 있고, List라는 컬렉션 추상화가 있다.

그리고 List의 대표 구현체로 LinkedList와 ArrayList가 따로 존재한다.

흔히

ArrayList는 조회가 빠르고, LinkedList는 삽입/삭제가 빠르다

라고 말하지만, 실무에서는 꼭 이게 정답이지 않는 경우까지 생겨 깊이있게 파보았다.

이 글에서는 JVM 메모리 모델 + CPU 캐시 + 객체 구조까지 포함해서 왜 대부분의 상황에서 ArrayList를 기본값으로 사용하는지 정리해본다.

👀 본론

배열 : 진짜 Random Access가 가능한 이유

배열은 연속 메모리에 놓인다.

그래서 인덱스 접근은 단순 산술로 끝나게 된다.

addr(arr[i]) = base + i * elementSize

이렇게 산술로 끝나다 보니 O(1) 시간대로 끊기게 되는 것이다.

그렇다면 이 연산을 CPU 캐시 관점에서 보면 어떨까?

CPU는 메모리를 읽을 때 보통 64바이트 단위 (캐시 라인)로 가져온다.

int[]는 원소 하나가 4바이트이기에 캐시 라인 하나에 16개의 원소가 들어간다.

즉, 배열을 순회할 때는

접근 패턴이 예측 가능하고
CPU prefetcher가 다음 데이터를 미리 땡겨오고
캐시 hit 확률이 매우 높을 수밖에 없다.

그래서 같은 O(n)순회라도 배열인 경우 체감 성능이 좋은 것이다.

ArrayList : 동적배열

ArrayList는 내부적으로 Object[] elemetData를 가진다.

즉 배열을 감싼 래퍼 클래스 형태이다.

그렇다면 add() 메소드는 왜 평균 O(1)일까?

ArrayList의 add(e)는 보통 O(1)이다.

배열이 꽉 차면 "새 배열 생성 + 복사"가 발생하게 되며 O(n)이 되지만 확장 정책 때문에 전체적으로 amortized O(1)이 성립한다.

풀어서 이해해보면

n개를 넣는 동안 복사는 가끔만 발생하고
복사의 총량이 선형에 머물기 때문에
평균 비용은 상수로 수렴한다.

하지만, 결국 리사이징은 System.arraycopy()를 호출하게 된다.

이건 C레벨에서 빠르게 복사하지만 결국 확실히 비싼작업이다.

그래서 대략적인 크기를 아는 리스트라면 무조건 초기 용량을 잡아서 선언하는게 더 빠를 것이라 판단하게 되었다.

LinkedList : 이론 vs. 실무

Java의 LinkedList는 이중연결 리스트다.

노드가 다음과 같이 생겼다.

이 노드들을 활용해 구현한 동적 배열이 아래의 LinkedList인 것이다.

흔히 이론적으로, "LinkedList는 삽입과 삭제가 빠르다!"라는 이야기가 많다.

구현체 코드를 보면 볼수록 과연 진짜 그런가? 에 대한 궁금증이 생기기 시작했다.

LinkedList는 정말 삽입/삭제가 빠를까?

중간 삽입/삭제가 빠르려면 결국에는 조건이 붙는다.

삭제할 노드의 참조를 이미 알고 있을 때만 O(1)이다.

하지만 대부분의 코드에서는 list.remove(x) 처럼 값으로 지우거나, list.get(i) 후 처리하거나 contains()같은 탐색을 한다.

이 순간 이미 탐색 비용 O(n)이 포함되게 되는 것이다.

이를 CPU 캐시 관점에서 보면 어떻게 될까?

Node 객체들은 힙 영역에 흩어져 있다.

따라서 순회할 때 매번

포인터를 따라가며
서로 멀리 떨어진 메모리 위치를 읽고
캐시 미스가 발생한다.

이걸 pointer chasing이라고 한다.

즉, LinkedList는 O(n)의 순회이지만 배열 기반 O(n) 순회보다 실제 실행시간은 더 느리다고 체감이 되는 것이다.

그렇다면 Java에서의 int[] 와 ArrayList<Integer>는??

여기서 또 다른 궁금증이 생겼다. 그럼 int[] 배열과는 어떻게 다를까?

'배열"이라고 하더라도 primitive 배열과 wrapper리스트는 완전히 다르다.

int[] : 연속 메모리에 값 자체가 저장된다.
ArrayList<Integer> : Object[] 안에 Integer 객체 참조(주소값)가 저장된다.

즉, ArrayList<Integer>는 사실상 배열 + 객체 조합이다.

이런 구조는 결국 캐시 효율이 떨어지고, GC의 부담이 커지고 메모리의 오버헤드 증가라는 결과를 낸다.

그래서 성능이 만약 민감하다면, primitive 배열 혹은 primitive 컬렉션 같은 선택을 하게 되는 것이다.

ListIterator : LinkedList의 단점 보완

리스트를 공부하게 되면 얼마 안지나서 마주하게 되는 친구이다.

LinkedList의 중간에 어느 한 지점을 계속 가리키고 싶을때 쓰게 되는 녀석이 ListIterator 이다.

ListIterator<String> cursor = list.listIterator(4);

이 코드는 4번째 위치에 커서를 두는 것과 같다.

그림으로 표현하면 아래와 같다.

이전 노드를 삭제할 때는 아래와 같이 작동하게 된다.

if (cursor.hasPrevious()) {
    cursor.previous(); // D
    cursor.remove();   // D 삭제
}

다음 노드를 삭제할 때도 동일하다.

if (cursor.hasNext()) {
    cursor.next();   // E
    cursor.remove(); // E 삭제
}

즉, ListIterator로 하여금 중간 위치를 지속적으로 가리킬 수 있게 만들어서 이동 + 삭제까지를 O(1)의 시간복잡도 내에 처리 가능하도록 한다.

하지만 조금만 생각해보면 커서 기반으로 뭔가 편집을 하게 되는 특수한 경우가 아니면 쓸 일이 잘 없겠다는 생각이 들었다.

👀 마무리하며

이번 글에서는 ArrayList와 LinkedList의 내부 구현과 동작 방식의 관점에서 조금 더 깊이있게 살펴보았다.

그동안 관습적으로 ArrayList를 선택해왔던 이유가 "그냥 많이쓰니까"가 아니라 연속 메모리 구조, 캐시 친화성, 예측 가능한 성능 특성 때문이라는 점을 구조적으로 이해할 수 있었다. 자료구조를 선택한다는 것은 결국 어떤 접근 패턴과 어떤 비용을 감수할 것인지를 선택하는 일이라는 것도 다시금 느끼게 되었다.

'Java' 카테고리의 다른 글

다시, 기초부터 : 왜 이렇게 동작하는가 (0)	2026.01.01

Contents

당신이 좋아할만한 콘텐츠

다시, 기초부터 : 왜 이렇게 동작하는가 2026.01.01

새소식