JavaScript-Programm zum Suchen nach Elementen in einer verknüpften Liste

Eine verknüpfte Liste ist eine lineare Datenstruktur, in der jedes Element (auch Knoten genannt) einen Datenwert und einen Verweis auf den nächsten Knoten in der Liste enthält. Eine häufige Operation für eine verknüpfte Liste besteht darin, nach einem bestimmten Element zu suchen. Dazu müssen Sie die Liste durchgehen und den Datenwert jedes Knotens mit dem Zielelement vergleichen, bis eine Übereinstimmung gefunden wird.

Hier ist ein Beispiel für die Linkliste, die wir in diesem Artikel verwenden werden -

10 -> 20 -> 30 -> 40 -> Leer

In dieser verknüpften Liste enthält jeder Knoten einen Wert und der Pfeil zeigt den nächsten Knoten in der Sequenz an. Die Liste beginnt mit dem Kopfknoten, der den Wert 10 enthält, und endet mit dem Endknoten, der den Wert 40 enthält und auf Null zeigt. Wir werden diese verknüpfte Liste verwenden, um zu demonstrieren, wie man mit JavaScript nach einem Element in einer verknüpften Liste sucht.

Sehen wir uns das Beispiel unten an -

Linked list: 10 -> 20 -> 30 -> 40 -> null
Input: 40
Output: Element found at index 3
Input: 10
Output: Element found at index 0
Input: null
Output: Element not found

Lassen Sie uns nun den Algorithmus zum Erstellen verknüpfter Listen in JavaScript besprechen.

Algorithmus

Schritt 1 – Definieren Sie eine Node-Klasse mit zwei Eigenschaften: value und next. Das Wertattribut stellt die im Knoten gespeicherten Daten dar und das nächste Attribut ist ein Verweis auf den nächsten Knoten in der verknüpften Liste.

Schritt 2 – Definieren Sie eine LinkedList-Klasse mit drei Eigenschaften: Kopf, Schwanz und Länge. Das Head-Attribut repräsentiert den ersten Knoten in der verknüpften Liste, das Tail-Attribut repräsentiert den letzten Knoten in der verknüpften Liste und das Längenattribut repräsentiert die Anzahl der Knoten in der verknüpften Liste.

Schritt 3 – Definieren Sie eine Methode mit dem Namen – fügen Sie sie zur LinkedList-Klasse hinzu, die einen Wert als Parameter akzeptiert. Die Add-Methode sollte einen neuen Knoten mit dem angegebenen Wert erstellen und ihn am Ende der verknüpften Liste hinzufügen.

Schritt 4 – Definieren Sie eine Methode namens „remove“ für die LinkedList-Klasse, die einen Wert als Parameter akzeptiert. Die Methode „remove“ sollte den ersten Knoten mit einem bestimmten Wert in der verknüpften Liste entfernen.

Schritt 5 – Definieren Sie eine Methode namens „Suche“ für die LinkedList-Klasse, die einen Wert als Parameter akzeptiert. Die Suchmethode sollte den ersten Knoten in der verknüpften Liste mit dem angegebenen Wert zurückgeben oder null, wenn der Knoten nicht gefunden wird.

Schritt 6 – Definieren Sie eine Methode namens reverse für die LinkedList-Klasse, die verwendet wird, um die Reihenfolge der Knoten in der verknüpften Liste umzukehren.

Beispiel: Implementieren Sie den obigen Algorithmus mit JavaScript

Das folgende Programm definiert eine Node-Klasse und eine LinkedList-Klasse. Die Node-Klasse erstellt einen neuen Knoten unter Verwendung des angegebenen Datenwerts und einer Referenz auf den nächsten Knoten in der Liste. Die LinkedList-Klasse erstellt eine neue verknüpfte Liste, wobei der Kopfknoten zunächst auf Null zeigt und die Größeneigenschaft auf 0 gesetzt ist. Die Add-Methode fügt am Ende der verknüpften Liste einen neuen Knoten hinzu. Die Suchmethode durchläuft die verknüpfte Liste und gibt den Index des Elements zurück, wenn es gefunden wird, oder eine Meldung, wenn es nicht gefunden wird. Schließlich erstellt das Programm eine neue verknüpfte Liste, fügt ihr Elemente hinzu und sucht nach einem bestimmten Element.

// Define the Node class for a singly linked list
class Node {
   constructor(data) {
      this.data = data;
      this.next = null;
   }
}
// Define the LinkedList class
class LinkedList {
   constructor() {
      this.head = null;
      this.size = 0;
   }
   // Add an element to the linked list
   add(element) {
      const node = new Node(element);
      // If the linked list is empty, set the new node as the head
      if (this.head === null) {
         this.head = node;
      } else {
         // Traverse to the end of the linked list and add the new node
         let current = this.head;
         while (current.next !== null) {
            current = current.next;
         }
         current.next = node;
      }
      this.size++;
   }
   // Search for an element in the linked list
   search(element) {
      let current = this.head;
      let index = 0;
      // Traverse through the linked list until the element is found
      while (current !== null) {
         if (current.data === element) {
            return `Element found at index ${index}`;
         }
         current = current.next;
         index++;
      }
      return "Element not found";
   }
}
// Create a new linked list
const ll = new LinkedList();
// Add elements to the linked list
ll.add(10);
ll.add(20);
ll.add(30);
ll.add(40);
ll.add(50);
// Search for an element in the linked list
const result = ll.search(30);
console.log(result); 

Fazit

Das Verfahren zum Suchen nach Elementen in einer verknüpften Liste mithilfe von JavaScript umfasst das Erstellen einer „LinkedList“-Klasse, die Methoden zum Hinzufügen von Elementen zur Liste und zum Suchen nach Elementen in der Liste definiert. Das Programm verwendet eine While-Schleife, um die verknüpfte Liste zu durchlaufen und das Datenelement in jedem Knoten mit dem gesuchten Element zu vergleichen. Wenn das Element gefunden wird, gibt das Programm den Index des Knotens zurück. Wenn das Element nicht gefunden wird, gibt das Programm „Element nicht gefunden“ zurück.

Das obige ist der detaillierte Inhalt vonJavaScript-Programm zum Suchen nach Elementen in einer verknüpften Liste. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!