Programme JavaScript pour écrire une fonction pour obtenir le Nième nœud dans une liste chaînée

Une liste chaînée est une structure de données linéaire où tous les nœuds sont connectés les uns aux autres en stockant l'adresse du nœud suivant. Trouver le nième nœud dans une liste chaînée signifie obtenir la valeur du nième nœud dans une liste chaînée donnée, ce qui peut être effectué par des méthodes itératives et récursives.

Exemple

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

Sortie

3

Explication : La valeur du troisième nœud est 3.

Méthode itérative

Dans cette méthode, nous parcourrons directement la liste chaînée en utilisant la boucle while jusqu'à atteindre le dernier nœud ou le nœud souhaité.

Exemple

// 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);
}

Sortie

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

Complexité temporelle et spatiale

La complexité temporelle du code ci-dessus est O(N), où N est la taille de la liste chaînée donnée. Le nombre donné ici peut être inférieur à la taille de la liste chaînée donnée, mais dans le pire des cas, nous ne parcourrons que la longueur de la liste chaînée.

Ici, nous n'utilisons aucun espace supplémentaire, ce qui signifie que la complexité temporelle du code ci-dessus est O(1).

Méthode récursive

Dans cette méthode, nous utiliserons des appels récursifs au lieu de boucles while pour parcourir la liste chaînée et implémenter la logique précédente.

Exemple

// 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);
}

Sortie

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

Complexité temporelle et spatiale

La complexité temporelle et spatiale du code ci-dessus est la même, les deux sont O(N), où N est le nombre de nœuds dans la liste chaînée donnée. L'espace ici est dû aux appels récursifs.

Conclusion

Dans ce tutoriel, nous avons implémenté un programme JavaScript pour trouver le nième nœud dans une liste chaînée donnée. Si le nième nœud n'existe pas, alors nous imprimons qu'il n'existe pas, sinon nous imprimons la valeur qui existe à ce nœud. Nous avons implémenté deux méthodes, l’une itérative utilisant la boucle while et l’autre récursive. La complexité temporelle des deux est O(N), mais l'itération est meilleure car elle ne nécessite aucun espace supplémentaire.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!