ListとLinkedListのどちらを使用する方が良いですか?
Grauenwolf
質問する
261898 次
15 に答える
302
ほとんどの場合、 のList<T>方が便利です。LinkedList<T>リストの途中でアイテムを追加/削除するとコストが低くなりますが、リストの最後List<T>でのみ安価に追加/削除できます。
LinkedList<T>シーケンシャル データ (順方向または逆方向) にアクセスしている場合にのみ最も効率的です。ランダム アクセスは、毎回チェーンをたどる必要があるため、比較的高価です (したがって、インデクサーがない理由)。ただし、 aList<T>は本質的に単なる配列 (ラッパーを使用) であるため、ランダム アクセスは問題ありません。
List<T>Find、などの多くのサポート方法も提供していますToArray。ただし、これらはLinkedList<T>拡張メソッドを介して .NET 3.5/C# 3.0 でも利用できるため、それほど重要ではありません。
于 2008-10-04T08:28:41.717 に答える
239
リンクされたリストをリストと考えると、少し誤解を招く可能性があります。それはチェーンのようなものです。実際、.NET では、LinkedList<T>実装すらしていませんIList<T>。リンクされたリストには、あるように見えるかもしれませんが、実際にはインデックスの概念はありません。確かに、クラスで提供されているメソッドはどれもインデックスを受け入れません。
リンクされたリストは、一重にリンクされている場合と、二重にリンクされている場合があります。これは、チェーン内の各要素が次の要素へのリンクのみを持っているか (単一リンク)、または前/次の要素の両方へのリンクを持っているか (二重リンク) を示します。 LinkedList<T>二重にリンクされています。
内部的にList<T>は、配列によってサポートされています。これにより、メモリ内で非常にコンパクトな表現が提供されます。逆に、LinkedList<T>連続する要素間の双方向リンクを格納するために追加のメモリが必要です。そのため、a のメモリ フットプリントはLinkedList<T>一般に for よりも大きくなります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>リスト内の余分なアイテムは、挿入/削除後にシャッフルする必要があるため、線形時間を提供します。
于 2011-10-15T11:58:03.047 に答える
118
リンクされたリストは、リスト メンバーの非常に高速な挿入または削除を提供します。リンクされたリストの各メンバーには、リストの次のメンバーへのポインターが含まれているため、位置 i にメンバーを挿入します。
- メンバー i-1 のポインターを更新して、新しいメンバーを指すようにします
- メンバーiを指すように新しいメンバーにポインタを設定します
リンク リストの欠点は、ランダム アクセスができないことです。メンバーにアクセスするには、目的のメンバーが見つかるまでリストをトラバースする必要があります。
于 2008-10-04T08:34:23.983 に答える
111
編集
この回答へのコメントを読んでください。人々は私が適切なテストをしなかったと主張します。これは受け入れられる答えであってはならないことに同意します。学びながら、いくつかのテストを行い、それらを共有したいと感じました。
元の答え...
興味深い結果が見つかりました:
// 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;
したがって、複数のアイテムを挿入する予定があり、アイテムを挿入する予定の場所の参照がどこかにある場合にのみ、リンクされたリストを使用してください。多くのアイテムを挿入する必要があるからといって、挿入したい場所を検索するのに時間がかかるため、高速にはなりません.
于 2012-09-17T20:47:37.900 に答える
20
List と LinkedList の違いは、基礎となる実装にあります。List は配列ベースのコレクション (ArrayList) です。LinkedList は、ノード ポインター ベースのコレクション (LinkedListNode) です。API レベルの使用法では、どちらも ICollection や IEnumerable などの同じ一連のインターフェイスを実装しているため、どちらもほとんど同じです。
主な違いは、パフォーマンスが重要な場合です。たとえば、「INSERT」操作が多いリストを実装している場合、LinkedList は List よりも優れています。LinkedList は O(1) 時間で実行できるため、List は基になる配列のサイズを拡張する必要がある場合があります。詳細については、LinkedList と配列データ構造のアルゴリズムの違いについて調べてください。http://en.wikipedia.org/wiki/Linked_listと配列
この助けを願って、
于 2008-10-04T08:35:55.523 に答える
12
配列よりもリンクされたリストの主な利点は、リンクによってアイテムを効率的に再配置できることです。セジウィック、p。91
于 2012-11-25T08:52:14.643 に答える
4
LinkedList を使用する一般的な状況は次のようなものです。
大きなサイズ (たとえば 100,000) の文字列のリストから多くの特定の文字列を削除したいとします。削除する文字列は HashSet dic で検索できます。文字列のリストには、削除する文字列が 30,000 ～ 60,000 個含まれていると考えられています。
では、100,000 個の文字列を格納するのに最適なリストの型は何でしょうか? 答えは LinkedList です。それらが 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();
}
于 2014-08-19T12:47:02.687 に答える
2
組み込みのインデックス アクセス、並べ替え (およびこのバイナリ検索の後)、および "ToArray()" メソッドが必要な場合は、List を使用する必要があります。
于 2008-10-04T08:27:29.660 に答える
1
これは、いくつかの間違った測定値を修正する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) ランダム アクセスのようにパフォーマンスが向上する他の領域もあります。
于 2014-07-03T00:29:50.477 に答える
0
使用するLinkedList<>場合
- 水門を通過するオブジェクトの数はわかりません。たとえば、
Token Stream. - 最後にのみ削除\挿入したい場合。
それ以外の場合は、 を使用することをお勧めしますList<>。
于 2012-11-23T16:24:44.510 に答える