Java 컬렉션 성능에 대해(ArrayList, LinkedList, 차이)

Java 컬렉션 성능에 대해

자바에서 가장 많이 사용하는 자료구조 중 하나가 리스트(List)입니다. 리스트는 데이터를 순서대로 저장하고 필요에 따라 접근할 수 있도록 돕는 핵심적인 컬렉션 인터페이스의 구현체입니다. 특히 ArrayList와 LinkedList는 리스트 인터페이스의 대표적인 두 구현체로, 표면적으로는 기능이 비슷해 보이지만 내부 구조와 성능 특성에는 큰 차이가 있습니다. 개발자는 상황에 따라 적합한 리스트를 선택해야 하며, 그렇지 않으면 성능 저하나 불필요한 자원 낭비가 발생할 수 있습니다. 이번 글에서는 ArrayList와 LinkedList를 중심으로 내부 구조, 성능 차이, 그리고 활용 사례를 구체적으로 살펴보겠습니다.

ArrayList의 구조와 성능 특성

ArrayList는 이름에서 알 수 있듯이 내부적으로 동적 배열(dynamic array)을 기반으로 구현되어 있습니다. 배열을 기본 구조로 사용하기 때문에 인덱스를 통한 임의 접근(Random Access)에 뛰어난 성능을 보입니다. 특정 인덱스에 위치한 요소를 조회할 때는 상수 시간 O(1)에 접근할 수 있어, 조회 중심의 시나리오에서 매우 유리합니다.

반면 배열 기반 구조 특성상 중간에 요소를 삽입하거나 삭제하는 경우에는 뒤 요소들을 이동시키는 비용이 발생합니다. 즉, 중간 삽입/삭제는 최악 O(n)</strong) 시간이 걸립니다. 단, 리스트의 끝에 추가하는 연산은 내부 용량(capacity)이 충분하다면 평균적으로 O(1)에 가깝습니다. 용량이 가득 찬 경우에는 더 큰 배열을 새로 할당하고 기존 데이터를 복사하는 리사이즈 과정이 발생하지만, 일반적으로 증설은 지수적으로(capacity를 보통 1.5배~2배) 증가하므로 전체적으로는 암ortized O(1)에 가까운 성능을 보입니다.

import java.util.ArrayList;

public class ArrayListExample {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            list.add(i);          // 끝에 삽입은 빠름 (평균 O(1))
        }
        list.add(5, 100);         // 중간 삽입은 요소 이동 → O(n)
        System.out.println(list);
    }
}

장점 요약

• 빠른 인덱스 접근 (O(1))
• 순차적인 추가/순회가 빠름
• 메모리 사용이 상대적으로 효율적(추가 포인터 없음)

단점 요약

• 중간 삽입/삭제 시 요소 이동 비용으로 O(n)
• 용량 초과 시 배열 재할당+복사 비용 발생

결론적으로 ArrayList는 조회가 빈번하거나 데이터가 주로 순차적으로 추가되는 경우에 적합합니다.

LinkedList의 구조와 성능 특성

LinkedList는 이중 연결 리스트(doubly linked list)를 기반으로 구현됩니다. 각 노드는 데이터와 함께 이전/다음 노드에 대한 참조를 보유합니다. 이 구조 덕분에 참조를 이미 알고 있다면 노드 연결만 바꾸면 되므로 특정 위치에서의 삽입/삭제 자체의 링크 조작은 O(1)에 가깝습니다.

그러나 인덱스를 통한 접근은 배열처럼 즉시 접근이 불가능합니다. 특정 인덱스의 노드를 찾기 위해서는 머리(head) 또는 꼬리(tail)에서부터 순차적으로 이동해야 하며, 인덱스 접근은 O(n)</strong)입니다. 즉, LinkedList의 강점은 중간 삽입/삭제이지만, 그 위치까지 이동하는 탐색 비용을 고려해야 합니다.

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 0; i < 10; i++) {
            list.add(i);
        }
        list.add(5, 100);   // 중간 삽입 자체는 링크 변경으로 유리
        list.remove(2);     // 중간 삭제도 유리 (탐색 비용 제외)
        System.out.println(list);
    }
}

장점 요약

• 중간 삽입/삭제의 링크 변경은 O(1)
• 크기 변경이 자유롭고 재할당 불필요

단점 요약

• 인덱스 기반 접근은 O(n) (탐색 필요)
• 각 노드가 포인터를 추가로 저장 → 메모리 오버헤드
• 메모리 상에서 노드가 흩어져 → 캐시 지역성(cache locality) 낮아 실제 실행 속도에서 불리

결론적으로 LinkedList는 삽입/삭제가 빈번하고 임의 접근이 상대적으로 적은 경우에 적합합니다.

성능 비교와 활용 사례

1) 조회 성능 (get, set)

• ArrayList: O(1) → 인덱스로 즉시 접근
• LinkedList: O(n) → 순차 탐색 필요

2) 삽입/삭제 성능 (add, remove)

• ArrayList: 중간 삽입/삭제는 요소 이동으로 O(n), 꼬리 추가는 평균 O(1)
• LinkedList: 노드 참조를 이미 알고 있다면 링크 변경 O(1), 단 인덱스로 위치를 찾는 과정은 O(n)

3) 메모리 사용량

• ArrayList: 데이터만 저장 → 메모리 효율적
• LinkedList: 각 노드에 이전/다음 포인터 저장 → 추가 메모리 사용

4) CPU 캐시와 실제 체감 성능

• ArrayList: 연속 메모리 → 캐시 적중률 높아 순회/조회가 매우 빠른 경향
• LinkedList: 불연속 메모리 → 캐시 미스 증가로 이론 대비 체감 성능이 떨어질 수 있음

5) 활용 사례

• ArrayList: 검색/정렬/조회 빈도가 높은 목록, 예: DB 조회 결과 리스트, 로그 축적 후 일괄 처리
• LinkedList: 큐(Queue)/덱(Deque)처럼 삽입/삭제가 잦은 구조, 예: 작업 대기열, 프로듀서-컨슈머 버퍼

실제 벤치마크를 수행하면, 많은 경우 ArrayList가 전반적으로 더 빠른 경향을 보입니다. 특히 순회와 임의 접근에서 캐시 지역성의 이점을 크게 누리기 때문입니다. 반면 LinkedList는 삽입/삭제가 극단적으로 많은 특수한 워크로드에서만 이점을 보이는 경우가 많습니다. 또한 JDK의 LinkedList는 Deque 구현체로서 앞/뒤에 원소를 추가/제거하는 연산(addFirst, addLast, removeFirst, removeLast)을 자주 수행하는 시나리오에서 의미가 큽니다.

결론: 상황에 맞는 리스트 선택하기

ArrayList와 LinkedList는 동일한 List 인터페이스를 구현하지만 내부 구조가 다른 만큼 성능 특성도 확연히 다릅니다. 요약하면 다음과 같습니다.

• ArrayList → 조회/순회 빈번, 꼬리 추가 위주, 메모리 효율 중시 시 기본 선택
• LinkedList → 중간 삽입/삭제가 매우 빈번하고, 덱 연산(앞/뒤 추가/삭제)이 핵심일 때 고려

교과서적 정의만으로 “삽입/삭제는 LinkedList가 유리”라고 단정하기보다, 실제 프로그램의 데이터 크기, 접근 패턴, 캐시 효과, 메모리 제약을 함께 고려해야 합니다. 대부분의 일반적인 애플리케이션에서는 ArrayList가 더 좋은 체감 성능을 제공하므로 기본값으로 선택하고, 특정 요구가 있을 때 LinkedList를 선택하는 전략이 현실적입니다.