JavaScript-Programm zum Sortieren einer verknüpften Liste mit 0, 1 und 2

In diesem Tutorial lernen wir ein JavaScript-Programm zum Sortieren einer verknüpften Liste mit 0, 1 und 2. Sortieralgorithmen sind für jede Programmiersprache unerlässlich, und JavaScript bildet da keine Ausnahme. Das Sortieren einer verknüpften Liste von Nullen, Einsen und Zweien ist ein häufiges Problem, mit dem Entwickler beim Codieren von Interviews und realen Anwendungen konfrontiert sind.

Lassen Sie uns also untersuchen, wie Sie mithilfe der JavaScript-Programmierung eine verknüpfte Liste mit 0, 1 und 2 sortieren.

Was ist Sortieren?

Sortieren ist der Vorgang, bei dem Elemente in einer bestimmten Reihenfolge (aufsteigend oder absteigend) angeordnet werden. Es ist eine grundlegende Operation in der Informatik und hat zahlreiche Anwendungen in realen Szenarien. Sortieralgorithmen werden verwendet, um Daten für eine effiziente Suche zu organisieren, Redundanz zu reduzieren und die räumliche und zeitliche Komplexität zu optimieren.

Hier sind einige Beispiele für die Sortierung in JavaScript:

Beispiel 1 – Sortieren Sie eine Reihe von Zahlen in aufsteigender Reihenfolge:

Input: ar[]= [5, 3, 8, 1, 2, 9]
Output: [1, 2, 3, 5, 8, 9]

Beispiel 2 – Sortieren Sie ein Array von Zeichenfolgen alphabetisch:

Input: ['apple', 'banana', 'orange', 'grape']
Output: ['apple', 'banana', 'grape', 'orange']

Was ist eine verknüpfte Liste?

Eine verknüpfte Liste ist eine lineare Datenstruktur, die aus Knoten besteht, die durch Zeiger miteinander verbunden sind. Jeder Knoten enthält ein Datenelement und einen Verweis auf den nächsten Knoten in der Liste. Verknüpfte Listen werden häufig in dynamischen Datenstrukturen verwendet, bei denen sich die Datengröße häufig ändert.

Problemstellung

Das Ziel besteht darin, die verknüpfte Liste bestehend aus 0, 1 und 2 der Reihe nach anzuordnen und anzuzeigen. Lassen Sie es uns anhand eines Beispiels verstehen:

Beispiel

Input: 1 -> 1 -> 2 -> 0 -> 2 -> 0 -> 1 -> NULL 
Output: 0 -> 0 -> 1 -> 1 -> 1 -> 2 -> 2 -> NULL
Input: 1 -> 1 -> 2 -> 1 -> 0 -> NULL 
Output: 0 -> 1 -> 1 -> 1 -> 2 -> NULL 

Algorithmus zum Sortieren verknüpfter Listen mit 0, 1 und 2

Schritte zum Sortieren der verknüpften Liste von 0, 1 und 2 mithilfe des Zählsortieralgorithmus -

Schritt 1 – Definieren Sie eine Funktion sortList(head), die den Kopf der verknüpften Liste als Eingabe verwendet.

SCHRITT2 – Initialisieren Sie ein Zählarray count[] der Größe 3, wobei alle Elemente gleich 0 sind.

SCHRITT 3 – Durchlaufen Sie die verknüpfte Liste und erhöhen Sie die Anzahl der Knotendaten am entsprechenden Index im Zählarray.

SCHRITT 4 – Durchlaufen Sie die verknüpfte Liste erneut und ersetzen Sie die Knotendaten mit dem niedrigsten Indexwert durch eine Anzahl größer als 0.

Schritt 5 – Reduzieren Sie die Knotendatenanzahl für jeden Austausch.

Schritt 6 – Drucken Sie die verknüpfte Liste vor und nach dem Sortieren aus.

Lassen Sie uns nun versuchen, den obigen Algorithmus anhand eines Beispiels seiner Implementierung mithilfe von JavaScript zu verstehen.

Beispiel

Das folgende JavaScript-Programm sortiert eine verknüpfte Liste mit 0, 1 und 2 mithilfe des Zählsortieralgorithmus. Der Algorithmus zählt zunächst die Häufigkeit des Auftretens von 0, 1 und 2 in der Liste und aktualisiert dann den Wert des Knotens in der Liste basierend auf der Anzahl jedes Werts.

/* Link list node */
class Node {
   constructor(data) {
      this.data = data;
      this.next = null;
   }
}
class LinkedList {
   constructor() {
      this.head = null;
   }
   push(new_data) {
      const new_node = new Node(new_data);
      new_node.next = this.head;
      this.head = new_node;
   }
   printList() {
      let currentNode = this.head;
      let value = "";
      while (currentNode !== null) {
         value += currentNode.data + " -> ";
         currentNode = currentNode.next;
      }
      console.log(value + "null");
   }
   sortList() {
      const count = [0, 0, 0]; // Initialize count of '0', '1' and '2' as 0
      let ptr = this.head;
      while (ptr !== null) {
         count[ptr.data] += 1;
         ptr = ptr.next;
      }
      ptr = this.head;
      let i = 0;
      while (ptr !== null) {
         if (count[i] === 0) {
            ++i;
         } else {
            ptr.data = i;
            --count[i];
            ptr = ptr.next;
         }
      }
   }
}
const linkedList = new LinkedList();
linkedList.push(0);
linkedList.push(1);
linkedList.push(0);
linkedList.push(2);
linkedList.push(1);
linkedList.push(1);
linkedList.push(2);
linkedList.push(1);
linkedList.push(2);
console.log("Before sorting:");
linkedList.printList();
linkedList.sortList();
console.log("After sorting:");
linkedList.printList();

Fazit

Insgesamt zeigt das obige Javascript-Programm eine effiziente Möglichkeit, eine verknüpfte Liste, die nur 0, 1 und 2 enthält, mithilfe von Zähltechniken zu sortieren. Der Algorithmus hat eine Zeitkomplexität von O(n) und eine räumliche Komplexität von O(1), was ihn zur optimalen Lösung für dieses spezielle Sortierproblem macht.

Das obige ist der detaillierte Inhalt vonJavaScript-Programm zum Sortieren einer verknüpften Liste mit 0, 1 und 2. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!