Programme JavaScript pour insérer des nœuds dans une liste chaînée

Une liste chaînée est une structure de données de différentes longueurs, n'importe quel nœud peut être supprimé ou ajouté à la liste chaînée. Dans ce tutoriel, nous allons implémenter un programme complet pour insérer des nœuds dans une liste chaînée avec une complexité spatiale et temporelle. Comprenons d’abord l’énoncé du problème.

Introduction au problème

Dans la question donnée, on nous donne une liste chaînée et comme nous pouvons modifier la taille de la liste chaînée en ajoutant ou en supprimant des nœuds dans la liste chaînée, nous ajouterons ou insérerons des nœuds dans la liste chaînée.

Dans une liste chaînée, nous pouvons ajouter de nouveaux nœuds à trois emplacements différents : au début, après le dernier nœud et au milieu de la liste. Par exemple, la liste chaînée donnée est -

1 -> 2 -> 3 -> 4 -> 5 -> null, nous devons ajouter un nœud aléatoire de valeur 9. Par conséquent, il existe de nombreux cas où des nœuds doivent être ajoutés, tels que -

• Ajouter un nœud au début - 7 -> 1 -> 2 -> 3 -> 4 -> 5 -> null

• Ajouter un nœud au milieu - 1 -> 2 -> 3 -> 7 -> 4 -> 5 -> null

• Ajouter un nœud à la fin - 1 -> 2 -> 3 -> 4 -> 5 -> 7 -> null

Regardons les moyens d'accomplir les tâches suivantes -

Ajouter un nœud au début de la liste chaînée

Exemple

Pour ajouter un nœud au début de la liste chaînée, nous devons créer un nouveau nœud et passer la tête de la liste chaînée au nouveau nœud comme nœud suivant, puis déplacer la tête vers le nouveau nœud et ajouter le nouveau nœud nœud au début de la liste chaîné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 add(data) {
   var new_node = new Node(data);
   new_node.next = head;
   return new_node;
}

var head = new Node(1);
var tail = head;
tail = push(tail, 2)
tail = push(tail, 3)
tail = push(tail, 4)
tail = push(tail, 5)

head = add(7);
var data = 0;
while(head != null) {
   data = data + head.value + " -> ";
   head = head.next;
}
console.log("Linked List after adding a node at starting: ")
console.log(data + "null")

La complexité temporelle du code ci-dessus est O(1), car il suffit de déplacer un pointeur et aucun espace supplémentaire n'est utilisé, ce qui rend la complexité spatiale O(1).

Ajouter un nœud au milieu de la liste chaînée

Exemple

Pour ajouter un nœud au milieu d'une liste chaînée, nous devons créer un nouveau nœud et transmettre ce nœud avant de pouvoir ajouter le nouveau nœud de la liste chaînée comme nœud suivant du nouveau nœud, cela ajoutera le nouveau nœud nœud à la liste chaînée au milieu.

// 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 add(data,head) {
   var new_node = new Node(data);
   var temp = head;
   while(temp.value != 3) {
      temp  = temp.next;
   }
   new_node.next = temp.next;
   temp.next = new_node;
   return head;
}
var head = new Node(1);
var tail = head;
tail = push(tail, 2)
tail = push(tail, 3)
tail = push(tail, 4)
tail = push(tail, 5)
head = add(7,head);
var data = 0;
while(head != null) {
   data = data + head.value + " -> ";
   head = head.next;
}
console.log("Linked List after adding node in middle:")
console.log(data + "null")

La complexité temporelle du code ci-dessus est O(N) car nous devons nous déplacer vers le nœud où un nouveau nœud doit être ajouté. La complexité spatiale du processus ci-dessus est O(1) puisque nous n'utilisons aucun espace supplémentaire.

Ajouter un nœud à la fin de la liste chaînée

Exemple

Pour ajouter un nœud à la fin de la liste chaînée, nous devons créer un nouveau nœud et ajouter ce nœud après le nœud de queue et déplacer le nœud de queue vers le nœud suivant.

// 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 add(data) {
   var new_node = new Node(data);
   tail.next = new_node;
   tail = tail.next
   return tail;
}
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 = add(7);
var data = 0;
while(head != null){
   data = data + head.value + " -> ";
   head = head.next;
}
console.log("Linked List after adding a node at the end: ")
console.log(data + "null")

La complexité temporelle du code ci-dessus est O(1), car il suffit de déplacer un pointeur et aucun espace supplémentaire n'est utilisé, ce qui rend la complexité spatiale O(1).

Conclusion

Dans le didacticiel ci-dessus, nous avons appris comment ajouter un nouveau nœud dans une liste chaînée existante de trois manières possibles. Nous avons vu du code correct avec des explications et des complexités temporelles et spatiales. L'ajout d'un nœud au milieu de la liste chaînée prend un temps O(N), tandis que pour les deux autres cas, sa complexité temporelle est O(1), et pour les trois possibilités, la complexité spatiale est O(1).

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!