Java/Java이론

Java ArrayList와 LinkedList의 차이점 및 성능 비교

P_eli 2024. 10. 15. 18:22
728x90
반응형

Java에서 ArrayList와 LinkedList는 모두 List 인터페이스를 구현한 클래스이지만, 내부 구조와 성능에서 차이가 있습니다. 이 두 클래스의 차이점을 이해하고, 상황에 맞게 적절히 선택하는 것이 중요한데요, 이번 포스트에서는 ArrayList와 LinkedList의 차이점과 성능 비교를 설명하고, 각각의 사용 예제를 알아보겠습니다.

1. ArrayList vs LinkedList의 차이점

1.1 내부 구조

  • ArrayList: 내부적으로 **동적 배열(Dynamic Array)**을 사용합니다. 배열은 고정된 크기이지만, ArrayList는 크기를 동적으로 조정하면서 요소를 추가할 수 있습니다. 배열 기반이므로 인덱스를 이용한 요소 접근이 빠릅니다.
  • LinkedList: 내부적으로 **이중 연결 리스트(Doubly Linked List)**를 사용합니다. 각 노드는 이전 노드와 다음 노드를 참조합니다. 요소를 추가하거나 제거할 때 노드 포인터만 수정하면 되기 때문에 삽입, 삭제가 빠른 장점이 있습니다.

1.2 주요 차이점

  • 요소 접근 시간:
    • ArrayList는 인덱스 기반으로 O(1) 시간 복잡도를 가지므로 매우 빠르게 접근할 수 있습니다.
    • LinkedList는 인덱스를 이용해 요소에 접근할 때 O(n)의 시간이 걸리며, 리스트의 중간이나 끝 부분에 접근할수록 시간이 오래 걸립니다.
  • 삽입/삭제 시간:
    • ArrayList는 중간에 삽입 또는 삭제를 할 경우 요소들을 이동해야 하기 때문에 O(n)의 시간이 걸립니다.
    • LinkedList는 포인터만 수정하면 되므로 O(1)로 빠르게 삽입/삭제가 가능합니다. 다만, 해당 위치를 찾는 데는 O(n)이 걸릴 수 있습니다.
  • 메모리 사용:
    • ArrayList는 배열이기 때문에 상대적으로 메모리 사용이 효율적입니다. 다만, 크기 변경이 필요할 때는 새 배열을 할당하고 복사하는 비용이 발생할 수 있습니다.
    • LinkedList는 각 노드가 데이터 외에 이전 노드와 다음 노드를 참조하는 포인터를 포함하고 있기 때문에 더 많은 메모리를 사용합니다.

2. 성능 비교

2.1 데이터 추가 성능

  • ArrayList:
    • 끝에 요소를 추가할 때는 O(1)의 시간 복잡도를 가집니다. 하지만 배열의 크기가 부족할 경우, 새로운 배열을 할당하고 모든 요소를 복사해야 하므로 최악의 경우 O(n)이 걸릴 수 있습니다.
  • LinkedList:
    • 리스트의 처음이나 끝에 요소를 추가하는 것은 O(1)입니다. 하지만 중간에 요소를 추가할 때는 해당 위치를 찾아야 하므로 O(n)이 걸릴 수 있습니다.

2.2 데이터 삭제 성능

  • ArrayList:
    • 삭제 시에도 중간 요소를 제거하면 뒤에 있는 요소들을 한 칸씩 당겨야 하므로 O(n)의 시간이 걸립니다.
  • LinkedList:
    • 삭제할 노드의 포인터만 수정하면 되기 때문에, 노드를 찾는 시간이 걸리지만, 삭제 자체는 O(1)입니다.

2.3 탐색 성능

  • ArrayList:
    • 배열 기반이므로 인덱스를 이용해 빠르게 탐색이 가능하며, 탐색 시간은 O(1)입니다.
  • LinkedList:
    • 인덱스를 통한 탐색은 처음부터 노드를 하나씩 따라가야 하므로 O(n)의 시간이 걸립니다.

3. 언제 ArrayList와 LinkedList를 사용할까?

  • ArrayList를 사용할 때:
    • 요소에 자주 접근하고, 읽기 작업이 많은 경우.
    • 요소를 추가하거나 삭제하는 작업이 주로 리스트의 끝에서 이루어지는 경우.
  • LinkedList를 사용할 때:
    • 리스트의 중간에서 자주 삽입 또는 삭제가 발생하는 경우.
    • 요소의 접근 빈도가 낮고, 삽입/삭제 작업이 중요한 경우.

4. 예제 코드

4.1 ArrayList 예제

import java.util.ArrayList;

public class ArrayListExample {
    public static void main(String[] args) {
        ArrayList<String> arrayList = new ArrayList<>();

        // 요소 추가
        arrayList.add("Java");
        arrayList.add("Python");
        arrayList.add("C++");

        // 요소 접근
        System.out.println("첫 번째 요소: " + arrayList.get(0));

        // 요소 제거
        arrayList.remove(1); // Python 제거

        // 리스트 출력
        System.out.println("ArrayList: " + arrayList);
    }
}

 

4.2 LinkedList 예제

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>();

        // 요소 추가
        linkedList.add("Java");
        linkedList.add("Python");
        linkedList.add("C++");

        // 요소 접근
        System.out.println("첫 번째 요소: " + linkedList.get(0));

        // 요소 제거
        linkedList.remove(1); // Python 제거

        // 리스트 출력
        System.out.println("LinkedList: " + linkedList);
    }
}

5. 결론

  • ArrayList는 인덱스 기반의 빠른 접근이 필요한 경우 유리하며, 주로 읽기 작업이 많거나 끝에서 추가/삭제가 자주 발생하는 상황에서 적합합니다.
  • LinkedList는 삽입과 삭제가 빈번한 상황, 특히 리스트의 중간에서 이러한 작업이 자주 발생하는 경우에 적합합니다.

상황에 따라 올바른 자료구조를 선택하면 더 효율적인 프로그램을 작성할 수 있습니다.

728x90
반응형