Java: ArrayList vs LinkedList

ArrayList vs LinkedList: 차이점 및 성능 비교

arraylist vs linkedlist

자바 컬렉션 프레임워크는 다양한 데이터 구조를 제공하며, 그 중 ArrayList와 LinkedList는 List 인터페이스를 구현한 대표적인 클래스들입니다. 이 글에서는 ArrayList와 LinkedList의 차이점, 장단점, 그리고 성능 비교를 다루겠습니다.

List 인터페이스의 구현체

List 인터페이스를 구현한 대표적인 클래스는 다음과 같습니다:

• ArrayList
• LinkedList
• Vector
• Stack

이 중에서 ArrayList와 LinkedList의 차이점을 중점적으로 살펴보겠습니다.

ArrayList란?

ArrayList는 배열을 기반으로 한 리스트로, 중복을 허용하고 순서를 유지하며 인덱스로 원소들을 관리합니다. 배열과 유사하지만, 배열의 크기가 고정된 것과 달리 ArrayList는 동적으로 크기를 조정할 수 있습니다.

// Java ArrayList 예시
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(1);
        arrayList.add(2);
        arrayList.add(3);
        
        for (int value : arrayList) {
            System.out.println(value); // 출력: 1 2 3
        }
    }
}

 

ArrayList의 특징 및 내부 동작

• 동적 크기 조정: 요소를 추가할 때 배열의 용량이 부족하면 더 큰 배열을 생성하고 기존 배열의 요소를 복사합니다.
• Random Access: 인덱스를 통한 빠른 접근이 가능하여 탐색에 유리합니다.

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // 용량 확인 및 조정
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

장점

1. Random Access에 강함: 인덱스를 통해 O(1) 시간에 요소를 접근할 수 있습니다.
2. Cache 효율성: 연속된 메모리 블럭이므로 캐시 히트율이 높습니다.

단점

1. 중간 삽입/삭제가 비효율적: 요소들을 이동시켜야 하므로 O(N) 시간이 소요됩니다.
2. 메모리 사용: 크기 조정 시 새로운 배열을 생성하고 기존 배열을 복사하는 작업이 필요합니다.

LinkedList란?

LinkedList는 노드들이 포인터로 연결된 자료 구조입니다. 각 노드는 데이터와 다음 노드를 가리키는 포인터를 포함합니다.

// Java LinkedList 예시
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        LinkedList<Integer> linkedList = new LinkedList<>();
        linkedList.add(1);
        linkedList.add(2);
        linkedList.add(3);
        
        for (int value : linkedList) {
            System.out.println(value); // 출력: 1 2 3
        }
    }
}

LinkedList의 특징 및 내부 동작

• 노드 기반 구조: 각 노드는 데이터와 다음 노드를 가리키는 포인터를 가집니다.
• 양방향 연결: 양방향으로 연결되어 있어 앞뒤로 탐색이 가능합니다.

장점

1. 삽입/삭제가 효율적: 포인터만 변경하면 되므로 O(1) 시간이 소요됩니다.
2. 유연한 크기: 필요에 따라 동적으로 크기를 조정할 수 있습니다.

단점

1. Random Access가 비효율적: 요소에 접근하려면 처음부터 차례대로 탐색해야 하므로 O(N) 시간이 소요됩니다.
2. Cache 효율성 낮음: 불연속 메모리 블럭이므로 캐시 히트율이 낮습니다.

ArrayList vs LinkedList 성능 비교

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

public class ListPerformanceTest {
    public static void main(String[] args) {
        List<Integer> arrayList = new ArrayList<>(2000000);
        List<Integer> linkedList = new LinkedList<>();

        System.out.println("= 순차적으로 추가하기 =");
        System.out.println("ArrayList : " + addSequentially(arrayList));
        System.out.println("LinkedList : " + addSequentially(linkedList));

        System.out.println("= 중간에 추가하기 =");
        System.out.println("ArrayList : " + addInMiddle(arrayList));
        System.out.println("LinkedList : " + addInMiddle(linkedList));

        System.out.println("= 중간에서 삭제하기 =");
        System.out.println("ArrayList : " + removeInMiddle(arrayList));
        System.out.println("LinkedList : " + removeInMiddle(linkedList));

        System.out.println("= 순차적으로 삭제하기 =");
        System.out.println("ArrayList : " + removeSequentially(arrayList));
        System.out.println("LinkedList : " + removeSequentially(linkedList));
    }

    public static long addSequentially(List<Integer> list) {
        long start = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            list.add(i);
        }
        return System.currentTimeMillis() - start;
    }

    public static long addInMiddle(List<Integer> list) {
        long start = System.currentTimeMillis();
        for (int i = 0; i < 10000; i++) {
            list.add(list.size() / 2, i);
        }
        return System.currentTimeMillis() - start;
    }

    public static long removeSequentially(List<Integer> list) {
        long start = System.currentTimeMillis();
        for (int i = list.size() - 1; i >= 0; i--) {
            list.remove(i);
        }
        return System.currentTimeMillis() - start;
    }

    public static long removeInMiddle(List<Integer> list) {
        long start = System.currentTimeMillis();
        for (int i = 0; i < 10000; i++) {
            list.remove(list.size() / 2);
        }
        return System.currentTimeMillis() - start;
    }
}

성능 결과

= 순차적으로 추가하기 =
ArrayList : 126ms
LinkedList : 171ms

= 중간에 추가하기 =
ArrayList : 1695ms
LinkedList : 10ms

= 중간에서 삭제하기 =
ArrayList : 1303ms
LinkedList : 122ms

= 순차적으로 삭제하기 =
ArrayList : 8ms
LinkedList : 23ms

성능 차이 분석

1. 순차적으로 추가하기: ArrayList가 LinkedList보다 빠릅니다. ArrayList는 배열 끝에 요소를 추가하는 데 최적화되어 있습니다.
2. 중간에 추가하기: LinkedList가 훨씬 빠릅니다. ArrayList는 중간에 요소를 추가할 때 모든 요소를 이동시켜야 합니다.
3. 중간에서 삭제하기: LinkedList가 더 빠릅니다. ArrayList는 중간 요소를 삭제할 때 모든 요소를 이동시켜야 합니다.
4. 순차적으로 삭제하기: ArrayList가 더 빠릅니다. LinkedList는 각 요소를 찾아가며 삭제해야 하기 때문입니다.

결론

• ArrayList: 탐색이 빠르고, 순차적인 추가/삭제가 효율적입니다. 그러나 중간 삽입/삭제가 빈번하면 성능이 떨어집니다.
• LinkedList: 중간 삽입/삭제가 빠르고, 메모리 효율성이 좋습니다. 그러나 탐색 속도가 느리고, 순차적 접근에서 성능이 떨어집니다.

적용 시나리오:

• ArrayList: 데이터의 크기가 변하지 않거나, 순차적 추가/삭제가 많은 경우.
• LinkedList: 중간 삽입/삭제가 빈번하거나, 요소의 크기가 자주 변하는 경우.

이 글을 통해 ArrayList와 LinkedList의 특성을 이해하고, 상황에 맞는 자료 구조를 선택하는 데 도움이 되길 바랍니다.