JavaScript-Programm zum Ermitteln der Länge einer verknüpften Liste

Die verknüpfte Liste ist eine lineare Datenstruktur, deren Länge variabel sein kann. Dies ist das Problem, dass die Länge des Arrays im Array nicht geändert werden kann. In diesem Artikel ermitteln wir die Länge einer bestimmten verknüpften Liste, indem wir den Code implementieren und Randfälle prüfen. In diesem Artikel werden wir die While-Schleife und das Klassenkonzept verwenden.

Einführung in das Problem

Bei dem gegebenen Problem erhalten wir eine verknüpfte Liste. Zuerst müssen wir die verknüpfte Liste mithilfe einer Klasse erstellen und dann müssen wir die Länge der angegebenen verknüpften Liste ermitteln. Da sich die Länge der verknüpften Liste ändern kann, ermitteln wir die Länge der verknüpften Liste an einem bestimmten Codepunkt.

Wir werden zwei Methoden verwenden: Die erste ist die direkte iterative Methode mit einer While-Schleife und die andere ist die rekursive Methode, um die Länge der angegebenen verknüpften Liste zu ermitteln.

Iterative Methode

Bei dieser Methode erstellen wir zunächst eine verknüpfte Liste mithilfe einer Klasse, um der verknüpften Liste eine Struktur bereitzustellen. Wir werden einige Funktionen definieren, wie zum Beispiel die Push-Funktion, um Werte zur verknüpften Liste hinzuzufügen, indem wir einfach Header und Daten übergeben.

Beispiel

In diesem Prozess verwenden wir eine While-Schleife, den Kopf oder Startknoten der verknüpften Liste, und eine Variable, um die Anzahl der Knoten in der verknüpften Liste zu zählen, d. h. die Länge der angegebenen verknüpften Liste.

// creating the linked list node
class Node{
   constructor(data)  {
      this.value = data;
      this.next = null;
   }
}
function push(tail, data){
   var new_node = new Node(data);
   tail.next = new_node;
   tail = tail.next;
   return tail
}
function length(head){
   temp = head;
   var count = 0
   while(temp != null) {
      count++;
      temp = temp.next;
   }
   return count;
}
var head = new Node(1);
var tail = head;
tail = push(tail, 2)
tail = push(tail, 3)
tail = push(tail, 4)
tail = push(tail, 5)
tail = push(tail, 6)
console.log("Length of the given linked list is: " + length(head))

Bei der oben angegebenen Methode verwenden wir keinen zusätzlichen Platz und durchlaufen die verknüpfte Liste nur einmal. Daher beträgt die zeitliche Komplexität der obigen Methode O(N), wobei N die Größe der verknüpften Liste ist und die räumliche Komplexität der obigen Methode O(1) ist.

Rekursive Methode

Bei dieser Methode befolgen wir die gleichen Schritte wie bei der obigen Methode, um die verknüpfte Liste zu erstellen. Für die Hauptaufgabe verwenden wir die rekursive Methode.

Beispiel

Das Aufrufen derselben Funktion mit anderen Parametern und spezifischen Grundbedingungen als die Funktion selbst wird als Rekursion bezeichnet. Bei dieser Methode rufen wir die Funktion mit dem Kopf der verknüpften Liste auf und rufen dann von dieser Funktion aus die Funktion erneut auf, jedoch mit dem Argument des nächsten Knotens vom aktuellen Knoten. Als Rückgabewert geben wir 1 + den Rückgabewert des rekursiven Aufrufs zurück und das Ergebnis wird beim ersten Aufruf ausgegeben. Schauen wir uns den Code an -

// creating the linked list node
class Node {
   constructor(data) {
      this.value = data;
      this.next = null;
   }
}
function push(tail, data) {
   var new_node = new Node(data);
   tail.next = new_node;
   tail = tail.next;
   return tail
}

function length(cur) {
   if(cur == null) return 0;
   return 1 + length(cur.next);
}
var head = new Node(1);
var tail = head;
tail = push(tail, 2)
tail = push(tail, 3)
tail = push(tail, 4)
tail = push(tail, 5)
tail = push(tail, 6)
console.log("Length of the given linked list is: " + length(head))

Zeitliche und räumliche Komplexität

Die zeitliche Komplexität der rekursiven Methode beträgt O(N), wobei N die Anzahl der in der angegebenen verknüpften Liste vorhandenen Knoten ist. Die Raumkomplexität des obigen Codes beträgt O(N), da es insgesamt N Aufrufe gibt und wir für jeden Aufruf den aktuellen Knotenstapel verwalten müssen.

Fazit

In diesem Tutorial haben wir gelernt, wie man die Länge einer bestimmten verknüpften Liste ermittelt, indem man den Code implementiert und Randfälle untersucht. Wir haben die while-Schleife und das Klassenkonzept aus diesem Artikel in der ersten Methode und die rekursive Methode verwendet, um die Länge in der zweiten Methode zu ermitteln. Die zeitliche Komplexität beider Methoden beträgt O(N), wobei N die Länge der verknüpften Liste ist, während die räumliche Komplexität der rekursiven Methode aufgrund der Stapelgröße O(N) beträgt.

Das obige ist der detaillierte Inhalt vonJavaScript-Programm zum Ermitteln der Länge einer verknüpften Liste. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!