어레이/어레이 목록에서 링크된 목록을 사용하는 경우

어레이/어레이 목록에서 링크된 목록을 사용하는 경우

많은 목록과 어레이를 사용하고 있지만 어레이 목록을 링크된 목록만큼 쉽게 사용할 수 없는 시나리오는 아직 경험하지 못했습니다.링크된 리스트가 눈에 띄게 좋은 예를 들어주셨으면 합니다.

다음과 같은 경우 어레이보다 링크된 목록이 더 좋습니다.

1. 리스트에서 상시 삽입/삭제가 필요합니다(시간 예측 가능성이 절대적으로 중요한 실시간 컴퓨팅 등).

2. 몇 개의 아이템이 리스트에 있을지 모르기 때문에어레이의 경우 어레이가 너무 커지면 메모리를 다시 선언하고 복사해야 할 수 있습니다.

3. 어떤 요소에도 무작위로 접근할 필요가 없습니다.

4. 목록 중간에 항목을 삽입할 수 있어야 합니다(예: priority 큐).

어레이는 다음과 같은 경우에 적합합니다.

1. 요소에 대한 색인/인덱스 액세스 필요

2. 어레이에 적절한 메모리 양을 할당할 수 있도록 어레이 내의 요소 수를 미리 알고 있어야 합니다.

3. 모든 요소를 순서대로 반복할 때 속도가 필요합니다.각 요소에 액세스하려면 어레이의 포인터 산술 기능을 사용할 수 있지만 링크된 목록의 각 요소에 대한 포인터를 기반으로 노드를 조회해야 합니다. 이로 인해 페이지 장애가 발생하여 성능 저하가 발생할 수 있습니다.

4. 기억은 걱정이다.꽉 찬 어레이는 링크된 목록보다 메모리를 적게 차지합니다.배열의 각 요소는 데이터일 뿐입니다.각 링크 목록 노드에는 데이터와 링크 목록 내의 다른 요소에 대한 하나 이상의 포인터가 필요합니다.

배열 목록(의 목록과 같음)Net)는 어레이의 이점을 제공하지만 리소스를 동적으로 할당하므로 목록 크기에 대해 크게 걱정할 필요가 없습니다.또한 인덱스에서 항목을 삭제해도 쉽게 요소를 변경할 수 있습니다.성능 측면에서는 어레이 목록이 원시 어레이보다 느립니다.

어레이는 O(1) 랜덤 액세스가 가능하지만 추가 및 삭제 비용이 많이 듭니다.

링크 리스트는 어디에서든 아이템을 추가 또는 삭제하거나 반복하는 데 매우 저렴하지만 랜덤 액세스는 O(n)입니다.

Algorithm           ArrayList   LinkedList
seek front            O(1)         O(1)
seek back             O(1)         O(1)
seek to index         O(1)         O(N)
insert at front       O(N)         O(1)
insert at back        O(1)         O(1)
insert after an item  O(N)         O(1)

Array Lists는 한 번 읽으면 여러 번 쓸 수 있지만 전면 또는 중간에서 추가/삭제하는 데는 적합하지 않습니다.

다른 답변에 추가하기 위해 대부분의 어레이 목록 구현에서는 O(1) 시간 내에 새로운 요소를 목록 끝에 추가할 수 있도록 목록 끝에 추가 용량을 예약합니다.어레이 목록의 용량이 초과되면 더 큰 새 어레이가 내부적으로 할당되고 이전 요소가 모두 복사됩니다.일반적으로 새 배열은 이전 배열의 두 배 크기입니다.즉, 평균적으로 어레이 목록의 끝에 새로운 요소를 추가하는 것은 이러한 구현에서 O(1) 작업이 됩니다.따라서 요소의 수를 미리 알 수 없는 경우에도 마지막에 요소를 추가하는 한 배열 목록이 링크된 목록보다 더 빠를 수 있습니다.어레이 목록의 임의의 위치에 새 요소를 삽입하는 것은 여전히 O(n) 작업입니다.

배열 목록의 요소에 액세스하는 속도도 링크된 목록보다 빠릅니다(액세스가 순차적이더라도).이는 어레이 요소가 연속된 메모리에 저장되고 쉽게 캐시될 수 있기 때문입니다.링크된 목록 노드는 여러 페이지에 분산될 수 있습니다.

임의의 위치에 아이템을 삽입 또는 삭제할 것을 알고 있는 경우 링크 리스트만 사용하는 것을 권장합니다.어레이 리스트는, 그 외의 거의 모든 것에 대해서 고속이 됩니다.

목록의 장점은 중간에 항목을 삽입해야 하고 어레이 크기 조정 및 이동을 시작하지 않으려는 경우 나타납니다.

보통 그렇지 않다는 점에서 당신이 옳아요.그런 구체적인 사건도 몇 건 있었지만 너무 많지는 않았어요

이 모든 것은 반복 중에 실행하는 조작의 종류에 따라 달라집니다.모든 데이터 구조는 시간과 메모리의 균형을 유지합니다.필요에 따라 적절한 DS를 선택해야 합니다.따라서 Linked List가 어레이보다 고속이거나 그 반대일 수 있습니다.데이터 구조에 관한 3가지 기본적인 조작을 검토해 주십시오.

• 검색 중

배열은 인덱스 기반 데이터 구조 검색 어레이.get(index)은 O(1) 시간이 걸리고 linked list는 인덱스 DS가 아니기 때문에 인덱스로 이동해야 합니다.인덱스 <=n, n은 링크드 리스트의 크기입니다.따라서 요소에 랜덤으로 액세스할 때 배열이 링크드 리스트의 속도를 높일 수 있습니다.

Q. 그럼 이것의 장점은 무엇인가요?

어레이는 연속된 메모리 블록이기 때문에 첫 번째 액세스 시 큰 청크가 캐시에 로드됩니다.이것에 의해, 어레이의 나머지 요소에의 액세스도 비교적 고속화됩니다.참조하는 장소의 요소에의 액세스도 증가하기 때문에, 캐치 미스도 적어집니다.캐시 로컬이란 캐시 내에 있는 작업을 의미하기 때문에 메모리보다 훨씬 빠르게 실행됩니다.기본적으로 어레이에서는 순차적인 요소 액세스가 캐시 내에 있을 가능성을 최대한 높입니다.링크된 목록이 반드시 연속된 메모리 블록에 있는 것은 아니지만 목록에 순차적으로 나타나는 항목이 실제로 메모리에서 서로 가까이 배열된다는 보장은 없습니다. 즉, 캐시 적중률이 감소한다는 것입니다.링크 리스트 요소의 액세스 마다 메모리로부터 캐시의 누락이 증가하기 때문에, 액세스에 걸리는 시간이 길어지고, 퍼포먼스가 저하되기 때문에, 랜덤 액세스 조작(검색)이 많아지면, 어레이는 다음과 같이 고속이 됩니다.

• 삽입

이는 LinkedList(Java)에서는 어레이에 비해 삽입이 O(1) 조작이므로 LinkedList에서는 쉽고 빠릅니다.어레이가 꽉 차면 새로운 어레이에 콘텐츠를 복사해야 합니다.어레이가 꽉 차면 최악의 경우 O(n)의 ArrayList에 요소를 삽입할 수 있습니다.Array List는 어레이의 끝 이외의 장소에 삽입한 경우에도 인덱스를 갱신해야 합니다.링크 리스트의 경우 크기를 변경할 필요가 없습니다.포인터를 갱신하기만 하면 됩니다.

• 삭제

삽입처럼 기능하며 배열보다 Linked List에서 더 적합합니다.

실제 메모리 국소성은 실제 처리에서 성능에 큰 영향을 미칩니다.

랜덤 액세스에 비해 "빅 데이터" 처리에서 디스크 스트리밍 사용이 증가하면 이를 기반으로 애플리케이션을 구조화하면 대규모로 성능을 크게 향상시킬 수 있습니다.

어레이에 순차적으로 액세스하는 방법이 있다면 단연코 최고의 퍼포먼스입니다.성능이 중요한 경우에는 이를 목표로 설계하는 것이 최소한 고려되어야 합니다.

이것들은 컬렉션의 가장 일반적으로 사용되는 구현입니다.

어레이 리스트:

• 마지막에 삽입/삭제 일반적으로 O(1) 최악의 경우 O(n)

• 중간 O(n)에 삽입/삭제하다

• 임의의 위치 O(1)를 취득하다

Linked List:

• 임의의 위치 O(1)에 삽입/삭제(요소에 대한 참조가 있는 경우 주의)

• 중간 O(n)로 검색하다

• 첫 번째 또는 마지막 요소 O(1)를 검색합니다.

벡터: 사용하지 마세요.ArrayList와 비슷하지만 모든 메서드가 동기화되어 있는 오래된 구현입니다.이는 멀티스레딩 환경의 공유 목록에 대한 올바른 접근 방식이 아닙니다.

해시 맵

O(1)에서 키로 삽입/삭제/검색

Tree Set 삽입/삭제/O(log N)에 포함됨

O(1)의 해시 세트 삽입/제거/포함/크기

목록의 맨 위에 자주 삽입하거나 삭제해야 하는지가 가장 큰 차이점이라고 생각합니다.

배열의 경우 목록 맨 위에서 무언가를 제거하면 배열 요소의 모든 인덱스가 이동해야 하므로 복잡도가 o(n)보다 높아집니다.

링크 리스트의 경우 노드를 생성하여 헤드를 재할당하고 참조를 이전 헤드와 같이 next에 할당하기만 하면 되기 때문에 o(1)가 됩니다.

목록 끝에 자주 삽입 또는 삭제할 경우 복잡도가 o(1)이므로 어레이가 권장되며, 재인덱싱은 필요하지 않지만 링크된 목록의 경우 선두에서 마지막 노드로 이동해야 하므로 o(n)가 됩니다.

linked list와 array 모두 binary search를 사용할 것이기 때문에 o(log n)라고 생각합니다.

음, Arraylist는 다음과 같은 경우에 사용할 수 있습니다.

1. 몇 개의 요소가 존재할지 알 수 없습니다.
2. 그러나 인덱싱을 통해 모든 요소에 랜덤으로 액세스해야 합니다.

예를 들어 연락처 목록의 모든 요소를 Import하여 액세스해야 합니다(크기를 알 수 없음).

Radix Sort over 배열 및 다항식 연산에 대해 링크된 목록을 사용합니다.

1) 위에서 설명한 바와 같이 삽입 및 삭제 조작은 Array List(O(n)와 비교하여 Linked List(O(1))의 퍼포먼스가 우수합니다.따라서 응용 프로그램에서 자주 추가 및 삭제해야 하는 경우 Linked List가 최선의 선택입니다.

2) 검색(get method) 조작은 Array List(O(1)에서는 고속이지만 Linked List(O(n)에서는 고속입니다.따라서 추가 및 삭제 조작이 적고 검색 조작 요건이 더 많은 경우 Array List를 권장합니다.

벤치마킹을 해보니 목록 클래스가 Linked List보다 랜덤 삽입이 더 빠르다는 것을 알 수 있었습니다.

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int count = 20000;
            Random rand = new Random(12345);

            Stopwatch watch = Stopwatch.StartNew();
            LinkedList<int> ll = new LinkedList<int>();
            ll.AddLast(0);
            for (int i = 1; i < count; i++)
            {
                ll.AddBefore(ll.Find(rand.Next(i)),i);

            }
            Console.WriteLine("LinkedList/Random Add: {0}ms", watch.ElapsedMilliseconds);

            watch = Stopwatch.StartNew();
            List<int> list = new List<int>();
            list.Add(0);
            for (int i = 1; i < count; i++)
            {
                list.Insert(list.IndexOf(rand.Next(i)), i);

            }
            Console.WriteLine("List/Random Add: {0}ms", watch.ElapsedMilliseconds);

            Console.ReadLine();
        }
    }
}

링크 리스트는 900밀리초, 리스트클래스는 100밀리초 걸립니다.

이 명령어는 후속 정수 번호 목록을 작성합니다.각 새로운 정수는 목록에 이미 있는 난수 뒤에 삽입됩니다.List 클래스는 단순한 배열보다 더 나은 것을 사용할 수 있습니다.

어레이는 지금까지 가장 널리 사용되는 데이터 구조입니다.다만, 링크 리스트는 어레이가 서투르거나 비용이 많이 드는 경우에는 독자적인 방법으로 도움이 됩니다.

링크 리스트는 스택과 큐의 사이즈가 다른 경우에 실장하는 경우에 편리합니다.링크 목록의 각 노드는 대부분의 노드를 방해하지 않고 푸시 또는 팝할 수 있습니다.중간 어딘가에 노드를 삽입/삭제하는 경우에도 마찬가지입니다.그러나 어레이에서는 모든 요소를 이동해야 하므로 실행 시간이 많이 소요됩니다.

바이너리 트리 및 바이너리 검색 트리, 해시 테이블 및 시행은 데이터 구조의 일부이며, 적어도 C에서는 이를 구축하기 위한 기본 요소로 링크 리스트가 필요합니다.

단, 인덱스로 임의의 요소를 호출할 수 있을 것으로 예상되는 상황에서는 링크 리스트를 피해야 합니다.

질문에 대한 간단한 답변은 다음 사항을 사용하여 할 수 있습니다.

1. 어레이는 유사한 유형의 데이터 요소를 수집해야 할 때 사용합니다.반면 링크 리스트는 노드라고 하는 혼합형 데이터 링크 요소의 집합입니다.

2. 어레이에서는 O(1) 시간 내에 임의의 요소를 방문할 수 있습니다.반면 링크 리스트에서는 링크 리스트 전체를 헤드에서 필요한 노드까지 O(n) 시간이 걸립니다.

3. 어레이의 경우 처음에는 특정 크기를 선언해야 합니다.그러나 링크 리스트는 크기가 다릅니다.

언급URL : https://stackoverflow.com/questions/393556/when-to-use-a-linked-list-over-an-array-array-list