Implementierung von LinkedList in Javascript

Eine verknüpfte Liste ist eine Datenstruktur, die aus einer Folge von Elementen besteht, wobei jedes Element einen Verweis (oder „Link“) auf das nächste Element in der Folge enthält. Das erste Element heißt Kopf und das letzte Element heißt Schwanz.

Verknüpfte Liste hat viele Vorteile im Vergleich zu anderen Datenstrukturen. Schauen wir uns nun an, wie man eine verknüpfte Liste mit JavaScript implementiert.

Definieren Sie die Node-Klasse und die LinkedList-Klasse

Dies ist grundsätzlich eine Voraussetzung für die Implementierung verknüpfter Listen in JavaScript. In diesem Schritt müssen Sie zwei Klassen erstellen, eine für Knoten und eine andere für verknüpfte Listen.

Die Node-Klasse repräsentiert einen einzelnen Knoten in einer verknüpften Liste. Es hat zwei Eigenschaften: data und next. Das Datenattribut wird zum Speichern der tatsächlichen Daten des Knotens verwendet, während das nächste Attribut eine Referenz auf den nächsten Knoten in der Liste ist. Die Node-Klasse besteht aus einem Konstruktor, der die Daten und nächsten Eigenschaften initialisiert, wenn ein neuer Node erstellt wird.

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

Die LinkedList-Klasse ist eine Darstellung der verknüpften Liste selbst. Es verfügt über ein Head-Attribut, das auf den ersten Knoten in der Liste verweist. Die LinkedList-Klasse verfügt außerdem über einen Konstruktor, der die Head-Eigenschaft initialisiert, wenn eine neue LinkedList erstellt wird.

class LinkedList {
   constructor() {
      this.head = null;
      this.tail = null;
      this.length = 0;
   }
}

Die LinkedList-Klasse enthält außerdem eine Methode, mit der Sie Knoten in der Liste einfügen, löschen und durchsuchen können, während andere Vorgänge wie das Drucken der Liste, das Zählen von Elementen, das Umkehren der Liste usw. möglich sind.

Linkliste drucken

Sie können die Elemente einer verknüpften Liste drucken, indem Sie die verknüpfte Liste durchlaufen und die Daten jedes Knotens drucken.

printAll() {
   let current = this.head;
   while (current) {
      console.log(current.data);
      current = current.next;
   }
}

Knoten zur verknüpften Liste hinzufügen

Es gibt mehrere Möglichkeiten, Daten zu einer verknüpften Liste hinzuzufügen, je nachdem, wo der neue Knoten eingefügt werden muss, wie folgt:

Knoten am Anfang der verknüpften Liste hinzufügen

Um einen Knoten/ein Element am Anfang einer verknüpften Liste hinzuzufügen, setzen Sie nach dem Erstellen eines neuen Knotens mit Daten einfach dessen nächste Eigenschaft auf den aktuellen Kopf der verknüpften Liste. Anschließend können Sie den Kopf der verknüpften Liste auf den neuen Knoten aktualisieren. Dies wird auch als Kopfeinfügung einer verknüpften Liste bezeichnet und ist die grundlegendste Art der Datenaddition. Dies geschieht einfach durch Aufruf der unten definierten Add-Funktion.

add(data) {
   const newNode = new Node(data);
   if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
   } else {
      this.tail.next = newNode;
      this.tail = newNode;
   }
   this.length++;
   return this;
}

Knoten am Ende der verknüpften Liste hinzufügen

Um einen Knoten/ein Element am Ende der verknüpften Liste hinzuzufügen, müssen wir die verknüpfte Liste durchlaufen und den letzten Knoten finden. Erstellen Sie anschließend einen neuen Knoten mit den Daten und setzen Sie die nächste Eigenschaft des letzten Knotens auf den neuen Knoten. Dies wird auch als Tail-Insertion einer verknüpften Liste bezeichnet und ist die zweitgrundlegenste Art der Datenaddition. Dies geschieht einfach durch den Aufruf der unten definierten addToTail-Funktion.

addToTail(data) {
   let newNode = new Node(data);
   if (this.head === null) {
      this.head = newNode;
      return;
   }
   let current = this.head;
   while (current.next !== null) {
      current = current.next;
   }
   current.next = newNode;
}

Knoten an einem bestimmten Ort hinzufügen

Um einen Knoten/ein Element an einer bestimmten Position in der verknüpften Liste hinzuzufügen, können Sie die verknüpfte Liste durchlaufen, um den Knoten an der Position vor dem Einfügepunkt zu finden, einen neuen Knoten mit den Daten erstellen und das nächste Attribut des neuen Knotens festlegen zum aktuellen Knoten an dieser Position und ändern Sie das Attribut des vorherigen Knotens. Das nächste Attribut wird auf den neuen Knoten gesetzt.

addAtPosition(data, position) {
   let newNode = new Node(data);
   if (position === 1) {
      newNode.next = this.head;
      this.head = newNode;
      return;
   }
   let current = this.head;
   let i = 1;
   while (i < position - 1 && current) {
      current = current.next;
      i++;
   }
   if (current) {
      newNode.next = current.next;
      current.next = newNode;
   }
}

Beispiel (Knoten zur verknüpften Liste hinzufügen)

Im folgenden Beispiel haben wir Knoten am Anfang, am Ende und an bestimmten Positionen hinzugefügt.

class Node {
   constructor(data) {
      this.data = data;
      this.next = null;
   }
}
class LinkedList {
   constructor() {
      this.head = null;
      this.tail = null;
      this.length = 0;
   }
   
   // function to add data to linked list
   add(data) {
      const newNode = new Node(data);
      if (!this.head) {
         this.head = newNode;
         this.tail = newNode;
      } else {
         this.tail.next = newNode;
         this.tail = newNode;
      }
      this.length++;
      return this;
   }
   
   //function to add data to tail
   addToTail(data) {
      let newNode = new Node(data);
      if (this.head === null) {
         this.head = newNode;
         return;
      }
      let current = this.head;
      while (current.next !== null) {
         current = current.next;
      }
      current.next = newNode;
   }
   
   // function to insert data to linked list at a particular index
   addAtPosition(data, position) {
      let newNode = new Node(data);
      if (position === 1) {
         newNode.next = this.head;
         this.head = newNode;
         return;
      }
      let current = this.head;
      let i = 1;
      while (i < position - 1 && current) {
         current = current.next;
         i++;
      }
      if (current) {
         newNode.next = current.next;
         current.next = newNode;
      }
   }
   
   // this function is used to iterate over the entire linkedlist and print
   it
   printAll() {
      let current = this.head;
      while (current) {
         console.log(current.data);
         current = current.next;
      }
   }
}
const list = new LinkedList();

// add elements to the linkedlist
list.add("node1");
list.add("node2");
list.add("node3");
list.add("node4");
console.log("Initial List:");
list.printAll();
console.log("List after adding nodex at position 2");
list.addAtPosition("nodex",2);
list.printAll();
console.log("List after adding nodey to tail");
list.addToTail("nodey");
list.printAll();

Ausgabe

Initial List:
node1
node2
node3
node4

List after adding nodex at position 2
node1
nodex
node2
node3
node4
List after adding nodey to tail
node1
nodex
node2
node3
node4
nodey

Knoten löschen

Daten können auf Wunsch auch über verschiedene Methoden gelöscht werden.

Bestimmten Knoten löschen

Um einen bestimmten Knoten aus der verknüpften Liste zu löschen, müssen wir die verknüpfte Liste durchlaufen und den Knoten vor dem zu löschenden Knoten finden, seine nächste Eigenschaft aktualisieren, um den zu löschenden Knoten zu überspringen, und den Verweis auf den nächsten Knoten aktualisieren. Dadurch wird der Knoten basierend auf dem Wert gelöscht.

remove(data) {
   if (!this.head) {
      return null;
   }
   if (this.head.data === data) {
      this.head = this.head.next;
      this.length--;
      return this;
   }
   let current = this.head;
   while (current.next) {
      if (current.next.data === data) {
         current.next = current.next.next;
         this.length--;
         return this;
      }
      current = current.next;
   }
   return null;
}

Knoten an bestimmten Standorten löschen

Um einen Knoten an einer bestimmten Position in der verknüpften Liste zu löschen, müssen wir die verknüpfte Liste durchlaufen und den Knoten vor dem zu löschenden Knoten finden, seine nächste Eigenschaft aktualisieren, um den zu löschenden Knoten zu überspringen, und dann den Verweis auf aktualisieren der nächste Knoten. Dadurch werden Knoten grundsätzlich basierend auf ihrem Indexwert gelöscht.

removeAt(index) {
   if (index < 0 || index >= this.length) return null;
   if (index === 0) return this.remove();
   let current = this.head;
   for (let i = 0; i < index - 1; i++) {
      current = current.next;
   }
   current.next = current.next.next;
   this.length--;
   return this;
}

Beispiel (Knoten aus linearer Liste entfernen)

Im folgenden Beispiel implementieren wir das Löschen bestimmter Knoten und Knoten an bestimmten Standorten.

class Node {
   constructor(data) {
      this.data = data;
      this.next = null;
   }
}
class LinkedList {
   constructor() {
      this.head = null;
      this.tail = null;
      this.length = 0;
   }
   
   // function to add data to linked list
   add(data) {
      const newNode = new Node(data);
      if (!this.head) {
         this.head = newNode;
         this.tail = newNode;
      } 
      else {
         this.tail.next = newNode;
         this.tail = newNode;
      }
      this.length++;
      return this;
   }
   
   // function to remove data from linked list
   remove(data) {
      if (!this.head) {
         return null;
      }
      if (this.head.data === data) {
         this.head = this.head.next;
         this.length--;
         return this;
      }
      let current = this.head;
      while (current.next) {
         if (current.next.data === data) {
            current.next = current.next.next;
            this.length--;
            return this;
         }
         current = current.next;
      }
      return null;
   }
   
   // function to remove from a particular index 
      removeAt(index) {
      if (index < 0 || index >= this.length) return null;
      if (index === 0) return this.remove();
      let current = this.head;
      for (let i = 0; i < index - 1; i++) {
         current = current.next;
      }
      current.next = current.next.next;
      this.length--;
      return this;
   }
   
   // this function is used to iterate over the entire linkedlist and print it
   printAll() {
      let current = this.head;
      while (current) {
         console.log(current.data);
         current = current.next;
      }
   }
}
const list = new LinkedList();
// add elements to the linkedlist
list.add("node1");
list.add("node2");
list.add("node3");
list.add("node4");
console.log("Initial List:");
list.printAll();
console.log("List after removing node2");
list.remove("node2");
list.printAll();
console.log("List after removing node at index 2");
list.removeAt(2);
list.printAll();

Ausgabe

Initial List:
node1
node2
node3
node4
List after removing node2
node1
node3
node4

List after removing node at index 2
node1
node3

Fazit

Die Implementierung einer verknüpften Liste in JavaScript umfasst das Erstellen einer Node-Klasse zur Darstellung jedes Knotens in der Liste und einer LinkedList-Klasse zur Darstellung der Liste selbst sowie das Hinzufügen von Methoden zur LinkedList-Klasse, um Vorgänge wie das Hinzufügen und Entfernen von Daten und das Drucken der Liste auszuführen. Es ist wichtig, auch Grenzfälle zu berücksichtigen und diese bei der Implementierung entsprechend zu behandeln. Je nach Anwendungsfall gibt es mehrere Möglichkeiten, Daten zu einer LinkedList hinzuzufügen oder daraus zu entfernen.

Das obige ist der detaillierte Inhalt vonImplementierung von LinkedList in Javascript. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!