Im Jahr 2009 habe ich mir vorgenommen, ein ganzes Jahr lang jede Woche einen Blogbeitrag zu schreiben. Ich hatte gelesen, dass der beste Weg zu mehr Besucherzahlen in einem Blog darin besteht, konsequent zu posten. Ein Beitrag pro Woche schien ein realistisches Ziel zu sein, da ich so viele Artikelideen hatte, aber es stellte sich heraus, dass mir 52 Ideen fehlten. Ich wühlte mich durch einige halbfertige Kapitel von Professional JavaScript und fand eine Menge Material zu klassischen Informatik-Themen, darunter Datenstrukturen und Algorithmen. Ich habe dieses Material 2009 und (und einige 2012) in mehrere Beiträge verwandelt und viel positives Feedback darauf erhalten.

Jetzt, zum zehnjährigen Jubiläum dieser Beiträge, habe ich beschlossen, sie zu aktualisieren, neu zu veröffentlichen und mit JavaScript im Jahr 2019 zu erweitern. Es war interessant zu sehen, was sich geändert hat und was nicht, und ich hoffe, sie gefallen Ihnen.

Was ist eine verknüpfte Liste?

Eine verknüpfte Liste ist eine Datenstruktur, die mehrere Werte auf lineare Weise speichert. Jeder Wert in einer verknüpften Liste ist in einem eigenen Knoten enthalten, einem Objekt, das die Daten zusammen mit einem Link auf den nächsten Knoten in der Liste enthält. Der Link ist ein Zeiger auf ein anderes Knotenobjekt oder null, wenn es keinen nächsten Knoten gibt. Wenn jeder Knoten nur einen Zeiger auf einen anderen Knoten hat (am häufigsten next genannt), dann wird die Liste als einfach verknüpfte Liste (oder einfach verknüpfte Liste) betrachtet, während sie als doppelt verknüpfte Liste betrachtet wird, wenn jeder Knoten zwei Links hat (normalerweise previous und next). In diesem Beitrag konzentriere ich mich auf einfach verkettete Listen.

Warum eine verkettete Liste verwenden?

Der Hauptvorteil von verketteten Listen besteht darin, dass sie eine beliebige Anzahl von Werten enthalten können und dabei nur die für diese Werte erforderliche Menge an Speicher verwenden. Auf älteren Computern, auf denen der Speicher knapp war, war es sehr wichtig, den Speicher zu schonen. Damals musste man bei einem eingebauten Array in C angeben, wie viele Elemente das Array enthalten konnte, und das Programm reservierte diese Menge an Speicher. Das Reservieren dieses Speichers bedeutete, dass er nicht für den Rest des Programms oder für andere Programme, die gleichzeitig liefen, verwendet werden konnte, selbst wenn der Speicher nie gefüllt wurde. Auf speicherknappen Rechnern konnte der verfügbare Speicher bei der Verwendung von Arrays schnell erschöpft sein. Um dieses Problem zu umgehen, wurden verknüpfte Listen erstellt.

Obwohl ursprünglich für eine bessere Speicherverwaltung gedacht, wurden verknüpfte Listen auch dann beliebt, wenn Entwickler nicht wussten, wie viele Elemente ein Array letztendlich enthalten würde. Es war viel einfacher, eine verknüpfte Liste zu verwenden und nach Bedarf Werte hinzuzufügen, als die maximale Anzahl von Werten, die ein Array enthalten könnte, genau zu schätzen. Aus diesem Grund werden verknüpfte Listen oft als Grundlage für integrierte Datenstrukturen in verschiedenen Programmiersprachen verwendet.

Der integrierte JavaScript Array-Typ ist nicht als verknüpfte Liste implementiert, obwohl seine Größe dynamisch ist und für den Anfang immer die beste Option darstellt. Es kann sein, dass Sie Ihr ganzes Berufsleben lang keine verknüpfte Liste in JavaScript verwenden müssen, aber verknüpfte Listen sind immer noch ein guter Weg, um zu lernen, wie man seine eigenen Datenstrukturen erstellt.

Der Aufbau einer verknüpften Liste

Der wichtigste Teil einer verknüpften Liste ist ihre Knotenstruktur. Jeder Knoten muss einige Daten und einen Zeiger auf den nächsten Knoten in der Liste enthalten. Hier ist eine einfache Darstellung in JavaScript:

class LinkedListNode { constructor(data) { this.data = data; this.next = null; }}

In der Klasse LinkedListNode enthält die Eigenschaft data den Wert, den das verknüpfte Listenelement speichern soll, und die Eigenschaft next ist ein Zeiger auf das nächste Element in der Liste. Die next-Eigenschaft beginnt als null, da Sie den nächsten Knoten noch nicht kennen. Sie können dann eine verknüpfte Liste mit der Klasse LinkedListNode wie folgt erstellen:

// create the first nodeconst head = new LinkedListNode(12);// add a second nodehead.next = new LinkedListNode(99);// add a third nodehead.next.next = new LinkedListNode(37);

Der erste Knoten in einer verknüpften Liste wird normalerweise als Kopf bezeichnet, so dass der head-Bezeichner in diesem Beispiel den ersten Knoten darstellt. Der zweite Knoten wird erstellt und head.next zugewiesen, um eine Liste mit zwei Elementen zu erstellen. Ein dritter Knoten wird hinzugefügt, indem er head.next.next zugewiesen wird, was der next-Zeiger des zweiten Knotens in der Liste ist. Der next-Zeiger des dritten Knotens in der Liste bleibt null. Das folgende Bild zeigt die resultierende Datenstruktur.

Die Struktur einer verknüpften Liste ermöglicht es, alle Daten zu durchlaufen, indem man dem next-Zeiger auf jeden Knoten folgt. Hier ist ein einfaches Beispiel dafür, wie man eine verknüpfte Liste durchläuft und jeden Wert auf der Konsole ausgibt:

let current = head;while (current !== null) { console.log(current.data); current = current.next;}

Dieser Code verwendet die Variable current als Zeiger, der sich durch die verknüpfte Liste bewegt. Die Variable current wird auf den Kopf der Liste initialisiert und die Schleife while wird fortgesetzt, bis current null ist. Innerhalb der Schleife wird der auf dem Knoten current gespeicherte Wert gedruckt, und dann wird der next-Zeiger zum nächsten Knoten verfolgt.

Die meisten Operationen in verknüpften Listen verwenden diesen Traversal-Algorithmus oder etwas Ähnliches, so dass das Verständnis dieses Algorithmus wichtig ist, um verknüpfte Listen im Allgemeinen zu verstehen.

Die LinkedList-Klasse

Wenn Sie eine verknüpfte Liste in C schreiben würden, könnten Sie an diesem Punkt aufhören und Ihre Aufgabe als abgeschlossen betrachten (obwohl Sie eine Struktur statt einer Klasse verwenden würden, um jeden Knoten darzustellen). In objektorientierten Sprachen wie JavaScript ist es jedoch eher üblich, eine Klasse zu erstellen, um diese Funktionalität zu kapseln. Hier ein einfaches Beispiel:

const head = Symbol("head");class LinkedList { constructor() { this = null; }}

Die Klasse LinkedList stellt eine verknüpfte Liste dar und enthält Methoden zur Interaktion mit den darin enthaltenen Daten. Die einzige Eigenschaft ist eine Symboleigenschaft namens head, die einen Zeiger auf den ersten Knoten in der Liste enthält. Eine Symboleigenschaft wird anstelle einer Zeichenketteneigenschaft verwendet, um deutlich zu machen, dass diese Eigenschaft nicht außerhalb der Klasse geändert werden soll.

Hinzufügen neuer Daten zur Liste

Das Hinzufügen eines Elements in eine verknüpfte Liste erfordert das Durchlaufen der Struktur, um die richtige Position zu finden, das Erstellen eines neuen Knotens und das Einfügen an der richtigen Stelle. Der einzige Sonderfall ist, wenn die Liste leer ist. In diesem Fall erstellt man einfach einen neuen Knoten und weist ihn head:

const head = Symbol("head");class LinkedList { constructor() { this = null; } add(data) { // create a new node const newNode = new LinkedListNode(data); //special case: no items in the list yet if (this === null) { // just set the head to the new node this = newNode; } else { // start out by looking at the first node let current = this; // follow `next` links until you reach the end while (current.next !== null) { current = current.next; } // assign the node into the `next` pointer current.next = newNode; } }}

Die Methode add() akzeptiert ein einziges Argument, ein beliebiges Datenelement, und fügt es an das Ende der Liste an. Wenn die Liste leer ist (this ist null), dann wird this gleich dem neuen Knoten zugewiesen. Wenn die Liste nicht leer ist, müssen Sie die bereits vorhandene Liste durchlaufen, um den letzten Knoten zu finden. Das Durchlaufen geschieht in einer while-Schleife, die bei this beginnt und den next-Verknüpfungen der einzelnen Knoten folgt, bis der letzte Knoten gefunden ist. Der letzte Knoten hat eine next-Eigenschaft, die null entspricht. Daher ist es wichtig, das Traversal an diesem Punkt zu beenden und nicht, wenn current null ist (wie im vorherigen Abschnitt). Sie können dann den neuen Knoten dieser next-Eigenschaft zuweisen, um die Daten in die Liste einzufügen.

Die Komplexität der add()-Methode ist O(n), weil Sie die gesamte Liste durchlaufen müssen, um die Stelle zum Einfügen eines neuen Knotens zu finden. Sie können diese Komplexität auf O(1) reduzieren, indem Sie das Ende der Liste (gewöhnlich als Schwanz bezeichnet) zusätzlich zum Kopf verfolgen, wodurch Sie sofort einen neuen Knoten an der richtigen Position einfügen können.

Daten aus der Liste abrufen

Verknüpfte Listen erlauben keinen zufälligen Zugriff auf ihren Inhalt, aber Sie können dennoch Daten an jeder beliebigen Position abrufen, indem Sie die Liste durchlaufen und die Daten zurückgeben. Dazu fügen Sie eine get()-Methode hinzu, die einen nullbasierten Index der abzurufenden Daten akzeptiert, etwa so:

class LinkedList { // other methods hidden for clarity get(index) { // ensure `index` is a positive value if (index > -1) { // the pointer to use for traversal let current = this; // used to keep track of where in the list you are let i = 0; // traverse the list until you reach either the end or the index while ((current !== null) && (i < index)) { current = current.next; i++; } // return the data if `current` isn't null return current !== null ? current.data : undefined; } else { return undefined; } }}

Die get()-Methode überprüft zunächst, ob index ein positiver Wert ist, andernfalls gibt sie undefined zurück. Die Variable i wird verwendet, um zu verfolgen, wie tief der Traversal in die Liste eingedrungen ist. Die Schleife selbst ist derselbe grundlegende Durchlauf, den Sie zuvor gesehen haben, mit der zusätzlichen Bedingung, dass die Schleife beendet werden soll, wenn i gleich index ist. Das bedeutet, dass es zwei Bedingungen gibt, unter denen die Schleife beendet werden kann:

1. current ist null, was bedeutet, dass die Liste kürzer als index ist.
2. i ist gleich index, was bedeutet, dass current der Knoten an der Position index ist.

Wenn current null ist, wird undefined zurückgegeben, andernfalls wird current.data zurückgegeben. Diese Prüfung stellt sicher, dass get() niemals einen Fehler für einen index auslöst, der nicht in der Liste gefunden wird (obwohl man sich dafür entscheiden könnte, einen Fehler auszulösen, anstatt undefined zurückzugeben).

Die Komplexität der get()-Methode reicht von O(1) beim Entfernen des ersten Knotens (keine Traversierung ist erforderlich) bis O(n) beim Entfernen des letzten Knotens (Traversierung der gesamten Liste ist erforderlich). Es ist schwierig, die Komplexität zu reduzieren, da immer eine Suche erforderlich ist, um den richtigen Wert für die Rückgabe zu ermitteln.

Entfernen von Daten aus einer verknüpften Liste

Das Entfernen von Daten aus einer verknüpften Liste ist etwas schwierig, da sichergestellt werden muss, dass alle next Zeiger gültig bleiben, nachdem ein Knoten entfernt wurde. Wenn Sie zum Beispiel den zweiten Knoten in einer Liste mit drei Knoten entfernen wollen, müssen Sie sicherstellen, dass die next-Eigenschaft des ersten Knotens nun auf den dritten statt auf den zweiten Knoten zeigt. Das Überspringen des zweiten Knotens auf diese Weise entfernt ihn effektiv aus der Liste.

Der Vorgang des Entfernens besteht eigentlich aus zwei Vorgängen:

1. Finden Sie den angegebenen Index (derselbe Algorithmus wie in get())
2. Entfernen Sie den Knoten an diesem Index

Das Finden des angegebenen Indexes ist derselbe wie in der Methode get(), aber in dieser Schleife müssen Sie auch den Knoten verfolgen, der vor current kommt, weil Sie den next-Zeiger des vorherigen Knotens ändern müssen.

Es gibt auch vier Sonderfälle zu berücksichtigen:

1. Die Liste ist leer (kein Traversal möglich)
2. Der Index ist kleiner als Null
3. Der Index ist größer als die Anzahl der Elemente in der Liste
4. Der Index ist Null (Entfernen des Kopfes)

In den ersten drei Fällen kann der Entfernungsvorgang nicht abgeschlossen werden, so dass es sinnvoll ist, einen Fehler zu werfen; der vierte Sonderfall erfordert das Umschreiben der Eigenschaft this. So sieht die Implementierung einer remove()-Methode aus:

class LinkedList { // other methods hidden for clarity remove(index) { // special cases: empty list or invalid `index` if ((this === null) || (index < 0)) { throw new RangeError(`Index ${index} does not exist in the list.`); } // special case: removing the first node if (index === 0) { // temporary store the data from the node const data = this.data; // just replace the head with the next node in the list this = this.next; // return the data at the previous head of the list return data; } // pointer use to traverse the list let current = this; // keeps track of the node before current in the loop let previous = null; // used to track how deep into the list you are let i = 0; // same loops as in `get()` while ((current !== null) && (i < index)) { // save the value of current previous = current; // traverse to the next node current = current.next; // increment the count i++; } // if node was found, remove it if (current !== null) { // skip over the node to remove previous.next = current.next; // return the value that was just removed from the list return current.data; } // if node wasn't found, throw an error throw new RangeError(`Index ${index} does not exist in the list.`); }}

Die remove()-Methode prüft zunächst auf zwei Sonderfälle, eine leere Liste (this ist null) und ein index, das kleiner als Null ist. In beiden Fällen wird ein Fehler ausgelöst.

Der nächste Sonderfall ist, wenn index gleich 0 ist, was bedeutet, dass Sie den Listenkopf entfernen. Der neue Listenkopf sollte der zweite Knoten in der Liste sein, also können Sie this gleich this.next setzen. Es spielt keine Rolle, ob nur ein Knoten in der Liste vorhanden ist, da this am Ende gleich null wäre, was bedeutet, dass die Liste nach dem Entfernen leer ist. Der einzige Haken an der Sache ist, dass die Daten des ursprünglichen Kopfes in einer lokalen Variablen data gespeichert werden müssen, damit sie zurückgegeben werden können.

Da drei der vier Sonderfälle erledigt sind, können Sie nun mit einem Traversal ähnlich dem der Methode get() fortfahren. Wie bereits erwähnt, ist diese Schleife insofern etwas anders, als die Variable previous verwendet wird, um den Knoten zu verfolgen, der kurz vor current erscheint, da diese Information notwendig ist, um einen Knoten zu entfernen. Ähnlich wie bei get() kann current beim Verlassen der Schleife null sein, was bedeutet, dass der Index nicht gefunden wurde. In diesem Fall wird ein Fehler ausgelöst, andernfalls wird previous.next auf current.next gesetzt, wodurch current effektiv aus der Liste entfernt wird. Die auf current gespeicherten Daten werden als letzter Schritt zurückgegeben.

Die Komplexität der remove()-Methode ist die gleiche wie get() und reicht von O(1) beim Entfernen des ersten Knotens bis O(n) beim Entfernen des letzten Knotens.

Making the list iterable

Um mit der JavaScript-Schleife for-of und der Array-Destrukturierung verwendet zu werden, müssen Datensammlungen iterable sein. Die eingebauten JavaScript-Sammlungen wie Array und Set sind standardmäßig iterabel, und Sie können Ihre eigenen Klassen iterabel machen, indem Sie eine Symbol.iterator Generatormethode für die Klasse angeben. Ich ziehe es vor, zunächst eine values()-Generatormethode zu implementieren (um der Methode in den eingebauten Sammlungsklassen zu entsprechen) und dann Symbol.iterator values() direkt aufrufen zu lassen.

Die values()-Methode muss nur eine grundlegende Durchquerung der Liste und yield die Daten, die jeder Knoten enthält, durchführen:

class LinkedList { // other methods hidden for clarity *values(){ let current = this; while (current !== null) { yield current.data; current = current.next; } } () { return this.values(); } }

Die values()-Methode ist mit einem Sternchen (*) gekennzeichnet, um anzuzeigen, dass es sich um eine Generatormethode handelt. Die Methode durchläuft die Liste und verwendet yield, um jedes Datenelement zurückzugeben, auf das sie trifft. (Beachten Sie, dass die Methode Symbol.iterator nicht als Generator gekennzeichnet ist, da sie einen Iterator von der Generatormethode values() zurückgibt.)

Verwendung der Klasse

Nach der Fertigstellung können Sie die Implementierung der verknüpften Liste wie folgt verwenden:

const list = new LinkedList();list.add("red");list.add("orange");list.add("yellow"); // get the second item in the listconsole.log(list.get(1)); // "orange"// print out all itemsfor (const color of list) { console.log(color);}// remove the second item in the list console.log(list.remove(1)); // "orange" // get the new first item in the listconsole.log(list.get(1)); // "yellow"// convert to an arrayconst array1 = ;const array2 = ;

Diese grundlegende Implementierung einer verknüpften Liste kann mit einer sizeEigenschaft zum Zählen der Anzahl der Knoten in der Liste und anderen bekannten Methoden wie indexOf() abgerundet werden. Der vollständige Quellcode ist auf GitHub in meinem Projekt Computer Science in JavaScript verfügbar.

Fazit

Verknüpfte Listen sind nicht etwas, das Sie wahrscheinlich jeden Tag verwenden, aber sie sind eine grundlegende Datenstruktur in der Informatik. Das Konzept der Verwendung von Knoten, die aufeinander verweisen, wird in vielen anderen Datenstrukturen verwendet und ist in vielen höheren Programmiersprachen enthalten. Ein gutes Verständnis der Funktionsweise von verknüpften Listen ist wichtig für ein gutes Gesamtverständnis der Erstellung und Verwendung anderer Datenstrukturen.

Für die JavaScript-Programmierung sind Sie fast immer besser dran, wenn Sie die eingebauten Auflistungsklassen wie Array verwenden, anstatt Ihre eigenen zu erstellen. Die eingebauten Auflistungsklassen wurden bereits für den Einsatz in der Produktion optimiert und werden in allen Ausführungsumgebungen gut unterstützt.