Share
Die erste Datenstruktur, die wir betrachten werden, ist die verknüpfte Liste, und das aus gutem Grund. Sie ist nicht nur eine nahezu allgegenwärtige Struktur, die von Betriebssystemen bis hin zu Videospielen verwendet wird, sondern ist auch ein Baustein, mit dem viele andere Datenstrukturen erstellt werden können.
In einem sehr allgemeinen Sinn besteht der Zweck einer verknüpften Liste darin, einen konsistenten Mechanismus zum Speichern und Zugreifen auf eine beliebige Datenmenge bereitzustellen. Wie der Name schon sagt, werden die Daten zu einer Liste zusammengefügt.
Bevor wir uns damit beschäftigen, betrachten wir zunächst, wie Daten in einem Array gespeichert werden.
Ganzzahlige Daten, die in einem Array gespeichert sind Wie die Abbildung zeigt, werden Array-Daten als ein einzeln zusammenhängender Speicherblock gespeichert, der logisch segmentiert ist. Die im Array gespeicherten Daten werden in einem dieser Segmente abgelegt und über ihre Position oder ihren Index im Array referenziert.
Dies ist ein guter Weg, um Daten zu speichern. Die meisten Programmiersprachen machen es sehr einfach, Arrays zuzuordnen und deren Inhalte zu bearbeiten. Angrenzende Datenspeicherung bietet Leistungsvorteile (nämlich Datenlokalität), das Durchlaufen der Daten ist einfach und der Zugriff auf die Daten ist durch Index (Direktzugriff) in konstanter Zeit möglich.
Es gibt jedoch Zeiten, in denen ein Array nicht die ideale Lösung ist.
Betrachten Sie ein Programm mit den folgenden Anforderungen:
Accentsconagua
NextValue method) bis die Nummer 0xFFFF gefunden wird.ProcessItems Methode.Da die Anforderungen darauf hinweisen, dass mehrere Werte an die übergeben werden müssen ProcessItems Methode in einem einzigen Aufruf. Eine naheliegende Lösung wäre die Verwendung eines Arrays von Ganzzahlen. Zum Beispiel:
void LoadData () // Angenommen, 20 reicht aus, um die Werte aufzunehmen. int [] -Werte = new int [20]; für (int i = 0; i < values.Length; i++) if (values[i] == 0xFFFF) break; values[i] = NextValue(); ProcessItems(values); void ProcessItems(int[] values) //… Process data.
Diese Lösung hat mehrere Probleme, aber am deutlichsten wird es, wenn mehr als 20 Werte gelesen werden. Da das Programm jetzt ist, werden die Werte von 21 bis n einfach ignoriert. Dies kann durch die Zuweisung von mehr als 20 Werten (vielleicht 200 oder 2000) gemindert werden. Möglicherweise wird die Größe vom Benutzer konfiguriert, oder wenn das Array voll ist, kann ein größeres Array zugewiesen und alle vorhandenen Daten in dieses Feld kopiert werden. Letztendlich schaffen diese Lösungen Komplexität und verschwenden Speicher.
Was wir brauchen, ist eine Auflistung, mit der wir eine beliebige Anzahl von Integerwerten hinzufügen und diese Integer in der Reihenfolge auflisten können, in der sie hinzugefügt wurden. Die Sammlung sollte keine feste maximale Größe haben, und die Indizierung mit wahlfreiem Zugriff ist nicht erforderlich. Was wir brauchen, ist eine verknüpfte Liste.
Bevor wir fortfahren und erfahren, wie die Datenstruktur der verknüpften Liste entworfen und implementiert wird, lassen Sie uns eine Vorschau anzeigen, wie unsere ultimative Lösung aussehen könnte.
static void LoadItems () LinkedList list = new LinkedList (); while (true) int value = NextValue (); if (value! = 0xFFFF) list.Add (value); else break; ProcessItems (Liste); static void ProcessItems (LinkedList-Liste) //… Prozessdaten.
Beachten Sie, dass alle Probleme mit der Array-Lösung nicht mehr bestehen. Es gibt keine Probleme mehr, wenn das Array nicht groß genug ist oder mehr zuordnet, als nötig ist.
Sie sollten auch beachten, dass diese Lösung einige der Entwurfsentscheidungen enthält, die wir später treffen werden, nämlich die LinkedList Die Klasse akzeptiert ein generisches Typargument und implementiert das IEnumerable Schnittstelle.
Der Kern der Datenstruktur der verknüpften Liste ist die Klasse Node. Ein Knoten ist ein Container, der die Möglichkeit bietet, Daten zu speichern und Verbindungen zu anderen Knoten herzustellen.
Ein verknüpfter Listenknoten enthält Daten und eine Eigenschaft, die auf den nächsten Knoten zeigen In ihrer einfachsten Form könnte eine Knotenklasse, die Ganzzahlen enthält, folgendermaßen aussehen:
öffentliche Klasse Node public int Value get; einstellen; public Node Next get; einstellen;
Damit können wir jetzt eine sehr primitive verknüpfte Liste erstellen. Im folgenden Beispiel werden wir drei Knoten (erste, mittlere und letzte) zuordnen und diese dann in einer Liste verknüpfen.
// + ----- + ------ + // | 3 | null + // + ----- + ------ + Knoten zuerst = neuer Knoten Wert = 3; // + ----- + ------ + + ----- + ------ + // | 3 | null + | 5 | null + // + ----- + ------ + + ----- + ------ + Knoten mittel = neuer Knoten Wert = 5; // + ----- + ------ + + ----- + ------ + // | 3 | * --- + ---> | 5 | null + // + ----- + ------ + + ----- + ------ + first.Next = middle; // + ----- + ------ + + ----- + ------ + + ----- + ------ + // | 3 | * --- + ---> | 5 | null + | 7 | null + // + ----- + ------ + + ----- + ------ + + ----- + ------ + Node last = new Knoten Wert = 7; // + ----- + ------ + + ----- + ------ + + ----- + ------ + // | 3 | * --- + ---> | 5 | * --- + -> | 7 | null + // + ----- + ------ + + ----- + ------ + + ----- + ------ + middle.Next = zuletzt;
Wir haben jetzt eine verknüpfte Liste, die mit dem Knoten beginnt zuerst und endet mit dem Knoten zuletzt. Das Nächster Die Eigenschaft für den letzten Knoten zeigt auf null, was das Ende der Liste ist. Mit dieser Liste können wir einige grundlegende Operationen ausführen. Zum Beispiel der Wert jedes Knotens Daten Eigentum:
private static void PrintList (Knotenknoten) while (node! = null) Console.WriteLine (node.Value); node = node.Next;
Das Druckliste Diese Methode führt durch, dass jeder Knoten in der Liste durchlaufen wird, der Wert des aktuellen Knotens gedruckt wird und dann zu dem Knoten weitergeleitet wird, auf den der Knoten zeigt Nächster Eigentum.
Nun, da wir wissen, wie ein Verknüpfter Listenknoten aussehen könnte, wollen wir uns den eigentlichen ansehen LinkedListNode Klasse.
public class LinkedListNode /// /// Erstellt einen neuen Knoten mit dem angegebenen Wert. /// public LinkedListNode (T-Wert) Value = value; /// /// Der Knotenwert. /// public T Value get; internes Set; /// /// Der nächste Knoten in der verknüpften Liste (Null, wenn letzter Knoten). /// public LinkedListNode Next get; internes Set;
Bevor Sie unser implementieren LinkedList Klasse, müssen wir darüber nachdenken, was wir mit der Liste machen möchten.
Früher haben wir gesehen, dass die Sammlung stark typisierte Daten unterstützen muss, damit wir wissen, dass wir eine generische Schnittstelle erstellen möchten.
Da wir das .NET-Framework verwenden, um die Liste zu implementieren, ist es sinnvoll, dass sich diese Klasse wie die anderen integrierten Auflistungstypen verhalten soll. Der einfachste Weg, dies zu tun, ist die Implementierung von ICollection Schnittstelle. Beachten Sie, ich wähle ICollection und nicht IList. Das liegt daran, dass die IList Schnittstelle fügt die Fähigkeit hinzu, auf Werte nach Index zuzugreifen. Obwohl die direkte Indizierung im Allgemeinen nützlich ist, kann sie nicht effizient in einer verknüpften Liste implementiert werden.
Unter Berücksichtigung dieser Anforderungen können wir einen grundlegenden Klassen-Stub erstellen. Anschließend können wir diese Methoden durch den Rest des Abschnitts ergänzen.
Öffentliche Klasse LinkedList: System.Collections.Generic.ICollection public void Add (T-Element) throw new System.NotImplementedException (); public void Clear () throw new System.NotImplementedException (); public bool Enthält (T-Element) throw new System.NotImplementedException (); public void CopyTo (T [] -Array, int arrayIndex) werfen neues System.NotImplementedException (); public int Count get; privates Set; public bool IsReadOnly get throw new System.NotImplementedException (); public bool Remove (T-Element) throw new System.NotImplementedException (); public System.Collections.Generic.IEnumerator GetEnumerator () werfen neues System.NotImplementedException (); System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator () werfen neue System.NotImplementedException ();
| Verhalten | Fügt den angegebenen Wert am Ende der verknüpften Liste hinzu. |
| Performance | O (1) |
Das Hinzufügen eines Elements zu einer verknüpften Liste umfasst drei Schritte:
LinkedListNode Beispiel.Nächster Eigenschaft des letzten Knotens für den neuen Knoten.Der Schlüssel ist zu wissen, welcher Knoten der letzte Knoten in der Liste ist. Es gibt zwei Möglichkeiten, dies zu wissen. Die erste Möglichkeit besteht darin, den ersten Knoten (den "Kopfknoten") zu verfolgen und die Liste zu durchlaufen, bis wir den letzten Knoten gefunden haben. Für diesen Ansatz ist es nicht erforderlich, dass wir den letzten Knoten verfolgen, wodurch eine Referenzspeichermenge gespart wird (unabhängig von der Größe Ihres Plattformzeigers). Es ist jedoch erforderlich, dass wir die Liste jedes Mal durchlaufen, wenn ein Knoten hinzugefügt wird. Das würde machen Hinzufügen eine O (n) -Operation.
Der zweite Ansatz erfordert, dass wir den letzten Knoten (den "Endknoten") in der Liste verfolgen. Wenn wir den neuen Knoten hinzufügen, greifen wir einfach direkt auf unsere gespeicherte Referenz zu. Dies ist ein O (1) -Algorithmus und daher der bevorzugte Ansatz.
Das erste, was wir tun müssen, ist das Hinzufügen von zwei privaten Feldern LinkedList Klasse: Verweise auf die ersten (Kopf-) und letzten (Schwanz-) Knoten.
private LinkedListNode _head; private LinkedListNode _tail;
Als Nächstes müssen wir die Methode hinzufügen, die die drei Schritte ausführt.
public void Add (T-Wert) LinkedListNode-Knoten = neuer LinkedListNode (Wert); if (_head == null) _head = Knoten; _tail = Knoten; else _tail.Next = Knoten; _tail = Knoten; Count ++;
Zuerst ordnet es das Neue zu LinkedListNode Beispiel. Als nächstes wird geprüft, ob die Liste leer ist. Wenn die Liste leer ist, wird der neue Knoten einfach durch Zuweisen von hinzugefügt _Kopf und _Schwanz Verweise auf den neuen Knoten. Der neue Knoten ist jetzt sowohl der erste als auch der letzte Knoten in der Liste. Wenn die Liste nicht leer ist, wird der Knoten am Ende der Liste hinzugefügt _Schwanz Die Referenz wird aktualisiert und zeigt auf das neue Ende der Liste.
Das Anzahl Diese Eigenschaft wird inkrementiert, wenn ein Knoten hinzugefügt wird, um sicherzustellen, dass ICollection. Anzahl Die Eigenschaft gibt den genauen Wert zurück.
| Verhalten | Entfernt den ersten Knoten in der Liste, dessen Wert dem angegebenen Wert entspricht. Die Methode gibt true zurück, wenn ein Wert entfernt wurde. Andernfalls wird falsch zurückgegeben. |
| Performance | Auf) |
Bevor wir über das sprechen Löschen Algorithmus, schauen wir uns an, was es zu erreichen versucht. In der folgenden Abbildung sind vier Knoten in einer Liste enthalten. Wir möchten den Knoten mit dem Wert drei entfernen.
Eine verknüpfte Liste mit vier Werten Nach dem Entfernen wird die Liste so geändert, dass die Nächster Eigenschaft auf dem Knoten mit dem Wert zwei zeigt auf den Knoten mit dem Wert vier.
Die verknüpfte Liste mit dem 3-Knoten wurde entfernt Der grundlegende Algorithmus für das Entfernen von Knoten ist:
Der Teufel steckt wie immer im Detail. Es gibt einige Fälle, in denen wir beim Entfernen eines Knotens nachdenken müssen:
_Kopf und _Schwanz Felder zu Null._Kopf Feld, um auf den neuen Kopfknoten zu zeigen._Schwanz Feld, um auf den vorletzten Knoten in der Liste zu verweisen und seinen Knoten festzulegen Nächster Eigentum an Null.public bool Remove (T-Element) LinkedListNode previous = null; LinkedListNode current = _head; // 1: Leere Liste: Nichts tun. // 2: Einzelknoten: Vorherige ist null. // 3: Viele Knoten: // a: Der zu entfernende Knoten ist der erste Knoten. // b: Zu entfernender Knoten ist der mittlere oder letzte. while (current! = null) if (current.Value.Equals (item)) // Dies ist ein Knoten in der Mitte oder am Ende. if (vorherige! = null) // Fall 3b. // Vorher: Kopf -> 3 -> 5 -> null // Nachher: Kopf -> 3 ------> null previous.Next = current.Next; // Es war das Ende, also aktualisiere _tail. if (current.Next == null) _tail = previous; else // Fall 2 oder 3a. // Vorher: Kopf -> 3 -> 5 // Nach: Kopf ------> 5 // Kopf -> 3 -> null // Kopf ------> null _head = _head.Next; // Ist die Liste jetzt leer? if (_head == null) _tail = null; Anzahl--; wahr zurückgeben; previous = aktuell; current = current.Next; falsch zurückgeben;
Das Anzahl Eigenschaft wird dekrementiert, wenn ein Knoten entfernt wird, um sicherzustellen, dass ICollection. Anzahl Die Eigenschaft gibt den genauen Wert zurück.
| Verhalten | Gibt einen booleschen Wert zurück, der angibt, ob der angegebene Wert in der verknüpften Liste vorhanden ist. |
| Performance | Auf) |
Das Enthält Methode ist ziemlich einfach. Es betrachtet jeden Knoten in der Liste vom ersten bis zum letzten Punkt und gibt true zurück, sobald ein mit dem Parameter passender Knoten gefunden wird. Wenn das Ende der Liste erreicht ist und der Knoten nicht gefunden wurde, kehrt die Methode zurück falsch.
public bool Enthält (T-Element) LinkedListNode current = _head; while (current! = null) if (current.Value.Equals (item)) return true; current = current.Next; falsch zurückgeben;
| Verhalten | Gibt eine IEnumerator-Instanz zurück, die das Auflisten der verknüpften Listenwerte von Anfang bis Ende ermöglicht. |
| Performance | Die Enumerator-Instanz zurückgeben ist eine O (1) -Operation. Aufzählen jedes Elements ist eine O (n) -Operation. |
GetEnumerator wird durch Auflisten der Liste vom ersten bis zum letzten Knoten implementiert und verwendet das C # Ausbeute Schlüsselwort, um den aktuellen Wert des Knotens an den Aufrufer zurückzugeben.
Beachten Sie, dass die LinkedList das Iterationsverhalten in der implementiert IEnumerable Version der GetEnumerator-Methode und dieses Verhalten in der IEnumerable-Version.
IEnumerator IEnumerable.GetEnumerator () LinkedListNode current = _head; while (aktuell! = null) Ertrag Rückgabewert.Wert; current = current.Next; IEnumerator IEnumerable.GetEnumerator () return ((IEnumerable) this) .GetEnumerator ();
| Verhalten | Entfernt alle Elemente aus der Liste. |
| Performance | O (1) |
Das klar Methode setzt einfach die _Kopf und _Schwanz Felder auf null, um die Liste zu löschen. Da .NET eine in Garbage gesammelte Sprache ist, müssen die Knoten nicht explizit entfernt werden. Es liegt in der Verantwortung des Anrufers, nicht der verknüpften Liste, sicherzustellen, dass die Knoten enthalten sind IDisposable Referenzen werden ordnungsgemäß entsorgt.
public void Clear () _head = null; _tail = null; Zählung = 0;
| Verhalten | Kopiert den Inhalt der verknüpften Liste von Anfang bis Ende in das bereitgestellte Array, beginnend am angegebenen Arrayindex. |
| Performance | Auf) |
Das Kopieren nach Diese Methode durchläuft einfach die Listenelemente und verwendet die einfache Zuordnung, um die Elemente in das Array zu kopieren. Es liegt in der Verantwortung des Aufrufers, sicherzustellen, dass das Zielarray den geeigneten freien Speicherplatz für alle Elemente in der Liste enthält.
public void CopyTo (T [] Array, int arrayIndex) LinkedListNode current = _head; while (current! = null) array [arrayIndex ++] = current.Value; current = current.Next;
| Verhalten | Gibt eine Ganzzahl zurück, die die Anzahl der aktuell in der Liste enthaltenen Elemente angibt. Wenn die Liste leer ist, lautet der zurückgegebene Wert 0. |
| Performance | O (1) |
Anzahl ist einfach eine automatisch implementierte Eigenschaft mit einem öffentlichen Getter und privaten Setter. Das eigentliche Verhalten geschieht im Hinzufügen, Löschen, und klar Methoden.
public int Count erhalten; privates Set;
| Verhalten | Gibt false zurück, wenn die Liste nicht schreibgeschützt ist. |
| Performance | O (1) |
public bool IsReadOnly get return false;
Die soeben erstellte LinkedList-Klasse wird als einzeln verknüpfte Liste bezeichnet. Das bedeutet, dass nur eine einzige unidirektionale Verbindung zwischen einem Knoten und dem nächsten Knoten in der Liste besteht. Es gibt eine allgemeine Variation der verknüpften Liste, die es dem Anrufer ermöglicht, auf die Liste von beiden Enden zuzugreifen. Diese Variante wird als doppelt verknüpfte Liste bezeichnet.
Um eine doppelt verknüpfte Liste zu erstellen, müssen Sie zunächst unsere LinkedListNode-Klasse ändern, um eine neue Eigenschaft mit dem Namen Previous zu erhalten. Vorherige verhält sich wie Next, nur dass sie auf den vorherigen Knoten in der Liste zeigt.
Eine doppelt verknüpfte Liste, die eine vorherige Knoteneigenschaft verwendet In den folgenden Abschnitten werden nur die Änderungen zwischen der einfach verknüpften Liste und der neuen doppelt verknüpften Liste beschrieben.
Die einzige Änderung, die im vorgenommen wird LinkedListNode Klasse ist das Hinzufügen einer neuen Eigenschaft namens Bisherige was auf das vorige hinweist LinkedListNode in der verknüpften Liste oder kehrt zurück Null wenn es der erste Knoten in der Liste ist.
public class LinkedListNode /// /// Erstellt einen neuen Knoten mit dem angegebenen Wert. /// /// public LinkedListNode (T-Wert) Value = value; /// /// Der Knotenwert. /// public T Value get; internes Set; /// /// Der nächste Knoten in der verknüpften Liste (Null, wenn letzter Knoten). /// public LinkedListNode Next get; internes Set; /// /// Der vorherige Knoten in der verknüpften Liste (Null, wenn erster Knoten). /// public LinkedListNode Previous get; internes Set;
Während die einfach verknüpfte Liste nur Knoten am Ende der Liste hinzugefügt hat, können Sie mit der doppelt verknüpften Liste Knoten am Anfang und Ende der Liste hinzufügen AddFirst und AddLast, beziehungsweise. Das ICollection. Hinzufügen Methode wird auf die verschoben AddLast Methode, um die Kompatibilität mit dem einzeln verknüpften zu erhalten Liste Klasse.
| Verhalten | Fügt den angegebenen Wert am Anfang der Liste hinzu. |
| Performance | O (1) |
Wenn Sie einen Knoten am Anfang der Liste hinzufügen, ähneln die Aktionen dem Hinzufügen zu einer einfach verknüpften Liste.
Nächster Eigenschaft des neuen Knotens zum alten Kopfknoten.Bisherige Eigenschaft des alten Kopfknotens an den neuen Knoten._Schwanz Feld (falls erforderlich) und Inkrement Anzahl.public void AddFirst (T-Wert) LinkedListNode node = neuer LinkedListNode (Wert); // Speichern Sie den Kopfknoten, damit wir ihn nicht verlieren. LinkedListNode temp = _head; // Zeige den neuen Knoten. _head = Knoten; // Füge den Rest der Liste hinter head ein. _head.Next = temp; if (Count == 0) // Wenn die Liste leer war, sollten head und tail // auf den neuen Knoten zeigen. _tail = _head; else // Vorher: Kopf -------> 5 <-> 7 -> null // Nach: head -> 3 <-> 5 <-> 7 -> null temp.Previous = _head; Count ++;
| Verhalten | Fügt den angegebenen Wert am Ende der Liste hinzu. |
| Performance | O (1) |
Das Hinzufügen eines Knotens am Ende der Liste ist noch einfacher als das Hinzufügen eines Knotens am Anfang.
Der neue Knoten wird einfach an das Ende der Liste angehängt und aktualisiert den Status von _Schwanz und _Kopf gegebenenfalls, und Anzahl wird inkrementiert.
public void AddLast (T-Wert) LinkedListNode node = neuer LinkedListNode (Wert); if (Count == 0) _head = Knoten; else _tail.Next = Knoten; // Vorher: Kopf -> 3 <-> 5 -> null // Nach: Kopf -> 3 <-> 5 <-> 7 -> null // 7.Previous = 5 node.Previous = _tail; _tail = Knoten; Count ++;
Und wie schon erwähnt, ICollection.Hinzufügen wird jetzt einfach anrufen AddLast.
public void Add (T-Wert) AddLast (Wert);
Mögen Hinzufügen, das Löschen Die Methode wird erweitert, um das Entfernen von Knoten vom Anfang oder Ende der Liste zu unterstützen. Das ICollection.Die Remove-Methode entfernt weiterhin Elemente von Anfang an, wobei nur die entsprechende Änderung aktualisiert wird Bisherige Eigentum.
| Verhalten | Entfernt den ersten Wert aus der Liste. Wenn die Liste leer ist, wird keine Aktion ausgeführt. Gibt true zurück, wenn ein Wert entfernt wurde. Andernfalls wird falsch zurückgegeben. |
| Performance | O (1) |
RemoveFirst aktualisiert die Liste durch Festlegen der verknüpften Liste Kopf Eigenschaft an den zweiten Knoten in der Liste und Aktualisierung seiner Bisherige Eigentum an Null. Dadurch werden alle Verweise auf den vorherigen Kopfknoten entfernt und aus der Liste entfernt. Wenn die Liste nur ein Singleton enthielt oder leer war, ist die Liste leer (die Kopf und Schwanz Eigenschaften werden sein Null).
public void RemoveFirst () if (Count! = 0) // Vorher: Kopf -> 3 <-> 5 // Nach: Kopf -------> 5 // Kopf -> 3 -> null // Kopf ------> null _head = _head.Next; Anzahl--; if (Count == 0) _tail = null; else // 5.Previous war 3; jetzt ist es null. _head.Previous = null;
| Verhalten | Entfernt den letzten Knoten aus der Liste. Wenn die Liste leer ist, wird keine Aktion ausgeführt. Gibt true zurück, wenn ein Wert entfernt wurde. Andernfalls wird false zurückgegeben. |
| Performance | O (1) |
RemoveLast funktioniert durch Festlegen der Liste Schwanz Eigenschaft, die der Knoten ist, der dem aktuellen Endknoten vorausgeht. Dadurch wird der letzte Knoten aus der Liste entfernt. Wenn die Liste leer war oder nur einen Knoten hatte, wenn die Methode den Wert zurückgibt Kopf und Schwanz Eigenschaften werden sie beide sein Null.
public void RemoveLast () if (Count! = 0) if (Count == 1) _head = null; _tail = null; else // Vorher: Kopf -> 3 -> 5 -> 7 // Schwanz = 7 // Nach: Kopf -> 3 -> 5 -> null // Schwanz = 5 // Null aus 5 Nächste Eigenschaft. _tail.Previous.Next = null; _tail = _tail.Previous; Anzahl--;
| Verhalten | Entfernt den ersten Knoten in der Liste, dessen Wert dem angegebenen Wert entspricht. Die Methode gibt true zurück, wenn ein Wert entfernt wurde. Andernfalls wird falsch zurückgegeben. |
| Performance | Auf) |
Das ICollection. Löschen Die Methode ist nahezu identisch mit der einfach verknüpften Version, nur dass die Bisherige Eigenschaft wird jetzt während des Entfernungsvorgangs aktualisiert. Um wiederholten Code zu vermeiden, ruft die Methode auf RemoveFirst wenn bestimmt wird, dass der entfernte Knoten der erste Knoten in der Liste ist.
public bool Remove (T-Element) LinkedListNode previous = null; LinkedListNode current = _head; // 1: Leere Liste: Nichts tun. // 2: Einzelknoten: Vorherige ist null. // 3: Viele Knoten: // a: Der zu entfernende Knoten ist der erste Knoten. // b: Zu entfernender Knoten ist der mittlere oder letzte. while (aktuell! = null) // Kopf -> 3 -> 5 -> 7 -> null // Kopf -> 3 ------> 7 -> Null ) // Es ist ein Knoten in der Mitte oder am Ende. if (vorherige! = null) // Fall 3b. previous.Next = aktuell.Next; // Es war das Ende, also aktualisiere _tail. if (current.Next == null) _tail = previous; else // Vorher: Kopf -> 3 <-> 5 <-> 7 -> null // Nach: Kopf -> 3 <-------> 7 -> null // previous = 3 // current = 5 // current.Next = 7 // Also… 7.Previous = 3 current.Next.Previous = previous; Anzahl--; else // Fall 2 oder 3a. RemoveFirst (); return true; previous = aktuell; current = current.Next; falsch zurückgeben;
Wir können Knoten an der Spitze und am Ende der Liste hinzufügen. Warum interessiert uns das? So wie es jetzt steht, ist das doppelt verbunden Liste Klasse ist nicht mächtiger als die einzeln verknüpfte Liste. Mit nur einer geringfügigen Änderung können wir jedoch alle möglichen Verhaltensweisen öffnen. Durch das Freilegen der Kopf und Schwanz Eigenschaften als schreibgeschützte öffentliche Eigenschaften, kann der Konsument der verknüpften Liste alle möglichen neuen Verhaltensweisen implementieren.
public LinkedListNode Head get return _head; public LinkedListNode Tail get return _tail;
Mit dieser einfachen Änderung können wir die Liste manuell auflisten, was eine umgekehrte Aufzählung und Suche ermöglicht.
Das folgende Codebeispiel zeigt beispielsweise, wie die Liste verwendet wird Schwanz und Bisherige Eigenschaften, um die Liste in umgekehrter Reihenfolge aufzuzählen und auf jedem Knoten etwas zu bearbeiten.
public void ProcessListBackwards () LinkedList list = new LinkedList (); PopulateList (Liste); LinkedListNode current = list.Tail; while (aktuell! = null) ProcessNode (aktuell); current = current.Previous;
Zusätzlich ist das doppelt verbunden Liste Klasse ermöglicht es uns, das einfach zu erstellen Deque Klasse, die selbst ein Baustein für andere Klassen ist. Wir werden diese Klasse später in einem anderen Abschnitt besprechen.
