배열이 리스트보다 더 빠른 이유

결론을 먼저 말하자면, 배열과 리스트 간의 성능 차이는 사용 사례와 구현에 따라 다를 수 있으며, 종종 미미 할 수 있다
하지만, 자료구조 관점에서 리스트와 배열의 차이를 파악해보자

Intro. 궁금하더라

원래는 파이썬으로 알고리즘 문제를 풀었었는데, 자바로 풀게 되면서 궁금함을 느꼈다
이런 기초가 재밌더라 왠지 계속 글을 수정해 나가야겠다

실습

1. 데이터 읽기와 저장 비교

배열 쓰기 시간: 29.30 ms
리스트 쓰기 시간: 64.75 ms

배열 읽기 시간: 0.00 ms
리스트 읽기 시간: 0.01 ms

• 배열 쓰기
  • 배열의 크기는 고정되어 있으므로, 쓰기 연산은 매우 빠릅니다.
• 리스트 쓰기
  • ArrayList는 동적으로 크기를 조정할 수 있으므로, 필요에 따라 내부 배열을 확장해야 할 수도 있습니다.
  • 이로 인해 추가 오버헤드가 발생할 수 있습니다.
• 배열과 리스트 읽기
  • 배열과 ArrayList 모두 인덱스를 통한 접근이 O(1)의 시간 복잡도로 가능하므로, 읽기 성능은 매우 유사합니다.

2. 검색 성능 비교

선형 탐색 - 배열 위치: 4, 시간: 0.00274 ms
선형 탐색 - 리스트 위치: 4, 시간: 0.01166 ms
이진 탐색 - 배열 위치: 6, 시간: 0.00289 ms
이진 탐색 - 리스트 위치: 6, 시간: 0.00596 ms

• 선형 탐색
  • 배열과 ArrayList 모두 선형 탐색은 O(n)의 시간 복잡도를 가집니다.
• 이진 탐색
  • 이진 탐색은 정렬된 데이터에서만 사용 가능하며, 배열과 ArrayList 모두 O(log n)의 시간 복잡도를 가집니다.

ArrayList도 내부적으로 배열을 사용하지만, 메소드 호출과 객체 래퍼로 인한 추가 오버헤드가 있을 수 있습니다.

3. 정렬 성능 비교

Array sorting time: 0.21291 seconds
ArrayList sorting time: 0.09051 seconds

• 메모리 할당과 접근 패턴
  • 배열은 연속된 메모리 블록이므로 캐시 효율성이 더 높을 수 있습니다.
  • 그러나 ArrayList의 특정 구현과 JVM 최적화는 이를 상쇄시킬 수 있습니다.
• Garbage Collection
  • ArrayList는 크기 조정 중에 더 많은 객체를 생성하고 폐기할 수 있으므로, Garbage Collection의 영향을 받을 수 있습니다.
• 알고리즘과 최적화: 사용한 정렬 알고리즘과 자바 라이브러리의 내부 최적화도 성능에 큰 영향을 미칠 수 있습니다.

4. 데이터 삭제 비교

Array Deletion Time: 3.95321 ms
ArrayList Deletion Time: 0.51075 ms
LinkedList Deletion Time: 8.70194 ms

• 배열 삭제
  • 배열에서 요소를 삭제하려면 다른 요소를 이동해야 하므로 상대적으로 느립니다.
• ArrayList 삭제
  • ArrayList도 내부 배열에서 요소를 삭제하고 재조정해야 하므로 비슷한 오버헤드가 발생합니다.
  • 그러나 구현에 따른 최적화로 인해 더 빠를 수 있습니다.
• LinkedList 삭제
  • 연결 리스트에서의 삭제는 특정 노드에 대한 참조가 있으면 O(1)입니다.
  • 그러나 중간 요소를 삭제하려면 먼저 그 요소를 찾아야 하므로 O(n)의 시간이 걸릴 수 있습니다.

차이 분석

메모리 구조

배열은 메모리에서 연속된 공간에 할당됩니다.
이렇게 되면 CPU 캐시가 효율적으로 작동하므로 메모리 접근이 더 빠릅니다.

반면, 리스트(특히 LinkedList와 같은 일부 구현)는 메모리의 비연속적인 영역에 할당될 수 있으며, 이로 인해 캐시 효율이 떨어질 수 있습니다.

간접 참조의 유무

배열은 직접 메모리에 접근하므로 인덱스로 요소에 빠르게 접근할 수 있습니다.
일반적인 리스트 구현(예: ArrayList)은 내부적으로 배열을 사용하나, 추가적인 레이어가 있어 약간의 오버헤드가 발생할 수 있습니다.

동적 크기 조정

리스트는 동적으로 크기를 조정할 수 있으나, 이는 때때로 메모리 재할당과 복사를 필요로 합니다.
배열은 고정된 크기를 가지므로 이러한 오버헤드가 없습니다.

타입 래핑

일반 배열은 원시 타입을 직접 저장할 수 있으나, 리스트는 객체를 저장합니다.
원시 타입을 사용할 때, 리스트는 오토 박싱/언박싱 과정을 거쳐야 하므로 추가 오버헤드가 발생합니다.

실습 코드 모음

데이터 읽기와 쓰기

import java.util.ArrayList;
import java.util.Random;

public class Comparison {
    public static void main(String[] args) {
        int size = 1000000;
        int[] array = new int[size];
        ArrayList<Integer> arrayList = new ArrayList<>();
        Random rand = new Random();

        // 쓰기 성능 측정
        long startTime = System.nanoTime();
        for (int i = 0; i < size; i++) {
            array[i] = rand.nextInt();
        }
        long arrayWriteTime = System.nanoTime() - startTime;

        startTime = System.nanoTime();
        for (int i = 0; i < size; i++) {
            arrayList.add(rand.nextInt());
        }
        long listWriteTime = System.nanoTime() - startTime;

        System.out.printf("배열 쓰기 시간: %.2f ms\n", arrayWriteTime / 1000000.0);
        System.out.printf("리스트 쓰기 시간: %.2f ms\n", listWriteTime / 1000000.0);

        // 읽기 성능 측정
        int index = rand.nextInt(size);
        startTime = System.nanoTime();
        int valueFromArray = array[index];
        long arrayReadTime = System.nanoTime() - startTime;

        startTime = System.nanoTime();
        int valueFromList = arrayList.get(index);
        long listReadTime = System.nanoTime() - startTime;

        System.out.printf("배열 읽기 시간: %.2f ms\n", arrayReadTime / 1000000.0);
        System.out.printf("리스트 읽기 시간: %.2f ms\n", listReadTime / 1000000.0);
    }
}

검색 성능

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

public class SearchComparison {

    public static void main(String[] args) {
        int[] array = {34, 7, 23, 32, 85, 62, 30};
        List<Integer> list = new ArrayList<>(Arrays.asList(34, 7, 23, 32, 85, 62, 30));
        
        int target = 85;

        // 선형 탐색
        long startTime = System.nanoTime();
        int arrayLinearIndex = linearSearch(array, target);
        long arrayLinearTime = System.nanoTime() - startTime;

        startTime = System.nanoTime();
        int listLinearIndex = linearSearch(list, target);
        long listLinearTime = System.nanoTime() - startTime;

        System.out.printf("선형 탐색 - 배열 위치: %d, 시간: %.5f ms\n", arrayLinearIndex, arrayLinearTime / 1e6);
        System.out.printf("선형 탐색 - 리스트 위치: %d, 시간: %.5f ms\n", listLinearIndex, listLinearTime / 1e6);

        // 이진 탐색
        Arrays.sort(array);
        list.sort(Integer::compareTo);

        startTime = System.nanoTime();
        int arrayBinaryIndex = binarySearch(array, target);
        long arrayBinaryTime = System.nanoTime() - startTime;

        startTime = System.nanoTime();
        int listBinaryIndex = binarySearch(list, target);
        long listBinaryTime = System.nanoTime() - startTime;

        System.out.printf("이진 탐색 - 배열 위치: %d, 시간: %.5f ms\n", arrayBinaryIndex, arrayBinaryTime / 1e6);
        System.out.printf("이진 탐색 - 리스트 위치: %d, 시간: %.5f ms\n", listBinaryIndex, listBinaryTime / 1e6);
    }

    public static int linearSearch(int[] array, int target) {
        for (int i = 0; i < array.length; i++) {
            if (array[i] == target) return i;
        }
        return -1;
    }

    public static int linearSearch(List<Integer> list, int target) {
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i).equals(target)) return i;
        }
        return -1;
    }

    public static int binarySearch(int[] array, int target) {
        int left = 0, right = array.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (array[mid] == target) return mid;
            if (array[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }

    public static int binarySearch(List<Integer> list, int target) {
        int left = 0, right = list.size() - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (list.get(mid).equals(target)) return mid;
            if (list.get(mid) < target) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }
}

정렬

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;

public class SortingComparison {
    public static void main(String[] args) {
        int size = 100000; // Sample size
        int[] array = new int[size];
        ArrayList<Integer> arrayList = new ArrayList<>();

        // Filling with random integers
        Random rand = new Random();
        for (int i = 0; i < size; i++) {
            int value = rand.nextInt(size);
            array[i] = value;
            arrayList.add(value);
        }

        // Measuring time for sorting array
        long startTimeArray = System.nanoTime();
        Arrays.sort(array); // Using Java's built-in quicksort
        long endTimeArray = System.nanoTime();

        // Measuring time for sorting ArrayList
        long startTimeArrayList = System.nanoTime();
        arrayList.sort(null); // Using Java's built-in quicksort
        long endTimeArrayList = System.nanoTime();

        // Calculating and printing the times
        double timeArray = (endTimeArray - startTimeArray) / 1_000_000_000.0;
        double timeArrayList = (endTimeArrayList - startTimeArrayList) / 1_000_000_000.0;

        System.out.printf("Array sorting time: %.5f seconds%n", timeArray);
        System.out.printf("ArrayList sorting time: %.5f seconds%n", timeArrayList);
    }
}

데이터 삭제

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

public class DeletionComparison {
    public static void main(String[] args) {
        int size = 1000000;
        int[] array = new int[size];
        List<Integer> arrayList = new ArrayList<>();
        List<Integer> linkedList = new LinkedList<>();

        // Initialization
        for (int i = 0; i < size; i++) {
            array[i] = i;
            arrayList.add(i);
            linkedList.add(i);
        }

        // Measure deletion time for array
        long startTime = System.nanoTime();
        int[] newArray = new int[size - 1];
        System.arraycopy(array, 0, newArray, 0, size / 2);
        System.arraycopy(array, size / 2 + 1, newArray, size / 2, size - size / 2 - 1);
        long arrayTime = System.nanoTime() - startTime;

        // Measure deletion time for ArrayList
        startTime = System.nanoTime();
        arrayList.remove(size / 2);
        long arrayListTime = System.nanoTime() - startTime;

        // Measure deletion time for LinkedList
        startTime = System.nanoTime();
        linkedList.remove(size / 2);
        long linkedListTime = System.nanoTime() - startTime;

        System.out.printf("Array Deletion Time: %.5f ms%n", arrayTime / 1000000.0);
        System.out.printf("ArrayList Deletion Time: %.5f ms%n", arrayListTime / 1000000.0);
        System.out.printf("LinkedList Deletion Time: %.5f ms%n", linkedListTime / 1000000.0);
    }
}

레퍼런스

• Java의 ArrayList와 Linked List의 차이
• ArrayList의 구조

부족한 점이나 잘못 된 점을 알려주시면 시정하겠습니다 :>