JavaScript-Programm zum Schreiben einer Funktion zum Abrufen des N-ten Knotens in einer verknüpften Liste

Eine verknüpfte Liste ist eine lineare Datenstruktur, in der alle Knoten miteinander verbunden sind, indem die Adresse des nächsten Knotens gespeichert wird. Das Finden des n-ten Knotens in einer verknüpften Liste bedeutet, den Wert des n-ten Knotens in einer bestimmten verknüpften Liste abzurufen, was sowohl durch iterative als auch durch rekursive Methoden erfolgen kann.

Beispiel

Given linked list: 
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
Node to find: 3

Ausgabe

3

Erklärung: Der Wert des dritten Knotens ist 3.

Iterative Methode

Bei dieser Methode durchlaufen wir die verknüpfte Liste direkt mithilfe einer While-Schleife, bis wir den letzten Knoten oder den gewünschten Knoten erreichen.

Beispiel

// class to create the structure of the nodes 
class Node{
   constructor(data){
      this.value = data;
      this.next = null;
   }
}

// function to print the linked list
function print(head){
   var temp = head;
   var ans = ""
   while(temp.next != null){
      ans += temp.value;
      ans += " -> "
      temp = temp.next
   }
   ans += temp.value
   ans += " -> null"
   console.log(ans)
}

// function to add data in linked list 
function add(data, head, tail){
   return tail.next = new Node(data);
}

// function to find the nth node 
function findNode(head, node){
   var temp = head;
   while(node > 1 && temp != null){
      node--;
      temp = temp.next;
   }
   return temp;
}

// defining linked list
var head  = new Node(1)
var tail  = head
tail = add(2,head, tail)
tail = add(3,head, tail)
tail = add(4,head, tail)
tail = add(5,head, tail)
tail = add(6,head, tail)
tail = add(7,head, tail)
tail = add(8,head, tail)

// printing linked list 
console.log("The given linked list is: ")
print(head)

// defining node to get 
var node = 5;

// calling function to get the nth node; 
var nth_node = findNode(head,node)
if(nth_node == null){
   console.log("The given linked list does not have the Nth Node");
}
else{
   console.log("The value present at the nth node is: " + nth_node.value);
}

Ausgabe

The given linked list is: 
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> null
The value present at the nth node is: 5

Zeitliche und räumliche Komplexität

Die zeitliche Komplexität des obigen Codes beträgt O(N), wobei N die Größe der angegebenen verknüpften Liste ist. Die hier angegebene Zahl ist möglicherweise kleiner als die Größe der angegebenen verknüpften Liste, aber im schlimmsten Fall durchlaufen wir nur die Länge der verknüpften Liste.

Hier verwenden wir keinen zusätzlichen Platz, was bedeutet, dass die zeitliche Komplexität des obigen Codes O(1) ist.

Rekursive Methode

In dieser Methode verwenden wir rekursive Aufrufe anstelle von While-Schleifen, um die verknüpfte Liste zu durchlaufen und die vorherige Logik zu implementieren.

Beispiel

// class to create the structure of the nodes 
class Node{
   constructor(data){
      this.value = data;
      this.next = null;
   }
}

// function to print the linked list
function print(head){
   var temp = head;
   var ans = ""
   while(temp.next != null){
      ans += temp.value;
      ans += " -> "
      temp = temp.next
   }
   ans += temp.value
   ans += " -> null"
   console.log(ans)
}

// function to add data in linked list 
function add(data, head, tail){
   return tail.next = new Node(data);    
}

// function to find the nth node 
function findNode(head, node){
   if(node == 1){
      return head;
   }
   else if(head == null){
      return null;
   }
   else{
      return findNode(head.next, node-1);
   }
}

// defining linked list
var head  = new Node(1)
var tail  = head
tail = add(2,head, tail)
tail = add(3,head, tail)
tail = add(4,head, tail)
tail = add(5,head, tail)
tail = add(6,head, tail)
tail = add(7,head, tail)
tail = add(8,head, tail)

// printing linked list 
console.log("The given linked list is: ")
print(head)

// defining node to get 
var node = 9;

// calling function to get the nth node; 
var nth_node = findNode(head,node)
if(nth_node == null){
   console.log("The given linked list does not have the " + node + " number of nodes");
}
else{
   console.log("The value present at the nth node is: " + nth_node.value);
}

Ausgabe

The given linked list is: 
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> null
The given linked list does not have the 9 number of nodes

Zeitliche und räumliche Komplexität

Die zeitliche und räumliche Komplexität des obigen Codes ist gleich, beide sind O(N), wobei N die Anzahl der Knoten in der angegebenen verknüpften Liste ist. Der Platz hier ist auf rekursive Aufrufe zurückzuführen.

Fazit

In diesem Tutorial haben wir ein JavaScript-Programm implementiert, um den n-ten Knoten in einer bestimmten verknüpften Liste zu finden. Wenn der n-te Knoten nicht existiert, geben wir aus, dass er nicht existiert, andernfalls geben wir den Wert aus, der an diesem Knoten existiert. Wir haben zwei Methoden implementiert: eine iterative Methode mit While-Schleife und eine rekursive Methode. Die zeitliche Komplexität beider beträgt O(N), aber die Iteration ist besser, da sie keinen zusätzlichen Platz erfordert.

Das obige ist der detaillierte Inhalt vonJavaScript-Programm zum Schreiben einer Funktion zum Abrufen des N-ten Knotens in einer verknüpften Liste. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!