ArrayList와 LinkedList의 성능 차이

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 #과 같은 다른 프로그래밍 언어로 이루어집니다.

여기에 더 많은 정보 :

• http://en.wikipedia.org/wiki/Array_data_structure
• http://en.wikipedia.org/wiki/Linked_list

---

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