program tip

ArrayList와 LinkedList의 성능 차이

radiobox 2021. 1. 7. 07:50
반응형

ArrayList와 LinkedList의 성능 차이


예, 이것은 오래된 주제이지만 여전히 약간의 혼란이 있습니다.

자바에서 사람들은 다음과 같이 말합니다.

  1. ArrayList는 요소에 임의로 액세스하면 LinkedList보다 빠릅니다. 랜덤 액세스는 "n 번째 요소를주세요"를 의미한다고 생각합니다. ArrayList가 더 빠른 이유는 무엇입니까?

  2. LinkedList는 삭제를 위해 ArrayList보다 빠릅니다. 나는 이것을 이해한다. 내부 백업 어레이를 재 할당해야하므로 ArrayList가 느립니다. 코드 설명 :

    List<String> list = new ArrayList<String>();
    list.add("a");
    list.add("b");
    list.add("c");
    list.remove("b");
    System.out.println(list.get(1)); //output "c"
    
  3. LinkedList는 삽입시 ArrayList보다 빠릅니다. 여기서 삽입은 무엇을 의미합니까? 일부 요소를 다시 이동 한 다음 해당 요소를 가운데 빈 자리에 넣으려면 ArrayList가 LinkedList보다 느려 야합니다. 삽입이 add (Object) 작업만을 의미한다면 어떻게 느려질 수 있습니까?


ArrayList는 요소에 임의로 액세스하면 LinkedList보다 빠릅니다. 랜덤 액세스는 "n 번째 요소를주세요"를 의미한다고 생각합니다. ArrayList가 더 빠른 이유는 무엇입니까?

ArrayList목록의 모든 요소에 대한 직접 참조가 있으므로 일정한 시간에 n 번째 요소를 가져올 수 있습니다. LinkedListn 번째 요소에 도달하려면 처음부터 목록을 순회해야합니다.

LinkedList는 삭제를 위해 ArrayList보다 빠릅니다. 나는 이것을 이해한다. 내부 백업 어레이를 재 할당해야하므로 ArrayList가 느립니다.

ArrayList여유가 된 슬롯을 제거하기 위해 어레이의 일부를 복사해야하기 때문에 느립니다. ListIterator.remove()API를 사용하여 삭제 LinkedList하는 경우 몇 가지 참조를 조작하면됩니다. 값 또는 인덱스에 의해 삭제가 수행되는 경우 삭제할 LinkedList요소를 찾기 위해 먼저 전체 목록을 잠재적으로 스캔해야합니다.

일부 요소를 다시 이동 한 다음 해당 요소를 가운데 빈 자리에 넣으면 ArrayList가 느려집니다.

예, 이것이 의미하는 바입니다. 어레이 중간에 슬롯을 확보해야하기 때문에 ArrayList실제로 속도가 느립니다 LinkedList. 여기에는 일부 참조를 이동하고 최악의 경우 전체 어레이를 재 할당하는 것이 포함됩니다. LinkedList일부 참조를 조작하면됩니다.


지금은이 대답을 무시하십시오. 다른 답변, 특히 aix의 답변 은 대부분 정확합니다. 장기적으로 그들은 베팅하는 방법입니다. 그리고 충분한 데이터가있는 경우 (한 시스템의 한 벤치 마크에서 약 백만 개의 항목이있는 것처럼 보임) ArrayList 및 LinkedList는 현재 광고 된대로 작동합니다. 그러나 21 세기 초에 적용되는 몇 가지 요점이 있습니다.

내 테스트에 따르면 현대 컴퓨터 기술은 어레이에 엄청난 우위를 제공하는 것 같습니다. 배열의 요소는 엄청난 속도로 이동하고 복사 할 수 있습니다. 결과적으로 배열과 ArrayList는 대부분의 실제 상황에서 삽입 및 삭제시 LinkedList보다 훨씬 뛰어난 성능을 발휘합니다. 즉, ArrayList는 자체 게임에서 LinkedList를 이길 것입니다.

ArrayList의 단점은 삭제 후 메모리 공간에 매달리는 경향이 있으며 LinkedList는 항목을 포기할 때 공간을 포기합니다.

배열과 ArrayList 더 큰 단점은 사용 가능한 메모리를 조각화하고 가비지 수집기를 과도하게 사용한다는 것입니다. ArrayList가 확장되면 더 큰 새 배열을 만들고 이전 배열을 새 배열에 복사 한 다음 이전 배열을 해제합니다. 메모리는 다음 할당에 충분하지 않은 큰 연속 된 여유 메모리 청크로 채워집니다. 결국 해당 할당에 적합한 공간이 없습니다. 메모리의 90 %가 무료이지만 작업을 수행 할만큼 큰 개별 조각은 없습니다. GC는 사물을 이동하기 위해 미친 듯이 작동하지만 공간을 재정렬하는 데 너무 오래 걸리면 OutOfMemoryException이 발생합니다. 포기하지 않으면 프로그램 속도가 느려질 수 있습니다.

최악의 경우이 문제는 예측하기 어려울 수 있습니다. 프로그램은 한 번 제대로 실행됩니다. 그런 다음 경고없이 사용 가능한 메모리가 약간 줄어들면 속도가 느려지거나 중지됩니다.

LinkedList는 작고 섬세한 메모리를 사용하며 GC는 그것을 좋아합니다. 사용 가능한 메모리의 99 %를 사용하면 여전히 정상적으로 실행됩니다.

따라서 일반적으로 대부분의 내용이 삭제되지 않았거나 생성 및 확장을 엄격하게 제어 할 수있는 소규모 데이터 집합에 대해 ArrayList를 사용합니다. (예를 들어, 메모리의 90 %를 사용하는 ArrayList를 하나 만들고 프로그램 기간 동안 채우지 않고 사용하는 것은 괜찮습니다. 계속해서 메모리의 10 %를 사용하는 ArrayList 인스턴스를 만들고 해제하면 죽을 것입니다.) 그렇지 않으면 LinkedList를 사용하십시오. (또는 임의 액세스가 필요한 경우 일종의지도). 매우 큰 컬렉션 (예 : 100,000 개 이상의 요소)이 있고 GC에 대한 우려가없고 많은 삽입 및 삭제를 계획하고 무작위 액세스가없는 경우 몇 가지 벤치 마크를 실행하여 가장 빠른 것을 확인하십시오.


ArrayList클래스 배열 래퍼 클래스이다. 내부 배열을 포함합니다.

public ArrayList<T> {
    private Object[] array;
    private int size;
}

A LinkedList는 데이터를 관리하기위한 내부 노드가있는 연결 목록의 래퍼 클래스입니다.

public LinkedList<T> {
    class Node<T> {
        T data;
        Node next;
        Node prev;
    }
    private Node<T> first;
    private Node<T> last;
    private int size;
}

현재 코드는 실제 구현이 아닌 클래스가 어떻게 될 수 있는지 보여주기 위해 사용됩니다. 구현 방법을 알고 있으면 추가 분석을 수행 할 수 있습니다.

ArrayList는 요소에 임의로 액세스하면 LinkedList보다 빠릅니다. 랜덤 액세스는 "n 번째 요소를주세요"를 의미한다고 생각합니다. ArrayList가 더 빠른 이유는 무엇입니까?

ArrayList에 대한 액세스 시간 : O (1). LinkedList에 대한 액세스 시간 : O (n).

배열에서는를 사용하여 모든 요소에 액세스 할 수 array[index]있지만 연결 목록 first에서는 필요한 요소를 얻을 때까지 모든 목록을 탐색 해야합니다.

LinkedList는 삭제를 위해 ArrayList보다 빠릅니다. 나는 이것을 이해한다. 내부 백업 어레이를 재 할당해야하므로 ArrayList가 느립니다.

ArrayList의 삭제 시간 : 액세스 시간 + O (n). LinkedList 삭제 시간 : 액세스 시간 + O (1).

ArrayList에이 모든 요소를 이동해야 array[index]하는 array[index-1]삭제 색인 항목에 의해 시작. LinkedList는 해당 항목까지 탐색 한 다음 목록에서 분리하여 해당 노드를 지워야합니다.

LinkedList는 삭제를 위해 ArrayList보다 빠릅니다. 나는 이것을 이해한다. 내부 백업 어레이를 재 할당해야하므로 ArrayList가 느립니다.

ArrayList의 삽입 시간 : O (n). LinkedList의 삽입 시간 : O (1).

ArrayList가 O (n)을 취할 수있는 이유는 무엇입니까? 새 요소를 삽입하고 배열이 가득 차면 더 많은 크기의 새 배열을 만들어야합니다 (2 * 크기 또는 3 * 크기 / 2와 같은 공식을 사용하여 새 크기를 계산할 수 있음). LinkedList는 마지막 노드 옆에 새 노드를 추가합니다.

이 분석은 Java뿐만 아니라 C, C ++ 및 C #과 같은 다른 프로그래밍 언어로 이루어집니다.

여기에 더 많은 정보 :


remove () 및 insert () 모두 ArrayList 및 LinkedLists 모두에 대해 O (n)의 런타임 효율성을 갖습니다. 그러나 선형 처리 시간의 이유는 두 가지 매우 다른 이유에서 비롯됩니다.

ArrayList에서 O (1)의 요소에 도달하지만 실제로는 무언가를 제거하거나 삽입하면 다음 요소를 모두 변경해야하기 때문에 O (n)이됩니다.

LinkedList에서는 원하는 인덱스에 도달 할 때까지 맨 처음부터 시작해야하기 때문에 실제로 원하는 요소에 도달하려면 O (n)이 필요합니다. remove ()에 대한 참조 1 개와 insert ()에 대한 참조 2 개만 변경하면되므로 제거 또는 삽입은 일정합니다.

둘 중 삽입 및 제거가 더 빠른 것은 발생 위치에 따라 다릅니다. 시작 부분에 가까워지면 상대적으로 적은 수의 요소를 거쳐야하기 때문에 LinkedList가 더 빨라질 것입니다. 우리가 끝에 가까워지면 ArrayList가 더 빨라질 것입니다. 왜냐하면 우리는 일정한 시간에 거기에 도달하고 그 뒤에 오는 몇 개의 나머지 요소 만 변경하면되기 때문입니다.

보너스 : ArrayList에 대해이 두 가지 메서드를 O (1)로 만들 수있는 방법은 없지만 실제로 LinkedLists에서이를 수행하는 방법이 있습니다. 우리가 도중에 요소를 제거하고 삽입하는 전체 목록을 살펴보고 싶다고 가정 해 봅시다. 일반적으로 LinkedList를 사용하여 각 요소에 대해 처음부터 시작하며, Iterator로 작업중인 현재 요소를 "저장"할 수도 있습니다. Iterator의 도움으로 LinkedList에서 작업 할 때 remove () 및 insert ()에 대해 O (1) 효율성을 얻습니다. LinkedList가 ArrayList보다 항상 더 나은 곳을 알고있는 유일한 성능 이점입니다.


대답 1 : ArrayList는 내부적으로 배열을 사용합니다. ArrayList 개체의 멤버에 액세스하는 것은 인덱스가 지원 배열의 경계 내에 있다고 가정하고 제공된 인덱스에서 배열에 액세스하는 것만 큼 간단합니다. LinkedList는 n 번째 요소에 도달하기 위해 멤버를 반복해야합니다. LinkedList의 경우 O (n)이고 ArrayList의 경우 O (1)입니다.


LinkedList에서 요소는 앞뒤에 요소에 대한 참조를 갖습니다. ArrayList에서 데이터 구조는 배열 일뿐입니다.

  1. LinkedList는 N 번째 요소를 얻기 위해 N 요소를 반복해야합니다. ArrayList는 지원 배열의 N 요소 만 반환하면됩니다.

  2. 백업 배열은 새 크기에 대해 재 할당되고 배열을 복사하거나 삭제 된 요소 이후의 모든 요소를 ​​빈 공간을 채우기 위해 위로 이동해야합니다. LinkedList는 제거 된 요소의 이전 참조를 제거 이전의 요소로 설정하고 제거 된 요소 이전 요소의 다음 참조를 제거 된 요소 이후의 요소로 설정하면됩니다. 설명하는 데 더 오래 걸리지 만 더 빨리 할 수 ​​있습니다.

  3. 여기서 삭제와 같은 이유입니다.


ArrayList

  • ArrayList는 빈번한 작업이 검색 작업 인 경우 가장 좋은 선택입니다.
  • ArrayList는 내부적으로 여러 개의 시프트 작업이 수행되기 때문에 작업이 중간에 삽입 및 삭제 인 경우 최악의 선택입니다.
  • ArrayList 요소는 연속적인 메모리 위치에 저장되므로 검색 작업이 쉬워집니다.

LinkedList :-

  • LinkedList는 빈번한 작업이 중간에 삽입 및 삭제 인 경우 최상의 선택입니다.
  • LinkedList는 최악의 선택입니다. 우리의 빈번한 작업은 검색 작업입니다.
  • LinkedList에서 요소는 연속적인 메모리 위치에 저장되지 않으므로 검색 작업이 복잡합니다.

이제 당신의 질문에오고 있습니다 :-

1) ArrayList는 인덱스에 따라 데이터를 저장하고 ArrayList에 Random 검색 기능을 제공하는 마커 인터페이스 인 RandomAccess 인터페이스를 구현하고 있지만 LinkedList는 RandomAccess Interface를 구현하지 않아 ArrayList가 LinkedList보다 빠른 이유입니다.

2) LinkedList의 기본 데이터 구조는 이중 연결 목록이므로 LinkedList에서 중간에 삽입 및 삭제가 매우 쉽습니다. ArrayList (즉, ArrayList와 같이 삭제 및 삽입 작업에 대해 각각의 모든 요소를 ​​이동할 필요가 없기 때문입니다. 내부적으로 여러 번의 시프트 작업이 수행되므로 중간에 삽입 및 삭제 작업 인 경우 권장되지 않습니다.)
출처


ArrayList : ArrayList는 배열과 같은 구조를 가지고 있으며 모든 요소에 대한 직접 참조가 있습니다. 따라서 rendom 액세스는 ArrayList에서 빠릅니다.

LinkedList : LinkedList에서 n 번째 요소를 얻으려면 전체 목록을 탐색해야하는데 ArrayList에 비해 시간이 걸립니다. 모든 요소에는 이전 및 중첩 요소에 대한 링크가 있으므로 삭제가 빠릅니다.


ArrayList : ArrayList 클래스는 AbstractList를 확장하고 List 인터페이스와 RandomAccess (마커 인터페이스)를 구현합니다. ArrayList는 필요에 따라 확장 할 수있는 동적 배열을 지원합니다. 요소에 대한 첫 번째 반복을 제공합니다.

LinkedList : LinkedList는 요소가 서로 이중으로 연결된다는 점을 제외하고 ArrayList와 같이 인덱스 위치에 따라 정렬됩니다. 이 연결은 시작 또는 끝에서 추가 및 제거 할 수있는 새로운 메서드 (List 인터페이스에서 얻은 것 이상)를 제공하므로 스택 또는 대기열을 쉽게 구현할 수 있습니다. LinkedList는 ArrayList보다 더 느리게 반복 될 수 있지만 빠른 삽입 및 삭제가 필요한 경우 좋은 선택입니다. Java 5부터 LinkedList 클래스는 java.util.Queue 인터페이스를 구현하도록 향상되었습니다. 따라서 이제 일반 큐 메서드 인 peek (), poll () 및 offer ()를 지원합니다.


성능 차이에 대한 추가 정보를 추가하고 싶습니다.

ArrayList구현이에 의해 뒷받침 된다는 사실로 인해 Object[]임의 액세스 및 동적 크기 조정을 지원하고 LinkedList구현은 탐색하기 위해 헤드 및 테일에 대한 참조를 사용 한다는 것을 이미 알고 있습니다. 임의 액세스 기능이 없지만 동적 크기 조정도 지원합니다.

첫 번째는 ArrayList를 사용하면 인덱스에 즉시 액세스 할 수있는 반면 LinkedList를 사용하면 개체 체인을 반복 할 수 있다는 것입니다.

둘째, ArrayList에 삽입하는 것은 일반적으로 경계에 도달하면 커야하기 때문에 느립니다. 더 큰 새 어레이를 만들고 원래 어레이에서 데이터를 복사해야합니다.

그러나 흥미로운 점이미 모든 삽입에 맞도록 충분히 큰 ArrayList를 만들분명히 배열 복사 작업이 포함되지 않는다는 것입니다. LinkedList가 포인터를 처리해야하기 때문에 여기에 추가하는 것이 LinkedList보다 훨씬 빠르며 거대한 ArrayList는 주어진 인덱스에서 값을 설정합니다.

여기에 이미지 설명 입력

더 많은 ArrayList 및 LinkedList 차이점 을 확인하십시오 .


동일 해 보이지만 (동일하게 구현 된 inteface List-스레드로부터 안전하지 않음) 추가 / 삭제 및 검색 시간과 메모리 소비 측면에서 다른 결과를 제공합니다 (LinkedList가 더 많이 소비 함).

LinkedLists는 성능 O (1)와 함께 고도로 삽입 / 삭제를 사용하는 경우 사용할 수 있습니다. 성능 O (1)로 직접 액세스 작업을 사용하는 경우 ArrayLists를 사용할 수 있습니다.

이 코드는 이러한 주석을 명확히 할 수 있으며 성능 결과를 이해하려고 시도 할 수 있습니다. (보일러 플레이트 코드 죄송합니다)

public class Test {

    private static Random rnd;


    static {
        rnd = new Random();
    }


    static List<String> testArrayList;
    static List<String> testLinkedList;
    public static final int COUNT_OBJ = 2000000;

    public static void main(String[] args) {
        testArrayList = new ArrayList<>();
        testLinkedList = new LinkedList<>();

        insertSomeDummyData(testLinkedList);
        insertSomeDummyData(testArrayList);

        checkInsertionPerformance(testLinkedList);  //O(1)
        checkInsertionPerformance(testArrayList);   //O(1) -> O(n)

        checkPerformanceForFinding(testArrayList);  // O(1)
        checkPerformanceForFinding(testLinkedList); // O(n)

    }


    public static void insertSomeDummyData(List<String> list) {
        for (int i = COUNT_OBJ; i-- > 0; ) {
            list.add(new String("" + i));
        }
    }

    public static void checkInsertionPerformance(List<String> list) {

        long startTime, finishedTime;
        startTime = System.currentTimeMillis();
        int rndIndex;
        for (int i = 200; i-- > 0; ) {
            rndIndex = rnd.nextInt(100000);
            list.add(rndIndex, "test");
        }
        finishedTime = System.currentTimeMillis();
        System.out.println(String.format("%s time passed at insertion:%d", list.getClass().getSimpleName(), (finishedTime - startTime)));
    }

    public static void checkPerformanceForFinding(List<String> list) {

        long startTime, finishedTime;
        startTime = System.currentTimeMillis();
        int rndIndex;
        for (int i = 200; i-- > 0; ) {
            rndIndex = rnd.nextInt(100000);
            list.get(rndIndex);
        }
        finishedTime = System.currentTimeMillis();
        System.out.println(String.format("%s time passed at searching:%d", list.getClass().getSimpleName(), (finishedTime - startTime)));

    }

}

참조 URL : https://stackoverflow.com/questions/10656471/performance-differences-between-arraylist-and-linkedlist

반응형