Verknüpfte Liste mit Datenstrukturen und Algorithmen

Tag 1

Grundlegende Datenstrukturen

Wir lernen nicht nur auf herkömmliche Weise etwas über verknüpfte Listen; Wir werden auch untersuchen, was die Klassen Node und LinkedList sind und alle Operationen, die mit ihnen ausgeführt werden können.

Was ist eine verknüpfte Liste?

Eine verknüpfte Liste ist eine Sammlung von Elementen, die als Knoten bezeichnet werden, wobei jeder Knoten ein Datenelement und einen Verweis (oder Link) auf den nächsten Knoten in der Sequenz enthält.
Eine verknüpfte Liste ist eine lineare Datenstruktur, in der Elemente in Knoten gespeichert sind. Jeder Knoten enthält zwei Teile:
Im Gegensatz zu Arrays speichern *verknüpfte Listen keine Elemente an zusammenhängenden Speicherorten.
*Stattdessen zeigt jeder Knoten auf den nächsten Knoten, was eine dynamische Speichernutzung und ein einfaches Einfügen oder Löschen von Elementen ermöglicht.

Kernpunkt der verknüpften Liste

1. Knotenstruktur: Verknüpfte Listen bestehen aus Knoten, von denen jeder einen Wert und einen Verweis auf den nächsten Knoten enthält. Das Erkunden der Struktur und Eigenschaften von Knoten hilft zu verstehen, wie verknüpfte Listen Daten organisieren und speichern.
2. Kopf und Schwanz: Der erste Knoten in einer verknüpften Liste wird als Kopf bezeichnet, während der letzte Knoten als Schwanz bezeichnet wird. Das Verständnis der Eigenschaften und Funktionalität der Kopf- und Endknoten ist für das effiziente Durchlaufen und Bearbeiten verknüpfter Listen von entscheidender Bedeutung.

Hauptmerkmale:

Dynamische Größe:Es kann je nach Bedarf wachsen oder schrumpfen.
Sequentieller Zugriff: Der Zugriff auf Elemente erfordert das Durchqueren vom ersten Knoten (Kopf).

Arten von verknüpften Listen:

Es gibt drei Grundformen verknüpfter Listen
1. Einfach verknüpfte Listen.
2. Doppelt verknüpfte Listen.
3. Zirkulär verknüpfte Listen.

In diesem Artikel werden wir einfach verknüpfte Listen untersuchen.

Einfach verknüpfte Listen.

Jeder Knoten hat einen Verweis auf den nächsten Knoten.

• Jeder Knoten enthält:
  • Daten (der Wert, den Sie speichern möchten).
  • Ein nächster Zeiger, der auf den nächsten Knoten in der Sequenz zeigt.
• Der nächste Zeiger des letzten Knotens ist null, da es keinen Knoten danach gibt.

Analogie aus dem wirklichen Leben: Pfeil – Sobald ein Pfeil abgeschossen wird, kann er sich nur vorwärts bewegen.
Sobald der Pfeil losgelassen wird, fliegt er in einer geraden Linie und kann nicht zurückkehren.
Ähnlich verhält es sich mit der einfach verknüpften Liste: Sobald Sie von einem Knoten zum nächsten wechseln, können Sie nicht mehr zurückgehen – Sie können nur weiter vorwärts gehen.

[Data | Next] -> [Data | Next] -> [Data | Next] -> null

Operationen auf einfach verknüpften Listen

• Durchquerung
• Suchen
• Länge
• Einfügung:
  • Am Anfang einfügen
  • Am Ende einfügen
  • An einer bestimmten Position einfügen
• Löschung:
  • Von Anfang an löschen
  • Am Ende löschen
  • Einen bestimmten Knoten löschen

Einfügung:

Am Anfang einfügen

Lassen Sie uns eine Node-Klasse erstellen

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

Lassen Sie uns die Node-Klasse aufschlüsseln.

**Die Node-Klasse repräsentiert jedes einzelne Element in einer verknüpften Liste. Jeder Knoten enthält zwei Eigenschaften:

Eigenschaften:

- Daten: Dies enthält den im Knoten gespeicherten Wert (z. B. eine Zahl, eine Zeichenfolge oder ein Objekt).
- Weiter: Dies enthält eine Referenz (oder einen Zeiger) auf den nächsten Knoten in der verknüpften Liste. Anfangs ist es auf null gesetzt, da ein Knoten beim Erstellen noch mit keinem anderen Knoten verknüpft ist.

Abbauen:

Konstruktor (Konstruktor(Daten)):
Dies ist eine spezielle Methode in JavaScript-Klassen, die aufgerufen wird, wenn eine neue Instanz der Node-Klasse erstellt wird.
Der Datenparameter wird beim Erstellen eines neuen Knotens übergeben und speichert den tatsächlichen Wert des Knotens.
this.next = null; Setzt die nächste Eigenschaft zunächst auf Null, da ein Knoten beim Erstellen noch mit keinem anderen Knoten verbunden ist.

Beispiel:

let node1 = new Node(10); // Create a node with the value 10
console.log(node1.data);  // Output: 10
console.log(node1.next);  // Output: null (because it's not linked to any other node yet)

Lassen Sie uns eine SingleLinkList-Klasse erstellen

class SinglyLinkedList {
  constructor() {
    this.head = null; // Initially, the list is empty, so the head is null.
    this.size = 0; // The size is initially 0, as there are no nodes in the list.
  }

  // Insert at the beginning
  insertAtBeginning(data) {
    let newNode = new Node(data); // Create a new node with the given data
    newNode.next = this.head; // The new node's next points to the current head
    this.head = newNode; // Update the head to be the new node
    this.size++; // Increment the size of the list
  }
}

Die SinglyLinkedList-Klasse repräsentiert die gesamte verknüpfte Listenstruktur. Es verwaltet mehrere Knotenobjekte und stellt Methoden zum Arbeiten mit der Liste bereit, z. B. das Einfügen, Löschen und Durchlaufen von Knoten usw..

Eigenschaften:

- Kopf: Dies ist ein Verweis auf den ersten Knoten (oder den „Kopf“) der verknüpften Liste. Anfangs ist es auf Null gesetzt, was bedeutet, dass die Liste leer ist.
- Größe: Dadurch wird verfolgt, wie viele Knoten sich derzeit in der verknüpften Liste befinden. Anfangs ist es auf 0 gesetzt, da die Liste leer ist.

Abbauen:

Konstruktor (constructor()):

this.head = null;: This initializes the linked list with no elements, so the head points to null.
this.size = 0;: The size starts as 0 because there are no nodes in the list.

insertAtBeginning(data): for the sake of simplicity, later on, we will Deep Dive into the insertAtBeginning(data) method
let newNode = new Node(data);: This creates a new node with the value passed in as data.
newNode.next = this.head;: This links the new node to the current head (which could be nullif the list is empty or point to an existing node if the list has elements).
this.head = newNode;: This updates the head of the list to point to the new node, making it the first node in the list.
this.size++;: The size of the linked list is increased by 1 as a new node has been added.

let's Test

let list = new SinglyLinkedList();
list.insertAtBeginning(10); // List becomes: 10
list.insertAtBeginning(20); // List becomes: 20 -> 10
console.log(list.head.data); // Output: 20 (since the head is now the first node with value 20)
console.log(list.size);      // Output: 2 (since there are two nodes in the list)

Linked List deep dive Line by Line.

let's jump into the insertAtBeginning(data) method .

class Node {
  constructor(data) {
    this.data = data;   // Store the data value (like 10, 20, etc.)
    this.next = null;   // Initialize the next pointer as null
  }
}

class SinglyLinkedList {
  constructor() {
    this.head = null;   // Initially, the list is empty, so the head is null
    this.size = 0;      // The size of the list starts at 0
  }

  // Insert at the beginning of the list
  insertAtBeginning(data) {
    // Step 1: Create a new node with the given data
    let newNode = new Node(data); 

    // Explanation:
    // First time: If we insert 10, the newNode looks like this -> Node { data: 10, next: null }
    // Second time: If we insert 20, the newNode looks like this -> Node { data: 20, next: null }

    // Step 2: Point the new node's next property to the current head of the list
    newNode.next = this.head;

    // Explanation:
    // First time: Since the list is empty (this.head is null), newNode's next is set to null.
    // Second time: this.head is now the node with data 10, so newNode’s next will point to the node with data 10. 
    // So it looks like this: Node { data: 20, next: Node { data: 10, next: null } }

    // Step 3: Make the new node the new head of the list
    this.head = newNode;

    // Explanation:
    // First time: Now, the new node becomes the head. The list looks like this: Node { data: 10, next: null }.
    // Second time: The new node (with data 20) becomes the head, and it points to the previous head (which is the node with data 10).

    // Step 4: Increment the size of the list
    this.size++;

    // Explanation:
    // First time: The size is now 1 because there is one node (data 10).
    // Second time: The size becomes 2 because we added another node (data 20).
  }
}

// Example Usage:
let list = new SinglyLinkedList();
list.insertAtBeginning(10);  // First insertion: the list becomes [10]
list.insertAtBeginning(20);  // Second insertion: the list becomes [20 -> 10]

console.log(list);

// Output:
// SinglyLinkedList {
//   head: Node { data: 20, next: Node { data: 10, next: null } },
//   size: 2
// }

Coming soon...

Das obige ist der detaillierte Inhalt vonVerknüpfte Liste mit Datenstrukturen und Algorithmen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!