ArrayList vs LinkedList 언제 어떤 걸 써야 할까?

자바에서 가장 많이 쓰는 자료구조 둘을 꼽으라면 단연 ArrayList와 LinkedList일 겁니다. 근데 이 둘의 차이를 제대로 이해하고 있는 개발자는 생각보다 많지 않더라고요. 제가 공부하면서 깨달은 것들을 정리해볼게요.

메모리 구조부터 이해해야 한다

먼저 둘의 가장 근본적인 차이부터 봅시다.

 

ArrayList는 내부적으로 배열을 사용합니다. 배열은 메모리 상에서 연속된 공간에 데이터를 저장하죠. 메모리 주소가 차례대로 이어져 있다는 뜻입니다.

 

LinkedList는 노드(Node)라는 객체들을 체인처럼 연결해서 사용합니다. 각 노드는 실제 데이터와 다음 노드의 참조(주소)를 가지고 있어요. 그래서 메모리 상에서는 떨어져 있을 수 있지만, 참조로 연결되어 논리적으로는 이어진 거죠.

 

이 차이가 성능에 직결됩니다.

읽기(조회) 성능: ArrayList 완승

어떤 데이터를 찾아야 할 때를 생각해봅시다.

 

ArrayList에서 특정 인덱스의 데이터를 찾는 건 정말 쉽습니다. 첫 번째 원소의 메모리 주소에 인덱스 번호를 더하기만 하면 원하는 데이터를 한 번에 찾을 수 있어요. 이를 O(1) 시간복잡도라고 부릅니다.

ArrayList<String> list = new ArrayList<>();
list.add("데이터0");
list.add("데이터1");
list.add("데이터2");

// 어떤 인덱스의 값이든 바로 찾을 수 있음
String value = list.get(1000000);  // 매우 빠름

 

LinkedList는 어떨까요? 특정 위치의 데이터를 찾으려면 처음부터 차례대로 노드를 따라가야 합니다. 9999번째 데이터를 찾으려면 처음부터 노드를 9999번 타고 가야 한다는 뜻이에요. 이는 O(n) 시간복잡도입니다. 데이터가 많을수록 엄청 느려지죠.

LinkedList<String> list = new LinkedList<>();
// ... 100만 개의 데이터 추가

// 50만 번째 데이터를 찾으려면?
String value = list.get(500000);  // 처음부터 50만번 노드를 따라가야 함 - 매우 느림

 

개발자들이 실제로 테스트해본 결과를 보면, ArrayList의 조회 속도는 LinkedList의 수백 배에서 수천 배 빠릅니다.

중간에 삽입/삭제: LinkedList가 살아난다

이제 반대 상황입니다. 리스트 중간에 새로운 데이터를 삽입해야 한다고 생각해봅시다.

ArrayList는 배열 기반이라 문제가 생깁니다. 100개의 데이터가 있는데 50번 위치에 새로운 데이터를 삽입하려면? 50번 이후의 모든 데이터를 한 칸씩 뒤로 밀어야 해요. 그래서 최악의 경우 모든 데이터를 옮겨야 합니다. O(n) 시간복잡도이죠.

ArrayList<String> list = new ArrayList<>();
// ... 100만 개의 데이터 추가

// 중간에 삽입
list.add(500000, "새로운데이터");  
// 500000번 이후의 모든 데이터를 옮겨야 함 - 매우 느림

 

LinkedList는 다릅니다. 삽입 위치의 노드를 찾고 그 노드의 참조만 바꿔주면 됩니다. 나머지 데이터는 건드릴 필요가 없어요. 이론상으로는 O(1) 시간복잡도입니다.

LinkedList<String> list = new LinkedList<>();
// ... 100만 개의 데이터 추가

// 중간에 삽입
list.add(500000, "새로운데이터");  
// 참조만 변경 - 빠름

 

삭제도 원리는 동일합니다. 삭제 대상 노드의 이전 노드가 다음 노드를 가리키도록 바꾸기만 하면 끝이죠.

그런데 정말 그럴까? 상수항의 위력

여기서 중요한 포인트가 있습니다. 이론상 시간복잡도는 좋아 보이는데, 실제 성능은 어떨까요?

 

LinkedList가 중간 삽입에서 이론상 O(1)이라고 해도, 삽입 위치를 찾아가는 데 여전히 O(n)이 필요합니다. 그리고 노드를 생성하고 메모리를 할당하는 과정도 생각보다 비싼 작업이에요. 빅-오 표기법에서는 생략되는 상수항이 실제로는 매우 크다는 뜻입니다.

 

실제 테스트 결과를 보면

• LinkedList에 1억 개 요소를 끝에 추가: ArrayList와 비교하면 훨씬 더 오래 걸립니다. 각각 노드 객체를 생성해야 하는 오버헤드가 있기 때문이죠.
• 배열 중간에서 100개 삭제: LinkedList가 이론상으로는 유리해 보이지만, 실제로는 ArrayList가 더 빠를 수 있습니다. 이유는 ArrayList의 O(n) 작업이 단순하고 CPU 캐시 효율이 좋기 때문입니다.

ArrayList의 동적 크기 확장 비법

그런데 ArrayList가 계속 커질 수만은 없잖아요. 처음에는 10개 크기로 시작합니다. 그리고 데이터가 차면?

ArrayList는 현재 크기의 1.5배로 새로운 배열을 만듭니다. 그 다음 기존 데이터를 모두 복사하죠. 이 과정을 "grow"라고 합니다.

// ArrayList 초기 생성
ArrayList<String> list = new ArrayList<>();  // 크기: 10

// 10개까지는 추가 비용 없음
for (int i = 0; i < 10; i++) {
    list.add("데이터" + i);  // O(1)
}

// 11번째 추가할 때 - grow 발생
list.add("데이터10");  // 크기: 15로 확장, 모든 데이터 복사 - O(n)

// 15개까지 다시 추가 가능
// 16번째에 다시 grow - 크기: 22로 확장

 

평균적으로는 이 오버헤드가 상쇄돼서 추가 연산이 O(1)에 가까워진다는 게 핵심입니다.

CPU 캐시 효율이라는 숨은 승자

여기서 한 가지 더 중요한 게 있습니다. ArrayList는 메모리가 연속되어 있잖아요. 이건 CPU 캐시 관점에서 매우 좋다는 뜻입니다.

 

CPU는 한 번에 메모리를 하나씩 읽지 않고, 근처 메모리 영역을 함께 캐시해서 읽습니다(캐시 라인). ArrayList처럼 연속된 메모리라면 다음 데이터가 이미 캐시에 있을 가능성이 높아요.

 

LinkedList는 다릅니다. 각 노드가 메모리 상에 흩어져 있으니까 계속 새로운 메모리를 접근해야 하고, 캐시 미스가 자주 발생하죠. 이건 실제 성능에 큰 영향을 미칩니다.

메모리 사용량도 무시할 수 없다

LinkedList는 각 노드마다 다음 노드의 참조(포인터)를 저장해야 합니다. 자바의 경우 64비트 환경에서 참조 하나가 8바이트죠. 데이터가 String 객체라면, 참조까지 포함해서 추가 메모리가 꽤 필요합니다.

 

ArrayList는 순수하게 데이터만 저장하므로 메모리가 훨씬 효율적이에요.

그럼 LinkedList는 언제 써?

이렇게 보니 LinkedList가 별로인 것처럼 느껴질 수도 있지만, 그렇지 않습니다.

 

LinkedList가 진짜 빛나는 순간

1. 큐(Queue) 또는 스택(Stack) 구현: 양쪽 끝에서만 추가/제거한다면 LinkedList의 O(1) 성능이 진정한 가치를 발합니다.

// 큐로 사용할 때
LinkedList<Integer> queue = new LinkedList<>();
queue.addLast(1);    // O(1) - 끝에 추가
queue.removeFirst(); // O(1) - 처음에서 제거

2. 정말 자주 중간 삽입/삭제가 일어나는 경우: 조회는 거의 안 하고, 순차적으로 처리하면서 자주 삽입/삭제한다면 고려할 수 있습니다. 하지만 이런 경우는 실무에서 드문 편입니다.
3. Iterator로 순회하면서 삭제: removeFirst(), removeLast() 같은 메서드로 양쪽 끝에서 삭제하는 게 빠릅니다.

결론: 기본은 ArrayList

구분	ArrayList	LinkedList
조회	⭐⭐⭐⭐⭐	⭐
끝에 추가	⭐⭐⭐⭐⭐	⭐⭐⭐⭐⭐
중간 삽입/삭제	⭐⭐	⭐⭐⭐
메모리 효율	⭐⭐⭐⭐⭐	⭐⭐⭐
캐시 효율	⭐⭐⭐⭐⭐	⭐⭐
초기화 속도	⭐⭐⭐⭐	⭐⭐⭐⭐⭐

 

기본 원칙

• 90% 이상의 경우 ArrayList를 사용하세요. 조회가 많든 추가가 많든, 현대의 CPU와 메모리 구조상 ArrayList가 실제로 더 빠른 경우가 대부분입니다.
• 양쪽 끝에서만 추가/제거하는 경우 (Queue, Stack): LinkedList를 고려해보세요. addFirst(), removeLast() 같은 메서드를 적극 활용할 수 있다면 진정한 O(1) 성능을 얻을 수 있습니다.
• 정말 이상한 요구사항 (예: 중간에서 계속 삭제): 그럼에도 LinkedList보다는 다른 해결책을 먼저 생각해보세요. 알고리즘 문제라면 LinkedList, 실무라면 정책 변경이 답일 가능성이 높습니다.

마지막 팁: 초기 크기 지정하기

ArrayList를 사용한다면 데이터 개수를 대략 알 때는 초기 크기를 지정하는 게 좋습니다.

// 나쁜 예: 크기 모를 때 계속 grow됨
ArrayList<Integer> list = new ArrayList<>();

// 좋은 예: 초기 크기 지정하면 grow 없음
ArrayList<Integer> list = new ArrayList<>(10000);

 

이렇게 하면 중간에 배열을 재할당하는 오버헤드를 완전히 없앨 수 있어요.

 

자료구조를 선택할 때는 평균적인 성능만 봐서는 안 되고, 실제 사용 패턴과 메모리/캐시 특성까지 함께 고려해야 합니다. ArrayList의 "B급" 삽입/삭제 성능이 LinkedList의 "A급" 성능보다 실제로 더 빠를 수 있다는 걸 이해하는 게 중요하답니다.

 

이런 세부 사항을 놓치고 면접에서 "LinkedList는 중간 삽입이 빠르니까 써야 한다"고만 얘기하면, 실무 경험이 없는 것처럼 보이니까 조심하세요!