Eine sanfte Einführung in Datenstrukturen: Funktionsweise verknüpfter Listen

Haben Sie jemals eine Rube Goldberg Maschine gebaut? Wenn nicht, haben Sie vielleicht eine aufwändige Reihe von Dominosteinen gebaut?

Okay, vielleicht warst du nicht so nerdig wie ich. So sei es. Für diejenigen unter Ihnen, die das Vergnügen hatten, eines der oben genannten Dinge zu tun, haben Sie bereits die Essenz der heutigen Datenstruktur verstanden: verknüpfte Listen!

Wie verknüpfte Listen funktionieren

Die einfachste Form von verknüpften Listen - eine einfach verknüpfte Liste - ist eine Reihe von Knoten, bei denen jeder einzelne Knoten sowohl einen Wert als auch einen Zeiger auf den nächsten Knoten in der Liste enthält.

Durch Hinzufügen ( Hinzufügen ) wird die Liste erweitert, indem Elemente am Ende der Liste hinzugefügt werden.

Entfernungen ( Entfernen) werden immer von einer bestimmten Position in der Liste entfernt.

Suchen ( Enthält ) durchsucht die Liste nach einem Wert.

Beispielanwendungsfälle:

  • Speichern von Werten in einer Hash-Tabelle, um Kollisionen zu vermeiden (mehr dazu in einigen Beiträgen)
  • Remaking das erstaunliche Rennen!

Lassen Sie uns diesen Artikel schön und leicht halten, indem wir an einem Tool arbeiten, mit dem das CBS-Netzwerk ihre nächste großartige Renn-TV-Show planen kann.

Ich möchte, dass Sie sich dabei immer wieder fragen: „Wie unterscheiden sich verknüpfte Listen von Arrays? Wie sind sie ähnlich? "

Lass uns anfangen.

Zunächst müssen Sie die Darstellung unserer verknüpften Liste erstellen:

class LinkedList{ constructor(){ this._head = null; this._tail = null; this._length = 0; }
 size(){ return this._length; }}

Um den Start- und Endpunkt des Rennens zu verfolgen, erstellen Sie die Kopf- und Heckeigenschaften.

Um sicherzustellen, dass das Rennen für die Saison nicht zu lang oder zu kurz ist, erstellen Sie eine Längeneigenschaft und eine Größenmethode. Auf diese Weise können Sie immer genau verfolgen, wie lange das Rennen dauert.

Nachdem Sie nun die Möglichkeit haben, die Rennliste zu speichern, sollten Sie eine Möglichkeit zum Hinzufügen zu dieser Liste erstellen. Die Frage ist, was fügen Sie speziell hinzu?

Denken Sie daran, dass eine verknüpfte Liste eine Reihe von Knoten ist, bei denen jeder Knoten einen Wert und einen Zeiger auf den nächsten Knoten in der Liste hat. Wenn Sie dies wissen, erkennen Sie, dass ein Knoten nur ein Objekt mit einem Wert und einer nächsten Eigenschaft ist.

Da Sie jedes Mal, wenn Sie der Liste hinzufügen, einen neuen Knoten erstellen, entscheiden Sie sich, einen Konstruktor zu erstellen, der es einfacher macht, für jeden Wert, der Ihrer Liste hinzugefügt wird, einen neuen Knoten zu erstellen.

class Node{ constructor(value){ this.value = value; this.next = null; }}

Wenn Sie diesen Konstruktor zur Verfügung haben, können Sie Ihre Add-Methode erstellen.

class Node { constructor(value) { this.value = value; this.next = null; }}
class LinkedList { constructor() { this._head = null; this._tail = null; this._length = 0; } add(value) { let node = new Node(value); //we create our node if(!this._head && !this._tail){ //If it's the first node this._head = node; //1st node is head & tail this._tail = node; }else{ this._tail.next = node; //add node to the back this._tail = this._tail.next; //reset tail to last node } this._length++; } size() { return this._length; }}
const AmazingRace = new LinkedList();AmazingRace.add("Colombo, Sri Lanka");AmazingRace.add("Lagos, Nigeria");AmazingRace.add("Surat, India");AmazingRace.add("Suzhou, China");

Nachdem Sie diese Methode hinzugefügt haben, können Sie Ihrer Amazing Race-Liste eine Reihe von Orten hinzufügen. So wird es aussehen. Beachten Sie, dass ich zusätzliche Leerzeichen hinzugefügt habe, um das Verständnis zu erleichtern.

{ _head: { value: 'Colombo, Sri Lanka', next: { value: 'Lagos, Nigeria', next: { value: 'Surat, India', next: { value: 'Suzhou, China', next: null } } } }, _tail: { value: 'Suzhou, China', next: null }, _length: 4 }

Okay, jetzt, da Sie diese Liste erstellt haben und eine Möglichkeit zum Hinzufügen haben, stellen Sie fest, dass Sie Hilfe beim Hinzufügen von Standorten zu dieser Liste benötigen, weil Sie an Decidophobia leiden (ja, das ist eine Sache).

Sie beschließen, es mit Ihrem Kollegen Kent zu teilen und ihn zu bitten, noch ein paar Plätze hinzuzufügen. Das einzige Problem ist, wenn Sie es ihm geben, sagen Sie ihm nicht, welche Stellen Sie bereits hinzugefügt haben. Leider haben Sie auch vergessen, nachdem Sie unter Amnesie gelitten haben, die durch Entscheidungsangst hervorgerufen wurde.

Natürlich konnte er einfach console.log (AmazingRace) ausführen und lesen, was die Konsole ausgibt. Aber Kent ist ein fauler Programmierer und muss überprüfen, ob etwas vorhanden ist, damit er Duplikate vermeiden kann. In diesem Sinne erstellen Sie eine Include- Methode, um nach vorhandenen Werten zu suchen.

class Node { constructor(value) { this.value = value; this.next = null; }}class LinkedList { constructor() { this._head = null; this._tail = null; this._length = 0; } add(value) { let node = new Node(value); if(!this._head && !this._tail){ this._head = node; this._tail = this._head; }else{ this._tail.next = node; this._tail = this._tail.next; } this._length++; } contains(value){ let node = this._head; while(node){ if(node.value === value){ return true; } node = node.next; } return false; } size() { return this._length; } }
const AmazingRace = new LinkedList();AmazingRace.add("Colombo, Sri Lanka");AmazingRace.add("Lagos, Nigeria");AmazingRace.add("Surat, India");AmazingRace.add("Suzhou, China");
//Kent's check
AmazingRace.contains('Suzhou, China'); //trueAmazingRace.contains('Hanoi, Vietnam'); //falseAmazingRace.add('Hanoi, Vietnam');AmazingRace.contains('Seattle, Washington'); //falseAmazingRace.add('Seattle, Washington');AmazingRace.contains('North Pole'); // falseAmazingRace.add('North Pole');

Genial, jetzt hat Kent die Möglichkeit, Werte vor dem Hinzufügen zu überprüfen, um Duplikate zu vermeiden.

Abgesehen davon fragen Sie sich vielleicht, warum Sie nicht einfach die Methode includes in der Methode add verwendet haben, um doppelte Ergänzungen zu vermeiden. Wenn Sie eine verknüpfte Liste oder eine andere Datenstruktur implementieren, können Sie theoretisch jede gewünschte zusätzliche Funktionalität hinzufügen.

Sie können sogar native Methoden für vorhandene Strukturen ändern. Probieren Sie das Folgende in einer REPL aus:

Array.prototype.push = () => { return 'cat';}
let arr = [];arr.push('eggs'); // returns 'cat';

Der Grund, warum wir keines dieser Dinge tun, liegt in vereinbarten Standards. Im Wesentlichen erwarten Entwickler, wie bestimmte Methoden funktionieren sollen.

Da unsere verknüpfte Listenklasse nicht in JavaScript enthalten ist, haben wir mehr Freiheit bei der Implementierung, aber es gibt immer noch grundlegende Erwartungen, wie Datenstrukturen wie diese funktionieren sollten. Verknüpfte Listen speichern nicht von Natur aus eindeutige Werte. Aber sie haben Methoden wie enthält , die es uns ermöglichen, die Eindeutigkeit in unserer Liste vorab zu überprüfen und aufrechtzuerhalten.

Kent meldet sich mit seiner Liste der Ziele bei Ihnen, aber einige davon sind fraglich. Zum Beispiel ist der Nordpol möglicherweise nicht das beste Ziel für Amazing Race.

Sie entscheiden sich also, eine Methode zu entwickeln, um einen Knoten entfernen zu können. Es ist wichtig zu bedenken, dass Sie nach dem Entfernen des Knotens die Verknüpfung der Liste aufheben und erneut verknüpfen müssen, was vor und nach dem entfernten Knoten geschehen ist.

class Node { constructor(value) { this.value = value; this.next = null; }}class LinkedList { constructor() { this._head = null; this._tail = null; this._length = 0; } add(value) { let node = new Node(value); if(!this._head && !this._tail){ this._head = node; this._tail = this._head; }else{ this._tail.next = node; this._tail = this._tail.next; } this._length++; } remove(value) { if(this.contains(value)){ // see if our value exists let current = this._head; // begin at start of list let previous = this._head; while(current){ // check each node if(current.value === value){ if(this._head === current){ // if it's the head this._head = this._head.next; // reset the head this._length--; // update the length return; // break out of the loop } if(this._tail === current){ // if it's the tail node this._tail = previous; // make sure to reset it } previous.next = current.next; // unlink (see img below) this._length--; // update the length return; // break out of } previous = current; // look at the next node current = current.next; // ^^ } } } contains(value){ let node = this._head; while(node){ if(node.value === value){ return true; } node = node.next; } return false; } size() { return this._length; } }
const AmazingRace = new LinkedList();AmazingRace.add("Colombo, Sri Lanka");AmazingRace.add("Lagos, Nigeria");AmazingRace.add("Surat, India");AmazingRace.add("Suzhou, China");AmazingRace.add('Hanoi, Vietnam');AmazingRace.add('Seattle, Washington');AmazingRace.add('North Pole');
//Kent's check
AmazingRace.remove('North Pole');

In dieser Entfernungsfunktion steckt viel Code . Im Wesentlichen läuft es auf Folgendes hinaus:

  1. wenn der Wert in der Liste vorhanden ist…
  2. Durchlaufen Sie die verknüpfte Liste und verfolgen Sie den vorherigen und aktuellen Knoten
  3. dann, wenn es eine Übereinstimmung gibt →

4A. wenn es der Kopf ist

  • Setzen Sie den Kopf auf den nächsten Knoten in der Liste zurück
  • Aktualisieren Sie die Länge
  • aus der Schleife ausbrechen

4B. wenn es der Schwanz ist

  • Setzen Sie den Schwanz auf den vorherigen Knoten in der Liste zurück
  • Trennen Sie die Verknüpfung des Knotens, indem Sie die Zeiger wie unten gezeigt zurücksetzen

4C. Wenn es keine Übereinstimmung ist → iterieren Sie weiter

  • Machen Sie den nächsten Knoten aktuell
  • Machen Sie den aktuellen Knoten zum vorherigen

Eine letzte Anmerkung: Sie haben möglicherweise festgestellt, dass Sie den Knoten nicht tatsächlich gelöscht haben. Sie haben gerade die Verweise darauf entfernt. Nun, das ist in Ordnung, denn sobald alle Verweise auf ein Objekt entfernt wurden, hilft uns der Garbage Collector, es aus dem Speicher zu entfernen. Hier können Sie sich über die Speicherbereinigung informieren.

Mit der jetzt implementierten Entfernungsmethode können Sie diesen kleinen Code unten ausführen, um sicherzustellen, dass die Teilnehmer nicht erfrieren oder den Weihnachtsmann versehentlich stören, während er sich auf die diesjährigen Feierlichkeiten vorbereitet.

AmazingRace.remove('North Pole');

Du hast es geschafft! Sie haben eine einfache Implementierung einer verknüpften Liste erstellt. Sie können die Liste durch Hinzufügen von Elementen erweitern und durch Entfernen von Elementen verkleinern - alles basierend auf dem Wert des Elements.

Wenn Sie hinzufügen können, können Sie die verknüpfte Liste erweitern, um Werte am Anfang, Ende oder an einem beliebigen Punkt dazwischen einzufügen.

Sie haben alles, was Sie brauchen, um diese Methoden zu implementieren. Die Namen und Argumente für diese Methoden sollten ungefähr so ​​aussehen:

addHead(value) {
}
insertAfter(target, value){
}

Fühlen Sie sich frei, Ihre Implementierungen in den Kommentaren unten zu teilen?

Eine Zeitkomplexitätsanalyse der Warteschlangenmethoden

Hier ist noch einmal der Code:

class LinkedList { constructor() { this._head = null; this._tail = null; this._length = 0; } add(value) { let node = new Node(value); if(!this._head && !this._tail){ this._head = node; this._tail = this._head; }else{ this._tail.next = node; this._tail = this._tail.next; } this._length++; } remove(value) { if(this.contains(value)){ let current = this._head; let previous = this._head; while(current){ if(current.value === value){ if(this._head === current){ this._head = this._head.next; this._length--; return; } if(this._tail === current){ this._tail = previous; } previous.next = current.next; this._length--; return; } previous = current; current = current.next; } } } contains(value){ let node = this._head; while(node){ if(node.value === value){ return true; } node = node.next; } return false; } size() { return this._length; }
// To Be Implemented
addHead(value) {
}
insertAfter(target, value){
}

Hinzufügen ist O (1): Da Sie dank der Eigenschaft tail immer das letzte Element in der Liste kennen, müssen Sie die Liste nicht durchlaufen.

Entfernen ist O (n): Im schlimmsten Fall müssen Sie die gesamte Liste durchlaufen, um den zu entfernenden Wert zu finden. Ein großer Teil ist jedoch, dass das tatsächliche Entfernen des Knotens O (1) ist, da Sie nur Zeiger zurücksetzen.

Enthält ist O (n): Sie müssen die gesamte Liste durchlaufen, um zu überprüfen, ob der Wert in Ihrer Liste vorhanden ist.

addHead is O(1): Similar to our add method above, we always know the position of the head, so no iteration necessary.

insertAfter is O(n): Similar to our Remove method above, you’ll have to iterate over the entire list to find the target node that your value should be inserted after. Likewise, the actual insertion is O(1) because you’re just resetting pointers.

Linked List vs Array?

Why would you use a linked list instead of an arrays? Arrays technically allow you to do all of the things linked lists do, such as additions, insertions, and removals. Also, all these methods are already readily available to us in JavaScript.

Well, the biggest difference comes in the insertions and removals. Since arrays are indexed, when you perform an insertion or removal in the middle of the array, you have to reset the position of all following values to their new indices.

Imagine inserting into the start or middle of an array 100,000 values long! Insertions and removals like this are extremely expensive. Because of this, linked lists are often preferred for large data sets that are often shifted around.

On the other hand, arrays are great when it comes to finding items (random access) since they are indexed. If you know the position of an item, you can access it in O(1) time via array[position].

Linked lists always require you to iterate over the linked lists sequentially. Given this, arrays are usually preferred for either smaller data sets, or data sets that aren’t shifted around as often.

Time for a quick recap

Linked Lists:

  1. have a tail and head property to track the ends of the list
  2. have an add, addHead, insertAfter, and remove method to manage the contents of your list
  3. have a length property to track how long your linked list is

Further Reading

There are also the doubly-linked list and circular-linked list data structures. You can read about them on Wikipedia.

Also, here’s a solid, quick overview by Vivek Kumar.

Finally, Ian Elliot wrote a walk-through that helps you implementing all of the methods. But see if you can implement addHead() and insertAfter() for your linked list before peeking at this ?