[JAVA] List성능 비교와 최적화

Java에서 ArrayList와 LinkedList는 가장 널리 사용되는 리스트 구현체입니다. 하지만 각 리스트의 동작 원리와 성능 특성에 따라 적합한 사용 사례와 선택 기준이 달라집니다.

1. ArrayList vs LinkedList 성능 비교

ArrayList와 LinkedList의 동작 원리

• ArrayList는 내부적으로 동적 배열(Dynamic Array)을 사용하며, 인덱스를 기반으로 빠르게 접근이 가능합니다. 하지만 크기를 초과하는 요소를 추가할 때 배열을 재할당해야 하므로 성능 저하가 발생할 수 있습니다.
• LinkedList는 노드(Node) 간 연결로 구성된 데이터 구조로, 삽입과 삭제가 특정 위치에서 빠르게 이루어집니다. 하지만 인덱스를 기반으로 한 접근 속도가 느립니다.

성능 비교: 검색, 삽입, 삭제

• 검색: ArrayList는 O(1), LinkedList는 O(n)
• 삽입 및 삭제: LinkedList는 O(1) (중간 삽입 시), ArrayList는 O(n)
• 메모리 사용량: LinkedList는 각 노드가 추가 메모리(포인터)를 사용하므로 더 많은 메모리를 소비합니다.

성능 비교 예제

아래 코드는 대량의 데이터에서 두 리스트의 삽입 및 검색 성능을 비교합니다.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class PerformanceTest {
    public static void main(String[] args) {
        final int dataSize = 100_000;

        // ArrayList 테스트
        List<String> arrayList = new ArrayList<>();
        long start = System.currentTimeMillis();
        for (int i = 0; i < dataSize; i++) {
            arrayList.add("데이터" + i);
        }
        long end = System.currentTimeMillis();
        System.out.println("ArrayList 삽입 시간: " + (end - start) + "ms");

        start = System.currentTimeMillis();
        arrayList.get(dataSize / 2);
        end = System.currentTimeMillis();
        System.out.println("ArrayList 검색 시간: " + (end - start) + "ms");

        // LinkedList 테스트
        List<String> linkedList = new LinkedList<>();
        start = System.currentTimeMillis();
        for (int i = 0; i < dataSize; i++) {
            linkedList.add("데이터" + i);
        }
        end = System.currentTimeMillis();
        System.out.println("LinkedList 삽입 시간: " + (end - start) + "ms");

        start = System.currentTimeMillis();
        linkedList.get(dataSize / 2);
        end = System.currentTimeMillis();
        System.out.println("LinkedList 검색 시간: " + (end - start) + "ms");
    }
}

출력 예시

 

ArrayList 삽입 시간: 15ms
ArrayList 검색 시간: 0ms
LinkedList 삽입 시간: 30ms
LinkedList 검색 시간: 10ms

반응형

2. 데이터 크기에 따른 구현체 선택 기준

소규모 데이터

소규모 데이터의 경우, ArrayList가 대부분의 상황에서 적합합니다. 메모리 사용량이 적고 검색 성능이 뛰어나기 때문입니다.

대규모 데이터

대규모 데이터에서는 작업 특성에 따라 적절한 리스트를 선택해야 합니다.

• 읽기 및 검색이 많을 때: ArrayList 추천
• 삽입과 삭제가 빈번할 때: LinkedList 추천

선택 기준 요약

• 데이터가 자주 추가/삭제되는 경우: LinkedList
• 데이터가 자주 검색/읽기되는 경우: ArrayList
• 메모리가 중요한 경우: ArrayList

삽입 위치에 따른 성능 확인 예제

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class InsertTest {
    public static void main(String[] args) {
        final int dataSize = 10_000;

        // ArrayList 중간 삽입
        List<String> arrayList = new ArrayList<>();
        long start = System.currentTimeMillis();
        for (int i = 0; i < dataSize; i++) {
            arrayList.add(arrayList.size() / 2, "중간 데이터" + i);
        }
        long end = System.currentTimeMillis();
        System.out.println("ArrayList 중간 삽입 시간: " + (end - start) + "ms");

        // LinkedList 중간 삽입
        List<String> linkedList = new LinkedList<>();
        start = System.currentTimeMillis();
        for (int i = 0; i < dataSize; i++) {
            linkedList.add(linkedList.size() / 2, "중간 데이터" + i);
        }
        end = System.currentTimeMillis();
        System.out.println("LinkedList 중간 삽입 시간: " + (end - start) + "ms");
    }
}

출력 예시

 

ArrayList 중간 삽입 시간: 250ms
LinkedList 중간 삽입 시간: 10ms

3. 효율적인 메모리 관리 방법

ArrayList의 초기 용량 설정

ArrayList는 기본 용량이 10으로 설정되어 있으며, 용량 초과 시 크기를 1.5배로 늘립니다. 데이터 크기가 예상된다면 초기 용량을 지정하여 재할당 비용을 줄일 수 있습니다.

List<String> list = new ArrayList<>(1000); // 초기 용량 설정

LinkedList의 메모리 관리

LinkedList는 각 노드가 추가 메모리를 사용하므로, 메모리 사용량이 크며 적은 데이터를 다룰 때 비효율적입니다. 가능하면 작은 데이터를 자주 읽는 경우는 피하는 것이 좋습니다.

Stream과 병렬 처리 활용

대량의 데이터를 처리할 때, Stream API와 병렬 처리를 통해 성능을 최적화할 수 있습니다.

import java.util.ArrayList;
import java.util.List;

public class StreamTest {
    public static void main(String[] args) {
        List<Integer> numbers = new ArrayList<>();
        for (int i = 0; i < 1_000_000; i++) {
            numbers.add(i);
        }

        // 병렬 스트림
        long start = System.currentTimeMillis();
        long sum = numbers.parallelStream().mapToLong(Integer::longValue).sum();
        long end = System.currentTimeMillis();

        System.out.println("병렬 스트림 합계: " + sum);
        System.out.println("병렬 스트림 처리 시간: " + (end - start) + "ms");
    }
}

출력 예시

 

병렬 스트림 합계: 499999500000
병렬 스트림 처리 시간: 20ms

참고 사이트

Java 공식 문서: https://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html
Java Stream API: https://docs.oracle.com/javase/8/docs/api/java/util/stream/Stream.html