Warum LinkedList in Java ist keine echte Linked List?

Question

Per Definition verlinkte Liste ist eine Liste, die jedes Element davon auf das nächste Element bezieht (und vorherige Element, wenn wir etwa doppelt verknüpften Liste sind talkin.) http://en.wikipedia.org/wiki/Linked_list

jedoch in Java LinkedList implementiert List, Queue, Deque und mehr.

Sie können keine Methode in LinkedList finden, die Ihnen das nächste oder vorherige Objekt in der Liste gibt, das Beste, was Sie tun können, ist einen Iterator zu bekommen und Objekte zu bekommen. Meine Frage ist, warum Java diese Datenstruktur LinkedList aufgerufen hat, obwohl es nicht wirklich eine verknüpfte Liste ist? Eine verkettete Liste kann in Java wie folgt umgesetzt werden:

Public class MyLinkedList{ 
public int value; 
public MyLinkedList next; 
} 

Answer 1

Meine Frage ist, warum Java diese Datenstruktur LinkedList genannt hat, während es ist nicht wirklich eine verknüpfte Liste?

Da die Implementierung davon eine verkettete Liste ist. Von the documentation:

doppelt verketteten Liste Umsetzung der List und Deque Schnittstellen. Implementiert alle optionalen Listenoperationen und erlaubt alle Elemente (einschließlich null).

LinkedList ist ein List über eine verknüpfte Liste implementiert, ArrayList ein List ist ein Array implementiert, usw., welche Sie in Bezug auf die Laufzeiteigenschaften Materie wählen können. Zum Beispiel aus dem LinkedList Dokument:

Alle Operationen führen, wie für eine doppelt verkettete Liste erwartet werden konnte. Operationen, die in der Liste indexieren, durchlaufen die Liste vom Anfang oder vom Ende, je nachdem, was näher am angegebenen Index liegt.

So wissen Sie, zum Beispiel, dass next auf dem Iterator Sie erhalten von iterator oder listIterator wird sehr effizient sein, aber die get von Index wird beinhalten Traversal.

Answer 2

Ob eine Auflistung eine verknüpfte Liste oder eine Array-Liste ist, geht es nicht um ihren Vertrag, sondern um ihre Implementierung. LinkedList ist in der Tat eine verkettete Liste durch die Implementierung und eine java.util.List durch Vertrag.

Wo es zeigt, ist nicht seine API, aber seine Raum/Zeit Komplexität Eigenschaften, die jeder mit einer verknüpften Liste vertrauten leicht voraussehen kann.

Als Referenz ist dies die tatsächliche Implementierung eines LinkedList Knoten, ein ziemlich gutes Spiel auf Ihre Erwartung:

957 privatestaticclass Node<E> {
958  E item;
959  Node <E> next;
960  Node <E> prev;
962  Node(Node <E> prev, E element, Node <E> next) {
963   this.item = element;
964   this.next = next;
965   this.prev = prev;
966  }
967 }

Answer 3

Sie keine Methode in LinkedList finden können, die Sie nächste oder vorherige Objekt gibt in die Liste

Nein, und das ist völlig angemessen.Die Idee "nächster Eintrag in einer Liste" macht keinen Sinn auf einer Liste. Es macht durchaus Sinn für einen Knoten innerhalb einer Liste, aber das ist nicht etwas, das durch die Java API offengelegt wird. Es ist natürlich intern vorhanden - nur nicht ausgesetzt. Wenn Sie über die Liste iterieren möchten, verwenden Sie einen Iterator. Sie können immer noch am Anfang oder Ende hinzufügen, vom Anfang oder Ende entfernen und dem Iterator hinzufügen/entfernen.

Während Sie sicherlich können conflate die Konzepte von "Knoten" und "Liste" wie Ihr vorgeschlagener Beispielcode tut, glaube ich nicht, dass es im Allgemeinen eine gute Idee ist.

Um es anders auszudrücken: Was versuchen Sie erreichen das verursacht Sie Probleme? Ich glaube, dass Sie in der Lage sein sollten, mit der öffentlichen API zu tun, was Sie wollen - Sie haben es vielleicht einfach nicht bemerkt.

Answer 4

Wenn die zugrunde liegende Implementierung der Schnittstelle eine verknüpfte Liste ist, verfügt das implementierende Objekt neben den richtigen Antworten der anderen über eine Methode zum Abrufen des nächsten Elements in der Liste. Diese Methode ist nicht als Teil des Vertrags verfügbar.

Die Tatsache, dass die Implementierung eine verknüpfte Liste ist, wirkt sich auf die Big-O-Leistung der verschiedenen Methoden des List-Vertrags aus.

Answer 5

In Java implementiert Linked List jedoch List, Queue, Deque und mehr.

Gemäß der API implementiert LinkedList diese Schnittstellen, so dass jede dieser Strukturen verwendet werden kann.

Answer 6

Als ich Ihre Frage durchgelesen habe, habe ich das Gefühl, dass Sie nicht zwischen dem Konzept der verketteten Liste und den Implementierungen der verketteten Liste unterscheiden konnten.

Ihr Beispielcode zeigte das Konzept der verketteten Liste sehr gut, aber das bedeutet nicht, dass es die einzige Möglichkeit oder der beste Weg ist, die verkettete Liste zu implementieren. Ich glaube, dass Sie alle Operationen ausführen können, die eine standardmäßige verknüpfte Liste unter Verwendung der integrierten Klasse LinkedList ausführt, obwohl Sie möglicherweise eine unbekannte Gruppe von APIs sehen, wie Sie sie in Ihrer Datenstrukturklasse oder Ihrem Lehrbuch sehen.

Also im Grunde ist es eine verkettete Liste, solange Sie Einfügevorgang in O(1) Zeit erreichen können, löschen Betrieb in O(1) Zeit, Suchoperation in O(n) Zeit usw., wie im Gegensatz zu der Zeit Komplexität von anderen Datenstrukturen als Array.

Die integrierte LinkedList lieferte die next Operation nicht direkt, sondern über ihren Iterator. Es war nur eine Designentscheidung der Programmiersprache Java, da Sie von der Iterator pattern profitieren könnten.

Und Java ist eine typische objektorientierte Sprache, eine der wichtigsten Eigenschaften ist Abstraction.