[Java] ArrayList vs LinkedList (추가/삭제는 Linked, 조회는 Array)

1. ArrayList와 LinkedList의 차이

ArrayList와 LinkedList는 Java에서 제공하는 두 가지 주요 List 구현체로, 각각의 구조와 사용 목적이 다르다.

 

ArrayList

- 구조 : 내부적으로 동적 배열(Dynamic Array)을 사용한다.

- 특징 :

  1) 데이터 접근이 빠르다. (Index를 기반으로 바로 접근 가능)

  2) 데이터 추가/ 삭제 시 배열의 크기를 변경하거나 요소를 이동하여야 하므로 속도가 느리다.

- 적합한 경우: 데이터 접근이 빈번한 경우에 적합하다.

 

LinkedList

- 구조 : 노드(Node)와 포인터로 이루어진 연결 리스트 구조이다.

            각 노드는 데이터와 다음 노드를 가리키는 포인터를 가진다.

- 특징 :

   1) 데이터 추가/ 삭제가 빠르다. (포인터만 변경)

   2) 데이터 접근이 느리다.(순차적으로 탐색 필요)

- 적합한 경우 : 데이터 삽입/ 삭제가 빈번한 경우에 적합하다. 

 

---

2. 코드 및 성능 비교

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

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

        // 데이터 추가 시간 비교
        System.out.println("=== 데이터 추가 성능 비교 ===");

        // ArrayList 끝에 추가
        long startTime = System.nanoTime();
        for (int i = 0; i < 100000; i++) {
            arrayList.add(i);
        }
        long arrayListEndAddTime = System.nanoTime() - startTime;
        System.out.println("ArrayList 끝에 추가: " + arrayListEndAddTime + "ns");

        // LinkedList 끝에 추가
        startTime = System.nanoTime();
        for (int i = 0; i < 100000; i++) {
            linkedList.add(i);
        }
        long linkedListEndAddTime = System.nanoTime() - startTime;
        System.out.println("LinkedList 끝에 추가: " + linkedListEndAddTime + "ns");

        // 끝에 추가 성능 비교
        printPerformanceComparison("끝에 추가", arrayListEndAddTime, linkedListEndAddTime);

        // 중간에 데이터 추가 시간 비교
        System.out.println("\n=== 중간에 데이터 추가 성능 비교 ===");

        // ArrayList 중간에 추가
        startTime = System.nanoTime();
        for (int i = 0; i < 10000; i++) {
            arrayList.add(500, i);
        }
        long arrayListMiddleAddTime = System.nanoTime() - startTime;
        System.out.println("ArrayList 중간에 추가: " + arrayListMiddleAddTime + "ns");

        // LinkedList 중간에 추가
        startTime = System.nanoTime();
        for (int i = 0; i < 10000; i++) {
            linkedList.add(500, i);
        }
        long linkedListMiddleAddTime = System.nanoTime() - startTime;
        System.out.println("LinkedList 중간에 추가: " + linkedListMiddleAddTime + "ns");

        // 중간 추가 성능 비교
        printPerformanceComparison("중간에 추가", arrayListMiddleAddTime, linkedListMiddleAddTime);

        // 데이터 접근 시간 비교
        System.out.println("\n=== 데이터 접근 성능 비교 ===");

        // ArrayList 접근
        startTime = System.nanoTime();
        for (int i = 0; i < 10000; i++) {
            arrayList.get(i);
        }
        long arrayListAccessTime = System.nanoTime() - startTime;
        System.out.println("ArrayList 데이터 접근: " + arrayListAccessTime + "ns");

        // LinkedList 접근
        startTime = System.nanoTime();
        for (int i = 0; i < 10000; i++) {
            linkedList.get(i);
        }
        long linkedListAccessTime = System.nanoTime() - startTime;
        System.out.println("LinkedList 데이터 접근: " + linkedListAccessTime + "ns");

        // 접근 성능 비교
        printPerformanceComparison("데이터 접근", arrayListAccessTime, linkedListAccessTime);

        // 데이터 삭제 시간 비교
        System.out.println("\n=== 데이터 삭제 성능 비교 ===");

        // ArrayList 중간 데이터 삭제
        startTime = System.nanoTime();
        for (int i = 0; i < 10000; i++) {
            arrayList.remove(500);
        }
        long arrayListRemoveTime = System.nanoTime() - startTime;
        System.out.println("ArrayList 중간 데이터 삭제: " + arrayListRemoveTime + "ns");

        // LinkedList 중간 데이터 삭제
        startTime = System.nanoTime();
        for (int i = 0; i < 10000; i++) {
            linkedList.remove(500);
        }
        long linkedListRemoveTime = System.nanoTime() - startTime;
        System.out.println("LinkedList 중간 데이터 삭제: " + linkedListRemoveTime + "ns");

        // 삭제 성능 비교
        printPerformanceComparison("중간 데이터 삭제", arrayListRemoveTime, linkedListRemoveTime);
    }

    private static void printPerformanceComparison(String operation, long arrayListTime, long linkedListTime) {
        double ratio;
        String fasterList;

        if (arrayListTime < linkedListTime) {
            ratio = ((double) linkedListTime / arrayListTime - 1) * 100;
            fasterList = "ArrayList";
        } else {
            ratio = ((double) arrayListTime / linkedListTime - 1) * 100;
            fasterList = "LinkedList";
        }

        System.out.printf("→ %s에서 %s가 약 %.2f%% 더 빠름%n",
                operation, fasterList, ratio);
    }
}

 

1. 리스트 생성

List<Integer> arrayList = new ArrayList<>();
List<Integer> linkedList = new LinkedList<>();

- ArrayList와 LinkedList의 객체를 생성.

두 리스트는 동일한 List 인터페이스를 구현하지만 내부 구현 방식이 다르다.

 

2. 데이터 추가 성능 비교

 2.1 끝에 데이터 추가

//ArrayList 끝에 추가
long startTime = System.nanoTime();
for (int i = 0; i < 100000; i++) {
   arrayList.add(i);
}
long arrayListEndAddTime = System.nanoTime() - startTime;

//LinkedList 끝에 추가. 
startTime = System.nanoTime();
for (int i = 0; i < 100000; i++) {
    linkedList.add(i);
}
long linkedListEndAddTime = System.nanoTime() - startTime;

• ArrayList.add(i):

• 배열의 끝에 데이터를 추가. 배열의 크기가 꽉 차면 새 배열을 생성하고 기존 데이터를 복사.

• 평균적으로 O(1), 최악의 경우 O(n).

• LinkedList.add(i):

• 끝에 노드를 추가. 새 노드를 생성하고 마지막 노드와 연결.

• 항상 O(1).

 

---

  2.2 중간에 데이터 추가

// ArrayList 중간에 추가
startTime = System.nanoTime();
for (int i = 0; i < 10000; i++) {
    arrayList.add(500, i);
}
long arrayListMiddleAddTime = System.nanoTime() - startTime;

// LinkedList 중간에 추가
startTime = System.nanoTime();
for (int i = 0; i < 10000; i++) {
    linkedList.add(500, i);
}
long linkedListMiddleAddTime = System.nanoTime() - startTime;

• ArrayList.add(index, element):

   -  배열의 중간에 데이터를 삽입하면 뒤의 데이터를 모두 이동해야 함.

   -  O(n).

• LinkedList.add(index, element):

   - 중간 노드를 탐색한 후 새 노드를 삽입. 탐색 O(n), 삽입 O(1).

   -  총 O(n).

 

---

  2.3. 데이터 접근 성능 비교

// ArrayList 데이터 접근
startTime = System.nanoTime();
for (int i = 0; i < 10000; i++) {
    arrayList.get(i);
}
long arrayListAccessTime = System.nanoTime() - startTime;

// LinkedList 데이터 접근
startTime = System.nanoTime();
for (int i = 0; i < 10000; i++) {
    linkedList.get(i);
}
long linkedListAccessTime = System.nanoTime() - startTime;

• ArrayList.get(index):

   • 배열의 인덱스에 바로 접근 가능. O(1).

• LinkedList.get(index):

   • 첫 노드부터 순차적으로 탐색. O(n).

 

---

  2.4 데이터 삭제 성능 비교

// ArrayList 중간 데이터 삭제
startTime = System.nanoTime();
for (int i = 0; i < 10000; i++) {
    arrayList.remove(500);
}
long arrayListRemoveTime = System.nanoTime() - startTime;

// LinkedList 중간 데이터 삭제
startTime = System.nanoTime();
for (int i = 0; i < 10000; i++) {
    linkedList.remove(500);
}
long linkedListRemoveTime = System.nanoTime() - startTime;

• ArrayList.remove(index):

  • 중간 데이터를 삭제하면 뒤의 데이터를 이동해야 함. O(n).

• LinkedList.remove(index):

  • 중간 노드를 탐색한 후 포인터를 조정. 탐색 O(n), 삭제 O(1).

• 총 O(n).

 

---

  2.5 성능 비교 결과 출력

private static void printPerformanceComparison(String operation, long arrayListTime, long linkedListTime) {
    double ratio;
    String fasterList;

    if (arrayListTime < linkedListTime) {
        ratio = ((double) linkedListTime / arrayListTime - 1) * 100;
        fasterList = "ArrayList";
    } else {
        ratio = ((double) arrayListTime / linkedListTime - 1) * 100;
        fasterList = "LinkedList";
    }

    System.out.printf("→ %s에서 %s가 약 %.2f%% 더 빠름%n",
            operation, fasterList, ratio);
}

• 계산 과정:

   • ratio: 빠른 리스트가 느린 리스트보다 얼마나 더 빠른지 백분율로 계산.

   • 결과를 형식화하여 출력.

• 예시 출력:

→ 끝에 추가에서 LinkedList가 약 50.00% 더 빠름

---

결론
1. 끝에 추가: LinkedList가 효율적.
2. 중간에 추가: LinkedList가 효율적.
3. 데이터 접근: ArrayList가 효율적.
4. 중간 데이터 삭제: LinkedList가 효율적.