Programme JavaScript pour trouver la longueur d'une liste chaînée

La liste chaînée est une structure de données linéaire dont la longueur peut être variable. La longueur de la liste chaînée peut être modifiée. C'est le problème que la longueur du tableau dans le tableau ne peut pas être modifiée. Dans cet article, nous trouverons la longueur d'une liste chaînée donnée en implémentant le code et en vérifiant les cas limites. Nous utiliserons le concept de boucle while et de classe dans cet article.

Introduction au problème

Dans le problème donné, on nous donne une liste chaînée, nous devons d'abord créer la liste chaînée à l'aide d'une classe, puis nous devons trouver la longueur de la liste chaînée donnée. Étant donné que la longueur de la liste chaînée peut changer, nous trouverons la longueur de la liste chaînée à un point de code spécifique.

Nous utiliserons deux méthodes, la première est la méthode itérative directe utilisant la boucle while et l'autre est la méthode récursive pour trouver la longueur de la liste chaînée donnée.

Méthode itérative

Dans cette méthode, nous allons d'abord créer une liste chaînée en utilisant une classe pour fournir une structure à la liste chaînée. Nous définirons certaines fonctions, comme la fonction push, pour ajouter des valeurs à la liste chaînée en passant simplement des en-têtes et des données.

Exemple

Dans ce processus, nous utiliserons une boucle while, le nœud de tête ou de départ de la liste chaînée, et une variable pour compter le nombre de nœuds dans la liste chaînée, c'est-à-dire la longueur de la liste chaînée donnée.

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

Dans la méthode donnée ci-dessus, nous n'utilisons aucun espace supplémentaire et ne parcourons la liste chaînée qu'une seule fois. Par conséquent, la complexité temporelle de la méthode ci-dessus est O(N), où N est la taille de la liste chaînée, et la complexité spatiale de la méthode ci-dessus est O(1).

Méthode récursive

Dans cette méthode, nous suivrons les mêmes étapes que dans la méthode ci-dessus pour créer la liste chaînée, pour la tâche principale, nous utiliserons la méthode récursive.

Exemple

Appeler la même fonction avec des paramètres et des conditions de base spécifiques différents de ceux de la fonction elle-même est appelé récursivité. Dans cette méthode, nous appellerons la fonction avec la tête de la liste chaînée, puis à partir de cette fonction, nous appellerons à nouveau la fonction mais avec l'argument le nœud suivant du nœud actuel. Comme valeur de retour nous renverrons 1 + la valeur de retour de l'appel récursif et le résultat sera donné au premier appel. Regardons le code -

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

Complexité temporelle et spatiale

La complexité temporelle de la méthode récursive est O(N), où N est le nombre de nœuds présents dans la liste chaînée donnée. La complexité spatiale du code ci-dessus est O(N) car il y a N appels au total et pour chaque appel, nous devons maintenir la pile de nœuds actuelle.

Conclusion

Dans ce tutoriel, nous avons appris comment trouver la longueur d'une liste chaînée donnée en implémentant le code et en étudiant les cas extrêmes. Nous avons utilisé la boucle while et le concept de classe de cet article dans la première méthode et la méthode récursive pour trouver la longueur dans la deuxième méthode. La complexité temporelle des deux méthodes est O(N), où N est la longueur de la liste chaînée, tandis que la complexité spatiale de la méthode récursive est O(N) en raison de la taille de la pile.

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!