Im vorherigen Artikel haben wir die zugrunde liegende Implementierung von ArrayList analysiert und wussten, dass die zugrunde liegende Implementierung von ArrayList auf Arrays basiert, sodass sie die Eigenschaften der schnellen Suche und Änderung haben, während ein langsames Einfügen und Löschen. Die in diesem Artikel eingeführte LinkedList ist eine weitere Implementierung der Listenschnittstelle. Die zugrunde liegende Schicht basiert auf einer bidirektionalen verknüpften Liste. Daher hat es die Eigenschaften eines schnellen Einfüges und Löschens bei langsamer Suche und Änderung. Darüber hinaus können die Funktionen von Warteschlangen und Stapeln durch den Betrieb der bidirektionalen verknüpften Liste realisiert werden. Die zugrunde liegende Struktur der LinkedList ist in der folgenden Abbildung dargestellt.
F repräsentiert die Kopfknotenreferenz, L repräsentiert die Heckknotenreferenz, und jeder Knoten in der verknüpften Liste hat drei Elemente, nämlich die Vorwärtsknotenreferenz (P), den Node -Element -Wert (e) und die nachfolgende Knotenreferenz (n). Der Knoten wird vom Knoten der inneren Klasse dargestellt, schauen wir uns seine interne Struktur an.
// Node Internal Class private statische Klassenknoten <e> {e item; // Element Node <e> als nächstes; // Nächster Knotenknoten <e> pre; // vorheriger Knotenknoten (Knoten <e> prev, e Element, Knoten <e> next) {this.iTEM = Element; this.Next = Weiter; this.prev = prev; }}Der interne Klassenknoten ist tatsächlich sehr einfach, mit nur drei Mitgliedsvariablen und einem Konstruktor. Das Element repräsentiert den Wert des Knotens, als nächstes ist die Referenz auf den nächsten Knoten, und die Präv ist der Verweis auf den vorherigen Knoten. Diese drei Werte werden durch den Konstruktor weitergegeben. Schauen wir uns als nächstes die Mitgliedervariablen und Konstrukteure von LinkedList an.
// Die Anzahl der festgelegten Elemente wird übersetzt int size = 0; // Der Header -Knoten referenziert transienter Knoten <e> zuerst; // Der Tail -Knoten referenziert transienten Knoten <e> letztes; // Der parameterlose Konstruktor Public LinkedList () {} // Der Konstruktor, der in die externe Sammlung verlinkte Linkedlist (Collection <) {{this this) {this {this (). Addall (c);}LinkedList enthält einen Verweis auf den Headerknoten und einen Verweis auf den Heckknoten. Es hat zwei Konstruktoren, einer ist ein parameterloser Konstruktor und der andere ist ein Konstruktor, der an die externe Sammlung übergeben wird. Im Gegensatz zu ArrayList gibt LinkedList nicht den Konstruktor der anfänglichen Größengrößen an. Sehen Sie sich die Methoden zum Hinzufügen, Löschen, Ändern und Suchen an.
// add (add) public boolean add (e e) {// linkLast (e) hinzufügen; return true;} // add (einfügen) public void add (int index, e element) {pechpositionIndex (index); if (index == Größe) {// linkLast (Element) hinzufügen; } else {// linkBefore einfügen (Element, Knoten (Index)); }} // löschen (geben index) public e remove (int index) {// prüfen, ob das Einweis legal checkElementIndex (Index) ist; return Unlink (node (index));} // Löschen (gegebenes Element) public boolean entfernen (Objekt o) {if (o == null) {for (node <e> x = zuerst; x! zurückkehren; }}} else {// Ruheverbindungsliste für (Knoten <e> x = zuerst; x! zurückkehren; }}} return false;} // public e set (int Index, E -Element) {// prüfen, ob das Einweis legal checkElementIndex (Index) ist; // Die Knotenreferenz des angegebenen SubScript -Knotens <E> x = node (Index) abrufen; // Erhalten Sie den Wert des angegebenen Indexknotens e oldval = x.item; // Setzen Sie das Knotenelement auf das neue Wert X.Item = Element; // Die vorherige Wertrückgabe oldval zurückgeben;} // public e get (int Index) {// prüfen, ob das Einweis legal checkElementIndex (Index) ist; // Rückgabe des Wertes des Knotens des angegebenen Abschlussrückgabeknotens (Index) .Item;}Die Methode zum Hinzufügen von Elementen in LinkedList besteht hauptsächlich darin, die beiden Methoden LinkLast und LinkBefore aufzurufen. Die LinkLast -Methode besteht darin, ein Element hinter der verknüpften Liste zu verknüpfen, und die LinkBefore -Methode besteht darin, ein Element in der Mitte der verknüpften Liste einzufügen. Die Löschmethode der LinkedList entfernt ein Element aus der verknüpften Liste, indem sie die Unlink -Methode aufruft. Schauen wir uns den Kerncode der Insertion- und Löschvorgänge der verknüpften Liste an.
// Vor dem Verknüpfen mit dem angegebenen Knoten void linkBefore (e e, Knoten <e> prof) {// den vorherigen Knotenreferenz des angegebenen Knotens endgültiger Knoten <e> pred = scc.prev abrufen; // Erstellen Sie einen neuen Knoten, die vorherige Knotenreferenz des neuen Knotens verweist auf den vorherigen Knoten des angegebenen Knotens // auf die Referenz des nächsten Knotens des neuen Knotens zeigt auf den gegebenen Knoten endgültiger Knoten <e> newnode = neuer Knoten <> (Pred, E, Eurne); // Zeigen Sie den vorherigen Knotenreferenz des angegebenen Knotens auf den neuen Knoten procc.prev = newnode; // Wenn der vorherige Knoten des angegebenen Knotens leer ist, bedeutet dies, dass der angegebene Knoten der Header -Knoten ist, wenn (pred == null) {// den Header -Knoten auf den neuen Knoten first = newnode Punkt; } else {// ansonsten zeig auf den nächsten Knotenverweis auf den neuen Knoten Pred.Next = newnode; } // die Anzahl der festgelegten Elemente eins Größe ++ hinzufügen; // Fügen Sie die Anzahl der Modifikationen hinzu und modCount ++; } // Entladen Sie den angegebenen Knoten E Unlink (Knoten <e> x) {// Erhalten Sie das Element des angegebenen Knotens Final E Element = X.Item; // Erhalten Sie den Verweis auf den nächsten Knoten des angegebenen Knotens Final Node <e> next = x.Next; // Erhalten Sie den Verweis auf den vorherigen Knoten des angegebenen Knotens endgültigen Knoten <e> prew = x.prev; // Wenn der vorherige Knoten des angegebenen Knotens leer ist, ist Erläuterung: Der angegebene Knoten ist ein Header -Knoten, wenn (prev == null) {// Punkt den Header -Knoten auf den nächsten Knoten des angegebenen Knotens first = next; } else {// Referenz auf den Nachfolgerknoten des vorherigen Knotens, der auf den nachfolgenden Knoten des angegebenen Knotens prev.Next = next zeigt; // Verweisen Sie auf den vorherigen Knoten des angegebenen Knotens x.prev = null; } // Wenn der nächste Knoten des angegebenen Knotens leer ist, bedeutet dies, dass der angegebene Knoten ein Heckknoten ist, wenn (next == null) {// den Heckknoten auf den vorherigen Knoten des angegebenen Knotens last = prev; } else {// Referenz auf den Vorwärtsknoten des nächsten Knotens, der auf den vorherigen Knoten des angegebenen Knotens als nächstes zeigt. X.Next = null; } // das Element des angegebenen Knotens x.Item = null; // die Anzahl der festgelegten Elemente nach Größe subtrahieren; // ModCount ++ hinzufügen; Rückgabeelement;} LinkBefore und UNLINK sind repräsentative Operationen von Verknüpfen von Knoten und Deinstallieren von Knoten. Andere Methoden zur Verknüpfung und Deinstallation von Knoten an beiden Enden sind ähnlich. Daher konzentrieren wir uns auf LinkBefore- und Unglied -Methoden.
Prozessdiagramm der Linkbefore -Methode:
Prozessdiagramm der Unvertink -Methode:
Durch die obige Abbildung ist die zeitliche Komplexität der Einfügungs- und Löschvorgänge der verknüpften Liste O (1), und die Such- und Änderungsvorgänge der verlinkten Liste erfordern das Durchqueren der verlinkten Liste, um Elemente zu finden. Beide Operationen werden als Node (int Index) -Methode bezeichnet, um Elemente zu lokalisieren, um zu sehen, wie Elemente über Einweisungen lokalisiert werden.
// Node Node <E> Knoten (int index) {// Wenn der Index in der ersten Hälfte der verlinkten Liste befindet, überprüfen Sie von Anfang an if if (Index <(Größe >> 1)) {Knoten <e> x = zuerst; für (int i = 0; i <index; i ++) {x = x.Next; } return x; } else {// Wenn sich der Index in der zweiten Hälfte der verlinkten Liste befindet, überprüfen Sie vom Endknoten <e> x = letztes; für (int i = size-1; i> index; i--) {x = x.prev; } return x; }} Stellen Sie beim Positionieren des Index zuerst fest, ob es sich in der oberen Hälfte oder in der unteren Hälfte der verknüpften Liste befindet. Wenn es in der oberen Hälfte ist, beginnen Sie von Anfang an und wenn es die untere Hälfte ist, beginnen Sie vom Ende. Daher ist die zeitliche Komplexität des Suchens und Änderns des Indexs O (N/2). Durch den Betrieb der bidirektionalen verknüpften Liste können auch die Funktionen von Einzel-Elementen-Warteschlangen, Zwei-Wege-Warteschlangen und Stapeln realisiert werden.
Einweg-Warteschlangenbetrieb:
// den Header Knoten public e peek () {endgültiger Knoten <e> f = zuerst; return (f == null)? NULL: F.Item;} // den Header -Knoten public e element () {return getfirst ();} // Pop Up den Header Knode public e poll () {Final Node <e> f = zuerst; return (f == null)? NULL: UNLINKFIRST (F);} // den Header Knoten public e remove () {return remefirst ();} // Knoten am Ende des Warteschlangens öffentliches Boolean -Angebot (e) {return add (e);} hinzufügen;Zwei-Wege-Warteschlangenbetrieb:
// public boolean offerFirst (e e) {addfirst (e); return true;} // public boolean offerLast (e e) {addlast (e); return true;} // den Header Knoten public e peekfirst () {endgültiger Knoten <e> f = zuerst; return (f == null)? NULL: F.Item; } // den Tail Node public e peeklast () {endgültiger Knoten <e> l = letztes; return (l == null)? NULL: L.Item;}Stack -Betrieb:
// Das Stack Public void push (e e) {addfirst (e);} // Setzen Sie den Stack public e pop () {return remyfirst ();} Egal, ob es sich um eine Einweg-Warteschlange, eine Zwei-Wege-Warteschlange oder ein Stapel handelt, sie arbeiten tatsächlich auf den Kopf- und Heckknoten der verknüpften Liste. Ihre Implementierungen basieren auf den vier Methoden: addfirst (), addlast (), removeFirst () und removelast (). Ihre Operationen ähneln LinkBefore () und Unlink (), außer dass einer an beiden Enden der verknüpften Liste betrieben werden soll und der andere in der Mitte der verlinkten Liste operieren soll. Es kann gesagt werden, dass diese vier Methoden spezielle Fälle von LinkBefore () und Unlink () sind, daher ist es nicht schwierig, ihre internen Implementierungen zu verstehen, sodass ich sie hier nicht vorstellen werde. Zu diesem Zeitpunkt steht unsere Analyse von LinkedList kurz vor dem Ende, und wir werden die wichtigsten Punkte im gesamten Text zusammenfassen:
1. LinkedList wird basierend auf einer Zwei-Wege-Link-Liste implementiert. Unabhängig davon, ob es sich um Hinzufügung, Lösch-, Änderungs- und Suchmethode oder die Implementierung von Warteschlangen und Stapeln handelt, kann sie über Operationsknoten implementiert werden.
2. LinkedList muss nicht im Voraus Kapazitäten angeben, da die Kapazität der Sammlung basierend auf verknüpften Listenvorgängen durch die Zugabe von Elementen automatisch erhöht wird.
3. Die von der Sammlung nach der LinkedList gelöschte Speicher wird automatisch reduziert und es ist nicht erforderlich, die methode trimToSize () wie ArrayList aufzurufen
V.
5. Die obige Analyse basiert auf JDK1.7, und andere Versionen haben einige Unterschiede, sodass sie nicht verallgemeinert werden kann.
Das obige ist der gesamte Inhalt dieses Artikels. Ich hoffe, es wird für das Lernen aller hilfreich sein und ich hoffe, jeder wird Wulin.com mehr unterstützen.