Implementieren von verknüpften Listen in JavaScript

Eine verknüpfte Liste ist eine Datenstruktur, die einem Array sehr ähnlich ist, mit der Ausnahme, dass die Daten nicht an einer einzigen Speicherstelle gespeichert werden. In JavaScript ist jedes Element (Knoten) einer verknüpften Liste ein Objekt, das auf das nächste Element (Knoten) zeigt, das auch auf das nächste Element der verknüpften Liste zeigt, bis das letzte Element auf nichts zeigt (Ende der verknüpften Liste). .

Der Einstiegspunkt zu einer verknüpften Liste wird als Kopf bezeichnet. Der Kopf ist ein Verweis 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.

Bildlich gesehen ist es am besten, verknüpfte Listen wie folgt anzuzeigen;

Dies kann auch als angesehen werden;

// Skeletal View of a Linked List

const list = {
  head: {
    data: 12,
    next: {
      data: 99,
      next: {
        data: 37,
        next: null
      }
    }
  }
}

//  Joshua Ajagbe

1. Musik-Player – Songs im Musik-Player sind mit den vorherigen und nächsten Songs verknüpft. So können Sie Songs entweder vom Anfang oder Ende der Liste abspielen.
2. Bildbetrachter – Vorherige und nächste Bilder sind verknüpft und können über die Schaltflächen „Weiter“ und „Zurück“ aufgerufen werden.
3. Vorherige und nächste Seite in einem Webbrowser – Wir können auf die vorherige und nächste in einem Webbrowser gesuchte URL zugreifen, indem wir die Zurück- und Weiter-Schaltflächen drücken, da sie als verknüpfte Liste verknüpft sind.

Es gibt drei Hauptarten von verketteten Listen, nämlich einfach verkettete Listen, doppelt verkettete Listen und kreisförmig verkettete Listen. Zum Zweck dieses Lernens werden wir die einfach verknüpfte Liste implementieren.

Wie bereits erwähnt, ist eine verknüpfte Liste einfach eine Kombination von Elementen (Knoten), die aufeinander verweisen. Die Grundeinheit einer verketteten Liste ist ein Knoten. Ein Knoten beherbergt die Daten und den Zeiger auf den nächsten Knoten, implementiert wie folgt;

// A Singly Linked List Node
function SinglyLinkedListNode(data) {
  this.data = data;
  this.next = null; // the pointer to the next node...
}

//  Joshua Ajagbe

function SinglyLinkedList() {
  this.head = null;
  this.size = 0; // this helps keep track of the size of the linked list.
}

SinglyLinkedList.prototype.insert = function (data) {
  // checking if linked list is empty
  if(this.head === null){
    this.head = new SinglyLinkedListNode(data);
  } else {
    let temp = this.head;
    this.head = new SinglyLinkedListNode(data);
    this.head.next = temp;
  }
  this.size++; // updating the linked list size.
}

// Let's add method to check if the linked list is empty here. Bonus 
SinglyLinkedList.prototype.isEmpty = function () {
  return this.size === 0;
}

//  Joshua Ajagbe

Das Entfernen eines Knotens aus einer verknüpften Liste wird durch Entfernen seines Zeigers implementiert. Dies bedeutet, dass der vorherige Knoten, der auf den (zu entfernenden) Knoten zeigt, dazu gebracht würde, den (zu entfernenden) Knoten zu überspringen und somit auf den nächsten Knoten zu zeigen.

SinglyLinkedList.prototype.remove = function (data) {
  let currentHead = this.head;
  if(currentHead.data === data) {
    this.head = currentHead.next;
    this.size--;
  } else {
    let prev = currentHead;
    while(currentHead.next) {
      if(currentHead.data === data){
        prev.next = currentHead.next;
        prev = currentHead;
        currentHead = currentHead.next
        this.size--;
        break;
      }
      prev = currentHead;
      currentHead = currentHead.next;
    }
  }
}


//  Joshua Ajagbe

Ich hoffe, dies hat Ihnen geholfen, die verknüpfte Liste und ihre Implementierung zu verstehen.

Falls Sie weitere Erklärungen wünschen, können Sie mich auf LinkedIn kontaktieren:https://www.linkedin.com/in/joshua-ajagbe/oder senden Sie mir eine E-Mail an [email protected].

Viel Spaß beim Lernen