So implementieren Sie einfach verknüpfte Listen in JavaScript

Hallo?, willkommen zurück zu dieser Serie über verlinkte Listen. In unserem letzten Artikel haben wir die Grundlagen verknüpfter Listen kennengelernt, einschließlich ihrer Definition, Terminologie, dem Unterschied zu Arrays und den Typen verknüpfter Listen. Ich habe versprochen, dass wir uns eingehender mit der Implementierung verknüpfter Listen befassen, also fangen wir an.

Kursübersicht

1. Einführung
2. Implementierung einfach verknüpfter Listen
   • Neuen Knoten erstellen
   • Am Anfang einfügen
   • Am Ende einfügen
   • Knoten löschen
   • Nach einem Knoten suchen
   • Die Liste durchqueren
3. Fazit

Einführung

Wie wir im vorherigen Artikel erfahren haben, sind verknüpfte Listen grundlegende Datenstrukturen in der Welt der Programmierung. Sie bestehen aus Knoten, wobei jeder Knoten Daten und einen Verweis (oder Link) auf den nächsten Knoten (in einer einfach verknüpften Liste) oder sowohl den nächsten als auch den vorherigen Knoten (in einer doppelt verknüpften Liste) in der Sequenz enthält. Im Gegensatz zu Arrays speichern verknüpfte Listen Elemente nicht an zusammenhängenden Speicherorten, was effiziente Einfügungen und Löschungen ermöglicht.

Das Verständnis des Konzepts einer verknüpften Liste ist entscheidend für die Beherrschung von Datenstrukturen und Algorithmen. In diesem Artikel befassen wir uns eingehender mit der Implementierung verknüpfter Listen und beginnen mit den Grundlagen einer einfach verknüpften Liste.

Implementierung einfach verknüpfter Listen

Eine einfach verknüpfte Liste ist die einfachste Art einer verknüpften Liste, bei der jeder Knoten auf den nächsten Knoten in der Sequenz zeigt. Genau wie im Bild unten.

Jetzt ist es an der Zeit, mit der Implementierung unserer grundlegenden Operationen für einfach verknüpfte Listen zu beginnen. Sollen wir?

Neuen Knoten erstellen

Beginnen wir mit der Erstellung einer neuen Node-Klasse. Die Node-Klasse verfügt über einen Konstruktor, der die Daten für den Knoten aufnimmt, und einen nächsten Zeiger, der zunächst auf Null gesetzt ist.

// Node class for Singly Linked List
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

Diese neu erstellte Node-Klasse (die einen Knoten in der verknüpften Liste darstellt) kann wie folgt visualisiert werden.

Bevor wir fortfahren, erstellen wir eine neue Instanz unserer SinglyLinkedList-Klasse, die unsere verknüpften Listenoperationen enthält.

// Singly Linked List class
class SinglyLinkedList {
  constructor() {
    this.head = null;
  }

  // Operations come here ?
}

Am Anfang einfügen

class SinglyLinkedList {
  constructor() {
    this.head = null;
  }
  // Previous `SinglyLinkedList` class codes here ?
  // .
  // .
  // .
  // Insert at the beginning
  insertAtBeginning(data) {
    const newNode = new Node(data); // Create a new node with the given data
    newNode.next = this.head; // Set the new node's next pointer to the current head
    this.head = newNode; // Update the head to be the new node
  }

  // Other operations come here ?
  // .
  // .
  // .
}

Erklärung: Das Einfügen am Anfang ist so, als ob sich jemand Neues ganz vorne in die Reihe einreiht. Sie werden zur neuen ersten Person und verlinken zur vorherigen ersten Person.

Am Ende einfügen

class SinglyLinkedList {
  constructor() {
    this.head = null;
  }
  // Previous `SinglyLinkedList` class codes here ?
  // .
  // .
  // .
  // Insert at the end
  insertAtEnd(data) {
    const newNode = new Node(data); // Create a new node with the given data

    // check if the list does not have a head i.e the list is empty
    // NOTE: Every non-empty linked list will have a head
    if (!this.head) {
      this.head = newNode; // If the list is empty, set the new node as the head
      return;
    }
    let current = this.head; // Start at the head of the list
    while (current.next) {
      current = current.next; // Move to the next node in the list by updating the current node
    }
    current.next = newNode; // Set the next pointer of the last node to the new node
  }

  // Other operations come here ?
  // .
  // .
  // .
}

Erklärung: Das Einfügen am Ende ist so, als ob jemand ganz am Ende in die Zeile einsteigt. Wir müssen bis zum Ende gehen, um die letzte Person zu finden, und sie dann mit der neuen Person verknüpfen.

Löschen Sie einen Knoten

class SinglyLinkedList {
  constructor() {
    this.head = null;
  }

  // Previous `SinglyLinkedList` class codes here ?
  // .
  // .
  // .

  // Delete a node
  deleteNode(data) {
    if (!this.head) return; // If the list is empty, do nothing
    if (this.head.data === data) {
      this.head = this.head.next; // If the node to delete is the head, update the head to the next node
      return;
    }
    let current = this.head;
    while (current.next) {
      if (current.next.data === data) {
        current.next = current.next.next; // If the node to delete is found, update the next pointer to skip it
        return;
      }
      current = current.next;
    }
  }

  // Other operations come here ?
  // .
  // .
  // .
}

Erläuterung: Das Löschen eines Knotens ist so, als würde sich jemand mitten in der Leitung dazu entschließen, ihn zu verlassen. Wir finden diese Person und verbinden die Person vor ihr mit der Person nach ihr.

Suchen Sie nach einem Knoten

class SinglyLinkedList {
  constructor() {
    this.head = null;
  }

  // Previous `SinglyLinkedList` class codes here ?
  // .
  // .
  // .

  // Search note
  search(data) {
    let current = this.head; // Start at the head of the list
    while (current) {
      if (current.data === data) {
        // If the data is found, return true
        return true;
      }
      current = current.next; // Move to the next node
    }
    return false;
  }

  // Other operations come here ?
  // .
  // .
  // .
}

Erklärung: Die Suche nach einem Knoten ist wie der Versuch, eine bestimmte Person in der Zeile zu finden. Wir beginnen vorne und fragen jede Person, bis wir sie finden oder das Ende erreichen.

Durchlaufen Sie die Liste

class SinglyLinkedList {
  constructor() {
    this.head = null;
  }
  // Previous `SinglyLinkedList` class codes here ?
  // .
  // .
  // .
  traverse() {
    let current = this.head; // Start at the head of the list
    while (current) {
      console.log(current.data); // Print the data of the current node
      current = current.next; // Move to the next node
    }
  }
}

// End of class

Erklärung: Das Überqueren ist, als würde man die Linie entlanggehen und jede Person begrüßen. Wir beginnen vorne und machen weiter, bis wir das Ende erreichen.

Abschluss

In diesem Artikel haben wir die grundlegenden Operationen verknüpfter Listen und deren Implementierung in JavaScript kennengelernt. Im nächsten Artikel erfahren wir mehr über doppelt verknüpfte Listen.

Denken Sie daran, dass das Beherrschen verknüpfter Listen Übung erfordert. Lösen Sie weiterhin Probleme und implementieren Sie diese Datenstrukturen in verschiedenen Szenarien.

Bleiben Sie auf dem Laufenden und verbunden

Um sicherzustellen, dass Sie keinen Teil dieser Serie verpassen und um mit mir in Kontakt zu treten, um ausführlichere Diskussionen über Softwareentwicklung (Web, Server, Mobile oder Scraping/Automatisierung), Datenstrukturen und Algorithmen sowie andere spannende Technologien zu führen Themen, folge mir auf:

• GitHub
• Linkedin
• X (Twitter)

Bleiben Sie dran und viel Spaß beim Programmieren ?‍??

Das obige ist der detaillierte Inhalt vonSo implementieren Sie einfach verknüpfte Listen in JavaScript. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!