So implementieren Sie eine verknüpfte Liste in JavaScript

Wenn Sie Datenstrukturen lernen, ist eine verknüpfte Liste eine Datenstruktur, die Sie kennen sollten. Wenn Sie es nicht wirklich verstehen oder nicht wissen, wie es in JavaScript implementiert ist, hilft Ihnen dieser Artikel.

In diesem Artikel werden wir diskutieren, was eine verknüpfte Liste ist, wie sie sich von einem Array unterscheidet und wie sie in JavaScript implementiert wird. Lass uns anfangen.

Was ist eine verknüpfte Liste?

Eine verknüpfte Liste ist eine lineare Datenstruktur ähnlich einem Array. Im Gegensatz zu Arrays werden Elemente jedoch nicht an einem bestimmten Speicherort oder Index gespeichert. Vielmehr ist jedes Element ein separates Objekt, das einen Zeiger oder einen Link zum nächsten Objekt in dieser Liste enthält.

Jedes Element (allgemein als Knoten bezeichnet) enthält zwei Elemente: die gespeicherten Daten und eine Verknüpfung zum nächsten Knoten. Die Daten können einen beliebigen gültigen Datentyp haben. Sie können dies in der folgenden Abbildung sehen.

Bild einer verknüpften Liste

Der Einstiegspunkt in eine verknüpfte Liste wird als Kopf bezeichnet. Der Kopf ist eine Referenz auf den ersten Knoten in der verknüpften Liste. Der letzte Knoten in der Liste zeigt auf null. Wenn eine Liste leer ist, ist der Kopf eine Nullreferenz.

In JavaScript sieht eine verknüpfte Liste folgendermaßen aus:

const list = { head: { value: 6 next: { value: 10 next: { value: 12 next: { value: 3 next: null } } } } } };

Ein Vorteil von verknüpften Listen

  • Knoten können einfach aus einer verknüpften Liste entfernt oder hinzugefügt werden, ohne die gesamte Datenstruktur neu zu organisieren. Dies ist ein Vorteil gegenüber Arrays.

Nachteile verknüpfter Listen

  • Suchvorgänge in verknüpften Listen sind langsam. Im Gegensatz zu Arrays ist der wahlfreie Zugriff auf Datenelemente nicht zulässig. Auf Knoten wird ab dem ersten Knoten nacheinander zugegriffen.
  • Aufgrund der Speicherung der Zeiger wird mehr Speicher als Arrays benötigt.

Arten von verknüpften Listen

Es gibt drei Arten von verknüpften Listen:

  • Einfach verknüpfte Listen : Jeder Knoten enthält nur einen Zeiger auf den nächsten Knoten. Darüber haben wir bisher gesprochen.
  • Doppelt verknüpfte Listen : Jeder Knoten enthält zwei Zeiger, einen Zeiger auf den nächsten Knoten und einen Zeiger auf den vorherigen Knoten.
  • Kreisförmige verknüpfte Listen : Zirkuläre verknüpfte Listen sind eine Variation einer verknüpften Liste, bei der der letzte Knoten auf den ersten Knoten oder einen anderen Knoten davor zeigt und so eine Schleife bildet.

Implementieren eines Listenknotens in JavaScript

Wie bereits erwähnt, enthält ein Listenknoten zwei Elemente: die Daten und den Zeiger auf den nächsten Knoten. Wir können einen Listenknoten in JavaScript wie folgt implementieren:

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

Implementieren einer verknüpften Liste in JavaScript

Der folgende Code zeigt die Implementierung einer verknüpften Listenklasse mit einem Konstruktor. Beachten Sie, dass der Kopf auf Null initialisiert wird, wenn der Kopfknoten nicht übergeben wird.

class LinkedList { constructor(head = null) { this.head = head } }

Alles zusammenfügen

Erstellen wir eine verknüpfte Liste mit der Klasse, die wir gerade erstellt haben. Zunächst schaffen wir zwei Listenknoten, node1und node2und ein Zeiger vom Knoten 1 bis 2 - Knoten.

let node1 = new ListNode(2) let node2 = new ListNode(5) node1.next = node2

Als nächstes erstellen wir eine verknüpfte Liste mit dem node1.

let list = new LinkedList(node1)

Versuchen wir, auf die Knoten in der gerade erstellten Liste zuzugreifen.

console.log(list.head.next.data) //returns 5

Einige LinkedList-Methoden

Als nächstes werden wir vier Hilfsmethoden für die verknüpfte Liste implementieren. Sie sind:

  1. Größe()
  2. klar()
  3. getLast ()
  4. getFirst ()

1. Größe ()

Diese Methode gibt die Anzahl der in der verknüpften Liste vorhandenen Knoten zurück.

size() { let count = 0; let node = this.head; while (node) { count++; node = node.next } return count; } 

2. clear ()

Diese Methode leert die Liste.

clear() { this.head = null; }

3. getLast ()

Diese Methode gibt den letzten Knoten der verknüpften Liste zurück.

getLast() { let lastNode = this.head; if (lastNode) { while (lastNode.next) { lastNode = lastNode.next } } return lastNode }

4. getFirst ()

Diese Methode gibt den ersten Knoten der verknüpften Liste zurück.

getFirst() { return this.head; }

Zusammenfassung

In diesem Artikel haben wir erläutert, was eine verknüpfte Liste ist und wie sie in JavaScript implementiert werden kann. Wir haben auch die verschiedenen Arten von verknüpften Listen sowie ihre allgemeinen Vor- und Nachteile erörtert.

Ich hoffe es hat euch Spaß gemacht.

Möchten Sie benachrichtigt werden, wenn ich einen neuen Artikel veröffentliche? Hier klicken.