언제 List와 LinkedList를 사용해야합니까?
언제 List 대 LinkedList 를 사용하는 것이 더 낫 습니까?
편집하다
이 답변에 대한 의견을 읽으십시오. 사람들은 내가 적절한 테스트를하지 않았다고 주장합니다. 나는 이것이 받아 들여서는 안된다는 데 동의합니다. 배우면서 몇 가지 테스트를 수행하고 공유하는 느낌이 들었습니다.
원래 답변 ...
흥미로운 결과를 찾았습니다.
// Temporary class to show the example
class Temp
{
public decimal A, B, C, D;
public Temp(decimal a, decimal b, decimal c, decimal d)
{
A = a; B = b; C = c; D = d;
}
}
연결된 목록 (3.9 초)
LinkedList<Temp> list = new LinkedList<Temp>();
for (var i = 0; i < 12345678; i++)
{
var a = new Temp(i, i, i, i);
list.AddLast(a);
}
decimal sum = 0;
foreach (var item in list)
sum += item.A;
목록 (2.4 초)
List<Temp> list = new List<Temp>(); // 2.4 seconds
for (var i = 0; i < 12345678; i++)
{
var a = new Temp(i, i, i, i);
list.Add(a);
}
decimal sum = 0;
foreach (var item in list)
sum += item.A;
본질적으로 데이터에만 액세스하더라도 훨씬 느립니다 !! 나는 linkedList를 사용하지 않는다고 말한다.
다음은 많은 인서트를 수행하는 또 다른 비교입니다 (목록 중간에 항목을 삽입 할 계획입니다)
연결 목록 (51 초)
LinkedList<Temp> list = new LinkedList<Temp>();
for (var i = 0; i < 123456; i++)
{
var a = new Temp(i, i, i, i);
list.AddLast(a);
var curNode = list.First;
for (var k = 0; k < i/2; k++) // In order to insert a node at the middle of the list we need to find it
curNode = curNode.Next;
list.AddAfter(curNode, a); // Insert it after
}
decimal sum = 0;
foreach (var item in list)
sum += item.A;
목록 (7.26 초)
List<Temp> list = new List<Temp>();
for (var i = 0; i < 123456; i++)
{
var a = new Temp(i, i, i, i);
list.Insert(i / 2, a);
}
decimal sum = 0;
foreach (var item in list)
sum += item.A;
삽입 위치 (.04 초)를 참조하는 링크 된 목록
list.AddLast(new Temp(1,1,1,1));
var referenceNode = list.First;
for (var i = 0; i < 123456; i++)
{
var a = new Temp(i, i, i, i);
list.AddLast(a);
list.AddBefore(referenceNode, a);
}
decimal sum = 0;
foreach (var item in list)
sum += item.A;
그래서 단지 당신이 여러 항목을 삽입 계획하고있는 경우 도 어딘가에는 다음 링크 된 목록을 사용하여 항목을 삽입 할 계획 곳의 레퍼런스를 가지고있다. 많은 항목을 삽입해야하기 때문에 삽입하려는 위치를 검색하면 시간이 걸리기 때문에 더 빠르지 않습니다.
대부분의 경우 List<T>더 유용합니다. LinkedList<T>목록 중간에 항목을 추가 / 제거 할 때 비용이 적게 들지만 목록 끝에List<T> 값을 추가 / 제거 할 수 있습니다 .
LinkedList<T>순차 또는 역순으로 순차 데이터에 액세스하는 경우에만 가장 효율적입니다. 임의의 액세스는 매번 체인을 걸어야하기 때문에 상대적으로 비쌉니다 (따라서 인덱서가없는 이유). 그러나 a List<T>는 본질적으로 배열 (래퍼 포함)이므로 임의 액세스가 좋습니다.
List<T>또한 지원 방법을 많이 제공합니다 - Find, ToArray등; 그러나 LinkedList<T>확장 방법을 통해 .NET 3.5 / C # 3.0 에서도 사용할 수 있으므로 그다지 중요하지 않습니다.
연결된 목록을 목록으로 생각하는 것은 약간 오해의 소지가 있습니다. 체인과 비슷합니다. 실제로 .NET에서는 LinkedList<T>조차 구현하지 않습니다 IList<T>. 비록 링크 된리스트에 인덱스의 실제 개념은 존재하지 않지만 보일 수 있습니다. 클래스에 제공된 메소드 중 어느 것도 인덱스를 허용하지 않습니다.
연결된 목록은 단독으로 연결되거나 이중으로 연결될 수 있습니다. 이것은 체인의 각 요소가 다음 요소에만 링크되는지 (단일 링크되어 있는지) 또는 이전 / 다음 요소 모두에 링크되어 있는지 (아마도 링크되어 있는지)를 나타냅니다. LinkedList<T>이중 연결되어 있습니다.
내부적 List<T>으로 배열이 지원합니다. 이것은 메모리에서 매우 컴팩트 한 표현을 제공합니다. 반대로, LinkedList<T>연속 요소 사이의 양방향 링크를 저장하기위한 추가 메모리가 필요합니다. 따라서 a의 메모리 풋 프린트 LinkedList<T>는 일반적으로 메모리 용량 보다 더 클 것입니다 List<T>( List<T>추가 작업 중에 성능을 향상시키기 위해 사용되지 않는 내부 배열 요소를 가질 수 있는 경고가 있음 ).
성능 특성도 다릅니다.
추가
LinkedList<T>.AddLast(item)일정한 시간List<T>.Add(item)상각 일정 시간, 선형 최악의 경우
접두사
LinkedList<T>.AddFirst(item)일정한 시간List<T>.Insert(0, item)선형 시간
삽입
LinkedList<T>.AddBefore(node, item)일정한 시간LinkedList<T>.AddAfter(node, item)일정한 시간List<T>.Insert(index, item)선형 시간
제거
LinkedList<T>.Remove(item)선형 시간LinkedList<T>.Remove(node)일정한 시간List<T>.Remove(item)선형 시간List<T>.RemoveAt(index)선형 시간
카운트
LinkedList<T>.Count일정한 시간List<T>.Count일정한 시간
포함
LinkedList<T>.Contains(item)선형 시간List<T>.Contains(item)선형 시간
명확한
LinkedList<T>.Clear()선형 시간List<T>.Clear()선형 시간
보다시피, 그것들은 대부분 동등합니다. 실제로 API는 사용하기 LinkedList<T>가 더 번거로우 며 내부 요구 사항에 대한 세부 정보가 코드에 유출됩니다.
그러나 목록 내에서 많은 삽입 / 제거를 수행해야하는 경우 일정한 시간을 제공합니다. List<T>삽입 / 제거 후 목록의 추가 항목을 뒤섞어 야하므로 선형 시간을 제공합니다.
연결된 목록은 목록 구성원을 매우 빠르게 삽입하거나 삭제합니다. 링크 된 목록의 각 멤버에는 목록의 다음 멤버에 대한 포인터가 포함되어 i 위치에 멤버를 삽입합니다.
- i-1 멤버의 포인터를 업데이트하여 새 멤버를 가리 킵니다.
- 새 멤버의 포인터를 멤버 i를 가리 키도록 설정하십시오.
연결된 목록의 단점은 임의 액세스가 불가능하다는 것입니다. 멤버에 액세스하려면 원하는 멤버를 찾을 때까지 목록을 탐색해야합니다.
내 이전 답변이 충분히 정확하지 않았습니다. 참으로 그것은 끔찍했다 : D 그러나 지금 나는 훨씬 더 유용하고 정확한 답변을 게시 할 수 있습니다.
추가 테스트를했습니다. https://github.com/ukushu/DataStructuresTestsAndOther.git 링크를 통해 소스를 찾아 환경에서 다시 확인할 수 있습니다.
짧은 결과 :
배열은 다음을 사용해야합니다.
- 가능한 자주. 동일한 양의 정보를 얻기 위해 빠르며 RAM 범위가 가장 작습니다.
- 필요한 정확한 세포 수를 알고 있다면
- 데이터가 어레이 <85000b에 저장된 경우
- 높은 랜덤 액세스 속도가 필요한 경우
목록을 사용해야합니다.
- 목록 끝에 셀을 추가해야하는 경우 (종종)
- 목록의 시작 / 중간에 셀을 추가해야하는 경우
- 데이터가 어레이 <85000b에 저장된 경우
- 높은 랜덤 액세스 속도가 필요한 경우
LinkedList는 다음을 사용해야합니다.
- 목록의 시작 / 중간 / 끝에 셀을 추가해야하는 경우 (종종)
- 순차적 액세스 만 필요한 경우 (앞으로 / 뒤로)
- 큰 항목을 저장해야하지만 항목 수가 적은 경우
- 링크에 추가 메모리를 사용하므로 대량의 항목에는 사용하지 않는 것이 좋습니다.
자세한 내용은:
알고 싶은 것 :
LinkedList<T>internally는 .NET의 List가 아닙니다. 심지어 구현하지도 않습니다IList<T>. 이것이 인덱스와 관련된 인덱스와 메소드가없는 이유입니다.LinkedList<T>노드 포인터 기반 컬렉션입니다. .NET에서는 이중 링크 구현입니다. 이는 이전 / 다음 요소가 현재 요소에 연결되어 있음을 의미합니다. 또한 데이터가 조각화되어 다른 RAM의 다른 위치에 다른 목록 개체를 배치 할 수 있습니다. 또한LinkedList<T>forList<T>또는 Array 보다 더 많은 메모리가 사용됩니다 .List<T>.Net에서 Java의 대안입니다ArrayList<T>. 이것은 이것이 배열 래퍼임을 의미합니다. 따라서 하나의 연속 된 데이터 블록으로 메모리에 할당됩니다. 할당 된 데이터 크기가 85000 바이트를 초과하면 Large Object Heap으로 이동합니다. 크기에 따라 힙 조각화 (가벼운 형태의 메모리 누수)가 발생할 수 있습니다. 그러나 크기가 85000 바이트 미만인 경우 메모리에서 매우 작고 빠른 액세스 표현을 제공합니다.랜덤 액세스 성능 및 메모리 소비에는 단일 연속 블록이 선호되지만 정기적으로 크기를 변경해야하는 컬렉션의 경우 일반적으로 Array와 같은 구조를 새 위치로 복사해야하지만 연결된 목록은 새로 삽입 된 메모리 만 관리하면됩니다. / 삭제 된 노드.
List와 LinkedList의 차이점은 기본 구현에 있습니다. List는 배열 기반 컬렉션 (ArrayList)입니다. LinkedList는 노드 포인터 기반 콜렉션 (LinkedListNode)입니다. API 레벨 사용법에서 ICollection, IEnumerable 등과 같은 동일한 인터페이스 세트를 구현하므로 둘 다 거의 동일합니다.
중요한 차이점은 성능이 중요합니다. 예를 들어 "INSERT"작업이 많은 목록을 구현하는 경우 LinkedList가 List보다 성능이 우수합니다. LinkedList는 O (1) 시간에이를 수행 할 수 있지만 List는 기본 배열의 크기를 확장해야 할 수도 있습니다. 자세한 정보 / 세부 사항은 LinkedList와 배열 데이터 구조의 알고리즘 차이를 읽으십시오. http://en.wikipedia.org/wiki/Linked_list 및 배열
이 도움을 바랍니다.
배열에 대한 링크 된 목록의 주요 장점은 링크가 항목을 효율적으로 재 배열 할 수있는 기능을 제공한다는 것입니다. 세지윅, p. 91
LinkedList를 사용하는 일반적인 상황은 다음과 같습니다.
크기가 큰 문자열 목록 (예 : 100,000)에서 많은 특정 문자열을 제거한다고 가정합니다. 제거 할 문자열은 HashSet dic에서 조회 할 수 있으며 문자열 목록에는 제거 할 문자열이 30,000-60,000 개 사이 인 것으로 생각됩니다.
그렇다면 100,000 개의 문자열을 저장하는 가장 좋은 유형의 목록은 무엇입니까? 답은 LinkedList입니다. 그것들이 ArrayList에 저장되어 있으면 그것을 반복하고 일치하는 문자열을 제거하는 데 최대 수십억 개의 연산을 취하는 반면 반복자와 remove () 메소드를 사용하면 약 10 만 개의 연산이 필요합니다.
LinkedList<String> strings = readStrings();
HashSet<String> dic = readDic();
Iterator<String> iterator = strings.iterator();
while (iterator.hasNext()){
String string = iterator.next();
if (dic.contains(string))
iterator.remove();
}
기본 제공 색인 액세스, 정렬 (및 이진 검색 후) 및 "ToArray ()"메소드가 필요한 경우 List를 사용해야합니다.
이것은 몇 가지 잘못된 측정을 수정하는 Tono Nam 의 승인 된 답변 에서 채택되었습니다 .
시험:
static void Main()
{
LinkedListPerformance.AddFirst_List(); // 12028 ms
LinkedListPerformance.AddFirst_LinkedList(); // 33 ms
LinkedListPerformance.AddLast_List(); // 33 ms
LinkedListPerformance.AddLast_LinkedList(); // 32 ms
LinkedListPerformance.Enumerate_List(); // 1.08 ms
LinkedListPerformance.Enumerate_LinkedList(); // 3.4 ms
//I tried below as fun exercise - not very meaningful, see code
//sort of equivalent to insertion when having the reference to middle node
LinkedListPerformance.AddMiddle_List(); // 5724 ms
LinkedListPerformance.AddMiddle_LinkedList1(); // 36 ms
LinkedListPerformance.AddMiddle_LinkedList2(); // 32 ms
LinkedListPerformance.AddMiddle_LinkedList3(); // 454 ms
Environment.Exit(-1);
}
그리고 코드 :
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
namespace stackoverflow
{
static class LinkedListPerformance
{
class Temp
{
public decimal A, B, C, D;
public Temp(decimal a, decimal b, decimal c, decimal d)
{
A = a; B = b; C = c; D = d;
}
}
static readonly int start = 0;
static readonly int end = 123456;
static readonly IEnumerable<Temp> query = Enumerable.Range(start, end - start).Select(temp);
static Temp temp(int i)
{
return new Temp(i, i, i, i);
}
static void StopAndPrint(this Stopwatch watch)
{
watch.Stop();
Console.WriteLine(watch.Elapsed.TotalMilliseconds);
}
public static void AddFirst_List()
{
var list = new List<Temp>();
var watch = Stopwatch.StartNew();
for (var i = start; i < end; i++)
list.Insert(0, temp(i));
watch.StopAndPrint();
}
public static void AddFirst_LinkedList()
{
var list = new LinkedList<Temp>();
var watch = Stopwatch.StartNew();
for (int i = start; i < end; i++)
list.AddFirst(temp(i));
watch.StopAndPrint();
}
public static void AddLast_List()
{
var list = new List<Temp>();
var watch = Stopwatch.StartNew();
for (var i = start; i < end; i++)
list.Add(temp(i));
watch.StopAndPrint();
}
public static void AddLast_LinkedList()
{
var list = new LinkedList<Temp>();
var watch = Stopwatch.StartNew();
for (int i = start; i < end; i++)
list.AddLast(temp(i));
watch.StopAndPrint();
}
public static void Enumerate_List()
{
var list = new List<Temp>(query);
var watch = Stopwatch.StartNew();
foreach (var item in list)
{
}
watch.StopAndPrint();
}
public static void Enumerate_LinkedList()
{
var list = new LinkedList<Temp>(query);
var watch = Stopwatch.StartNew();
foreach (var item in list)
{
}
watch.StopAndPrint();
}
//for the fun of it, I tried to time inserting to the middle of
//linked list - this is by no means a realistic scenario! or may be
//these make sense if you assume you have the reference to middle node
//insertion to the middle of list
public static void AddMiddle_List()
{
var list = new List<Temp>();
var watch = Stopwatch.StartNew();
for (var i = start; i < end; i++)
list.Insert(list.Count / 2, temp(i));
watch.StopAndPrint();
}
//insertion in linked list in such a fashion that
//it has the same effect as inserting into the middle of list
public static void AddMiddle_LinkedList1()
{
var list = new LinkedList<Temp>();
var watch = Stopwatch.StartNew();
LinkedListNode<Temp> evenNode = null, oddNode = null;
for (int i = start; i < end; i++)
{
if (list.Count == 0)
oddNode = evenNode = list.AddLast(temp(i));
else
if (list.Count % 2 == 1)
oddNode = list.AddBefore(evenNode, temp(i));
else
evenNode = list.AddAfter(oddNode, temp(i));
}
watch.StopAndPrint();
}
//another hacky way
public static void AddMiddle_LinkedList2()
{
var list = new LinkedList<Temp>();
var watch = Stopwatch.StartNew();
for (var i = start + 1; i < end; i += 2)
list.AddLast(temp(i));
for (int i = end - 2; i >= 0; i -= 2)
list.AddLast(temp(i));
watch.StopAndPrint();
}
//OP's original more sensible approach, but I tried to filter out
//the intermediate iteration cost in finding the middle node.
public static void AddMiddle_LinkedList3()
{
var list = new LinkedList<Temp>();
var watch = Stopwatch.StartNew();
for (var i = start; i < end; i++)
{
if (list.Count == 0)
list.AddLast(temp(i));
else
{
watch.Stop();
var curNode = list.First;
for (var j = 0; j < list.Count / 2; j++)
curNode = curNode.Next;
watch.Start();
list.AddBefore(curNode, temp(i));
}
}
watch.StopAndPrint();
}
}
}
다른 사람들이 여기에 문서화 된 이론적 성능에 따른 결과를 볼 수 있습니다. 매우 명확합니다- LinkedList<T>삽입시 큰 시간을 얻습니다. 나는 목록의 중간에서 제거를 테스트하지 않았지만 결과는 동일해야합니다. 물론 List<T>O (1) 랜덤 액세스와 같이 더 나은 성능을 발휘하는 다른 영역이 있습니다.
기본적 List<>으로 .NET의 배열 은 배열 의 래퍼 입니다. A LinkedList<> 는 연결된 목록 입니다. 따라서 문제는 배열과 연결 목록의 차이점과 연결 목록 대신 배열을 사용해야하는 시점에 있습니다. 아마 당신의 결정에있어서 가장 중요한 두 가지 요소는 :
- 삽입 / 제거가 컬렉션의 마지막 요소에 있지 않는 한 연결된 목록은 삽입 / 제거 성능이 훨씬 뛰어납니다. 배열이 삽입 / 제거 지점 다음에 나오는 나머지 모든 요소를 이동해야하기 때문입니다. 그러나 삽입 / 제거가 목록의 끝 부분에 있으면이 이동이 필요하지 않습니다 (용량을 초과하는 경우 배열의 크기를 조정해야 할 수도 있음).
- 어레이는 액세스 기능이 훨씬 뛰어납니다. 배열은 일정한 시간에 직접 색인을 생성 할 수 있습니다. 연결된 목록은 순회해야합니다 (선형 시간).
LinkedList<>때 사용
- 플러드 게이트를 통해 얼마나 많은 물체가 들어오는 지 모릅니다. 예를 들면 다음과 같습니다
Token Stream. - 끝 부분에서만 삭제 / 삽입하고 싶을 때.
다른 모든 것에는을 사용하는 것이 좋습니다 List<>.
위의 내용에 동의합니다. 또한 대부분의 경우 List가 더 확실한 선택 인 것 같습니다.
그러나 LinkedList가 효율을 높이기 위해 List보다 훨씬 나은 인스턴스가 많이 있다고 덧붙이고 싶습니다.
- 요소를 탐색하고 많은 삽입 / 삭제를 수행하려고한다고 가정하십시오. LinkedList는 선형 O (n) 시간으로 수행하는 반면 List는 2 차 O (n ^ 2) 시간으로 수행합니다.
- 더 큰 객체에 반복해서 액세스하려고한다고 가정하면 LinkedList가 더욱 유용 해집니다.
- Deque () 및 queue ()는 LinkedList를 사용하여 더 잘 구현됩니다.
- 더 큰 객체를 다루면 LinkedList의 크기를 늘리는 것이 훨씬 쉽고 좋습니다.
누군가가 이러한 의견이 도움이 되길 바랍니다.
여기에 많은 평균 답변이 있습니다 ...
일부 링크 된 목록 구현은 사전 할당 된 노드의 기본 블록을 사용합니다. 이들이 일정 시간 / 선형 시간보다이 작업을 수행하지 않으면 메모리 성능이 저하되고 캐시 성능이 훨씬 저하되므로 관련성이 떨어집니다.
다음과 같은 경우 링크 된 목록 사용
1) 나사산 안전을 원합니다. 더 나은 스레드 안전 알고리즘을 구축 할 수 있습니다. 잠금 비용은 동시 스타일 목록을 지배합니다.
2) 구조와 같은 큰 대기열이 있고 끝 부분을 제거하거나 항상 추가하려는 경우. > 100K 이상의 목록이 존재하지만 일반적이지 않습니다.
LinkedList 컬렉션의 성능과 관련 하여 비슷한 질문을 했고 Steven Cleary의 Deque C # 구현이 해결책이라는 것을 알았습니다 . 큐 컬렉션과 달리 Deque를 사용하면 항목을 앞뒤로 이동할 수 있습니다. 링크 된 목록과 비슷하지만 성능이 향상되었습니다.
참고 URL : https://stackoverflow.com/questions/169973/when-should-i-use-a-list-vs-a-linkedlist
'Programming' 카테고리의 다른 글
| Eclipse에서 불가능한 IntelliJ에서 가능한 것들? (0) | 2020.02.27 |
|---|---|
| 불변 위반 : _registerComponent (…) : 대상 컨테이너가 DOM 요소가 아닙니다 (0) | 2020.02.27 |
| Git 커밋 범위에서 더블 도트“..”와 트리플 도트“…”의 차이점은 무엇입니까? (0) | 2020.02.27 |
| bodyParser는 더 이상 사용되지 않습니다. express 4 (0) | 2020.02.27 |
| EC2 인스턴스의 키 페어 변경 (0) | 2020.02.27 |