List vs Linked List를 사용해야 하는 경우
목록과 Linked List를 사용하는 것이 좋은 시기는 언제입니까?
의 경우, 「」는,List<T>더 유용합니다. LinkedList<T>목록 중간에 항목을 추가/삭제할 경우 비용이 절감됩니다.List<T>목록 끝에 추가/삭제만 저렴하게 할 수 있습니다.
LinkedList<T>순차적 데이터(앞으로 또는 뒤로)에 액세스하는 경우에만 가장 효율적입니다. 랜덤 액세스는 매번 체인을 통과해야 하므로 상대적으로 비용이 많이 듭니다(그래서 인덱서가 없는 이유).단, a, 냐 however '이기 List<T>는 기본적으로 (랩퍼가 있는) 어레이에 대해서만 랜덤액세스가 가능합니다.
List<T>방법을 합니다. - 아, 아, 아, 아, 아, 아, 아, 아, 아.Find,ToArray은 등니다 available에도 할 수 있습니다만만, 것이,,LinkedList<T>★★★★★★★★★★★★★★★★★★★★★★★★NET 3.5/C# 3.0 입니다.그 때문에, 이 점은 큰 요인이 되지 않습니다.
링크된 목록을 목록으로 생각하면 약간 오해의 소지가 있습니다.사슬쇠. . .에서는요. 물,,LinkedList<T>도 하지 않다IList<T>링크 리스트에는 실제 인덱스의 개념은 존재하지 않습니다.클래스에서 제공되는 메서드는 인덱스를 허용하지 않습니다.
링크 리스트는 단일 링크 또는 이중 링크 할 수 있습니다.이는 체인의 각 요소가 다음 요소에만 링크되는지(단일 링크됨) 또는 이전/다음 요소 모두에 링크되는지(복수 링크됨)를 나타냅니다. LinkedList<T>는 이중으로 연결되어 있습니다.
intern적 intern intern internList<T>는 어레이에 의해 백업됩니다.이것은 메모리의 매우 콤팩트한 표현을 제공합니다.로, ★★★★★★★★★★★★★★.LinkedList<T>에는 후속 요소 간의 양방향 링크를 저장하기 위한 추가 메모리가 포함되어 있습니다.메모리 풋프린트는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를 가리키도록 설정합니다.
링크된 목록의 단점은 랜덤 액세스가 불가능하다는 것입니다.멤버에 액세스하려면 원하는 멤버를 찾을 때까지 목록을 통과해야 합니다.
편집
이 답변에 대한 댓글을 읽어주세요.사람들은 내가 제대로 된 검사를 하지 않았다고 주장한다.나는 이것이 받아들여지지 않아야 한다는 것에 동의한다.저는 배우면서 몇 가지 테스트를 했고 그것들을 공유하고 싶었습니다.
원답...
흥미로운 결과를 발견했습니다.
// 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;
기본적으로 데이터만 접근해도 훨씬 느려요!!linked List를 사용하지 마십시오.
삽입을 많이 한 다른 비교입니다(목록 중간에 아이템을 삽입할 예정입니다).
링크 리스트(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;
따라서 여러 항목을 삽입할 계획이며 항목을 삽입할 예정 위치에 대한 참조가 있는 경우에만 링크 목록을 사용하십시오.많은 아이템을 삽입해야 한다고 해서 삽입하고 싶은 장소를 검색하는 데 시간이 걸리기 때문에 더 빨라지는 것은 아닙니다.
나의 이전 답변은 정확하지 않았다.정말 끔찍했어요:D 하지만 이제 나는 훨씬 더 유용하고 정확한 답을 올릴 수 있어요.
나는 몇 가지 추가 테스트를 했다.다음 링크에서 소스 정보를 찾을 수 있습니다.또, https://github.com/ukushu/DataStructuresTestsAndOther.git 를 참조해 주세요.
짧은 결과:
어레이의 필요성:
- 가능한 한 자주.고속으로 같은 양의 정보를 얻기 위해 최소 RAM 범위를 사용합니다.
- 필요한 세포의 정확한 수를 알고 있다면
- 어레이에 저장된 데이터가 85000 b 미만인 경우(정수 데이터의 경우 85000/32 = 2656 요소)
- 고속 랜덤 액세스 속도가 필요한 경우
사용할 목록:
- 목록 끝에 셀을 추가해야 하는 경우(대부분)
- 리스트의 선두/중간에 셀을 추가할 필요가 있는 경우(자주 추가하지 않음
- 어레이에 저장된 데이터가 85000 b 미만인 경우(정수 데이터의 경우 85000/32 = 2656 요소)
- 고속 랜덤 액세스 속도가 필요한 경우
Linked List는 다음을 사용해야 합니다.
- 목록의 시작/중간/끝에 셀을 추가해야 하는 경우(대부분)
- 시퀀셜 액세스만 필요한 경우(전진/후진)
- 큰 아이템을 저장해야 하는데 아이템 수가 적은 경우.
- 링크용 메모리를 추가로 사용하기 때문에 대량의 아이템에는 사용하지 않는 것이 좋습니다.
상세:
흥미로운 점은 다음과 같습니다.
LinkedList<T>은 .internal의. . 구현조차 되지 않습니다.IList<T>그렇기 때문에 인덱스와 관련된 메서드나 인덱스가 존재하지 않습니다.LinkedList<T>는 노드 스위칭 기반 수집입니다.입니다.NET ★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★」 선행/는 현재.데이터는 단편화됩니다.다른 리스트 오브젝트를 RAM의 다른 장소에 배치할 수 있습니다. ,, 다, 보, 보, 보, 보, 보, used, used, used, used, used, used, used, used, also, used, also, also, also, alsoLinkedList<T>을 for thanList<T>아니면 어레이또는 어레이.List<T>.Net은 자바의 대안이다.Net은 Java의 대체 수단입니다.ArrayList<T>. 이것은 어레이 래퍼입니다.이는 어레이 래퍼임을 의미합니다.따라서 데이터. , 데이터. 모 리 이 속 록 당 so it할블 as다 block'니연 cont로 data됩 in of으데된iguous memory의터 allocated에s one즉메Large Object Heap(대형 객체 힙)이 있습니다.사이즈에 따라서는, 히프 플래그멘테이션(메모리 누수의 가벼운 형태)이 발생할 가능성이 있습니다. size < bytes 메모리내의 액세스 합니다.랜덤 액세스 퍼포먼스와 메모리 소비량에는 연속된 단일 블록을 사용하는 것이 좋습니다.다만, 일반적으로 어레이등의 구조를 새로운 장소에 카피할 필요가 있는 컬렉션에서는, 링크 리스트에서는, 새로 삽입 또는 삭제한 노드의 메모리만을 관리할 필요가 있습니다.
List와 LinkedList의 차이점은 기본 구현에 있습니다.목록은 어레이 기반 컬렉션(ArrayList)입니다.Linked List는 노드 포인터 기반 컬렉션(Linked List Node)입니다.API 레벨의 사용법에서는 양쪽 모두 ICollection, IEnumerable 등의 동일한 인터페이스 세트를 구현하기 때문에 거의 동일합니다.
중요한 차이는 퍼포먼스가 중요한 경우입니다.예를 들어 "INSERT" 작업이 많은 목록을 구현하는 경우 LinkedList가 목록보다 성능이 우수합니다.Linked List는 O(1) 시간 내에 실행할 수 있지만 List는 기본 어레이 크기를 확장해야 할 수 있습니다.자세한 내용은 LinkedList와 어레이 데이터 구조 간의 알고리즘 차이에 대해 자세히 읽어보시기 바랍니다.http://en.wikipedia.org/wiki/Linked_list 및 어레이
이게 도움이 됐으면 좋겠는데
어레이에 비해 링크 리스트의 주요 장점은 링크를 통해 항목을 효율적으로 재배치할 수 있다는 것입니다.세지윅, 페이지 91
Linked List를 사용하는 일반적인 상황은 다음과 같습니다.
크기가 큰 문자열 목록에서 특정 문자열을 많이 제거한다고 가정합니다(예: 100,000).삭제할 문자열은 HashSet dic에서 조회할 수 있습니다.이 문자열 목록에는 삭제할 문자열이 30,000~60,000개 포함되어 있는 것으로 생각됩니다.
그렇다면 100,000개의 문자열을 저장하는 데 가장 적합한 유형의 리스트는 무엇일까요?정답은 Linked List입니다.이러한 문자열이 ArrayList에 저장되어 있는 경우 반복하여 일치하는 문자열을 삭제하면 최대 수십억 번의 조작이 소요되지만 반복자 및 remove() 메서드를 사용하여 약 100,000회의 조작이 소요됩니다.
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를 사용해야 합니다.
「」입니다.List<>.NET은 어레이 위의 래퍼입니다.aLinkedList<> 는 링크 리스트입니다.따라서 어레이와 링크드 리스트의 차이점은 무엇이며, 링크드 리스트 대신 어레이를 사용해야 하는 시점이 문제입니다.사용할 결정을 내릴 때 가장 중요한 두 가지 요소는 다음과 같습니다.
- 삽입/제거가 컬렉션의 마지막 요소에 없는 한 링크된 목록은 삽입/제거 성능이 훨씬 우수합니다.이는 배열이 삽입/제거 지점 뒤에 오는 나머지 모든 요소를 이동해야 하기 때문입니다.그러나 삽입/탈부착이 목록의 끝에 있는 경우에는 이 이동이 필요하지 않습니다(용량을 초과한 경우 어레이 크기를 변경해야 할 수도 있습니다).
- 어레이는 액세스 기능이 훨씬 우수합니다.어레이를 직접 인덱싱할 수 있습니다(정시).링크된 목록을 통과해야 합니다(선형 시간).
이는 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();
}
}
}
결과는 다른 사용자가 여기에 기록한 이론적인 성능에 따른 것임을 알 수 있습니다.맑다 - 우우 quite quite quite quite quite quite quite quite quite quite quite 。LinkedList<T>삽입 시 큰 시간을 벌 수 있습니다.리스트의 중간에서 삭제하기 위한 테스트는 실시하지 않았지만 결과는 같습니다.입니다.List<T>에는 O(1) 랜덤액세스와 같이 퍼포먼스가 뛰어난 영역이 있습니다.
LinkedList<> 때
- 얼마나 많은 물체가 수문을 통해 들어오고 있는지 당신은 모른다.를 들어, 「」라고 하는 것은,
Token Stream. - 마지막에만 삭제 및 삽입을 원하는 경우.
외에는 다 .List<>.
나는 위에서 말한 대부분의 요점에 동의한다.그리고 대부분의 경우 리스트가 더 확실한 선택으로 보인다는 것도 동의합니다.
다만, Linked List가 List보다 효율이 훨씬 뛰어난 경우가 많다는 것을 덧붙이고 싶습니다.
- 요소를 통과하여 삽입/삭제 로트를 실행하는 경우 Linked List는 선형 O(n)시간으로 처리하지만 List는 2차 O(n^2)시간으로 처리합니다.
- 더 큰 오브젝트에 몇 번이고 액세스 하고 싶다고 하면 Linked List가 매우 편리해집니다.
- Deque() 및 queue()는 Linked List를 사용하여 구현이 용이합니다.
- Linked List의 크기를 늘리는 것은 더 크고 많은 개체를 처리할 때 훨씬 쉽고 더 좋습니다.
누군가 이 코멘트를 유용하게 여겨주길 바랍니다.
.NET에서는 목록은 배열로 표시됩니다.따라서 일반 목록을 사용하는 것이 Linked List에 비해 상당히 빠릅니다.그것이 바로 위의 사람들이 그들이 보는 결과를 보는 이유이다.
목록을 사용해야 하는 이유는 무엇입니까?상황에 따라 다르죠지정된 요소가 없는 경우 List는 4개의 요소를 만듭니다.이 제한을 초과하면 새 배열에 항목이 복사되고 이전 배열은 가비지 컬렉터에 맡겨집니다.그런 다음 크기를 두 배로 늘립니다.이 경우 8개의 요소가 포함된 새 배열을 만듭니다.100만 개의 요소가 포함된 목록이 있고 하나 더 추가된다고 가정해 보십시오.기본적으로 필요한 크기의 완전히 새로운 어레이가 생성됩니다.새로운 어레이의 용량은 2 Mill이지만, 필요한 용량은 1 Mil과 1 Mil뿐이었습니다.기본적으로 GEN2에 쓰레기 수집기 등을 위해 물건을 남겨두는 것입니다.따라서 실제로는 큰 병목현상이 될 수 있습니다.당신은 그것을 조심해야 합니다.
Linked List 컬렉션의 퍼포먼스에 대해서도 같은 질문을 했는데 Steven Cleary의 Deque C# 구현이 해결책이었습니다.큐 컬렉션과 달리 Deque는 앞뒤로 항목을 이동할 수 있습니다.링크 목록과 비슷하지만 성능이 향상되었습니다.
언급URL : https://stackoverflow.com/questions/169973/when-should-i-use-a-list-vs-a-linkedlist
'prosource' 카테고리의 다른 글
| 잘못된 Git 브랜치에 대한 커밋을 수정하려면 어떻게 해야 합니까? (0) | 2023.04.13 |
|---|---|
| 사전 목록에 값이 이미 있는지 확인하시겠습니까? (0) | 2023.04.13 |
| WPF에서 마우스 이벤트에 대해 제어를 투과적으로 하는 방법이 있습니까? (0) | 2023.04.13 |
| SQL Server에서 bigint(UNIX 타임스탬프)를 datetime으로 변환하려면 어떻게 해야 합니까? (0) | 2023.04.13 |
| 두 리비전 간에 변경된 파일 표시 (0) | 2023.04.13 |