Wann sollte ich eine Liste vs. eine LinkedList verwenden?

Question

Wann ist es besser, eine Liste gegen ein LinkedList ?

Answer 1

Der Unterschied zwischen List und LinkedList liegt in der zugrunde liegenden Implementierung. List ist eine Array-basierte Sammlung (ArrayList). LinkedList ist eine auf Knotenzeigern basierende Sammlung (LinkedListNode). Was die Verwendung auf API-Ebene betrifft, so sind beide ziemlich gleich, da beide dieselbe Reihe von Schnittstellen wie ICollection, IEnumerable usw. implementieren.

Der entscheidende Unterschied besteht darin, dass es auf die Leistung ankommt. Wenn Sie z. B. eine Liste implementieren, die eine umfangreiche "INSERT"-Operation erfordert, ist LinkedList besser als List. Da LinkedList dies in O(1)-Zeit erledigen kann, muss List möglicherweise die Größe des zugrunde liegenden Arrays erweitern. Für weitere Informationen/Details sollten Sie sich über den algorithmischen Unterschied zwischen LinkedList und Array-Datenstrukturen informieren. http://en.wikipedia.org/wiki/Linked_list y Array

Ich hoffe, das hilft,

Answer 2

Der Hauptvorteil von verknüpften Listen gegenüber Arrays besteht darin, dass die Verknüpfungen uns die Möglichkeit geben, die Elemente effizient neu anzuordnen. Sedgewick, S. 91

Answer 3

Eine übliche Situation für die Verwendung von LinkedList ist wie folgt:

Nehmen wir an, Sie möchten viele bestimmte Zeichenfolgen aus einer Liste von Zeichenfolgen mit einem großen Umfang, beispielsweise 100.000, entfernen. Die zu entfernenden Zeichenketten können im HashSet dic nachgeschlagen werden, und die Liste der Zeichenketten enthält vermutlich zwischen 30.000 und 60.000 solcher zu entfernender Zeichenketten.

Welche Art von Liste eignet sich dann am besten für die Speicherung von 100.000 Zeichenfolgen? Die Antwort lautet LinkedList. Wenn sie in einer ArrayList gespeichert werden, würde die Iteration darüber und das Entfernen übereinstimmender Strings bis zu Milliarden von Operationen erfordern, während die Verwendung eines Iterators und der remove()-Methode nur etwa 100.000 Operationen erfordert.

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();
}

Answer 4

Wenn Sie integrierten indizierten Zugriff, Sortierung (und danach binäre Suche) und die Methode "ToArray()" benötigen, sollten Sie List verwenden.

Answer 5

Im Wesentlichen ist ein List<> in .NET ist ein Wrapper über eine Array . A LinkedList<> ist eine verknüpfte Liste . Die Frage ist also, was der Unterschied zwischen einem Array und einer verknüpften Liste ist und wann ein Array anstelle einer verknüpften Liste verwendet werden sollte. Die beiden wichtigsten Faktoren bei der Entscheidung, welches Array Sie verwenden sollten, sind wahrscheinlich die folgenden:

• Bei verknüpften Listen ist die Leistung beim Einfügen/Entfernen wesentlich besser, solange das Einfügen/Entfernen nicht am letzten Element der Sammlung erfolgt. Das liegt daran, dass ein Array alle verbleibenden Elemente, die nach dem Einfüge-/Entfernungspunkt kommen, verschieben muss. Befindet sich der Einfüge-/Entnahmepunkt jedoch am Ende der Liste, ist diese Verschiebung nicht erforderlich (obwohl die Größe des Arrays möglicherweise angepasst werden muss, wenn seine Kapazität überschritten wird).
• Arrays haben viel bessere Zugriffsmöglichkeiten. In Arrays kann direkt indiziert werden (in konstanter Zeit). Verknüpfte Listen müssen durchlaufen werden (lineare Zeit).