Programme JavaScript pour échanger des nœuds dans une liste chaînée sans échanger de données

Le programme JavaScript permettant d'échanger des nœuds dans une liste chaînée sans échanger de données est un problème courant dans le développement Web qui implique de réorganiser l'ordre des nœuds dans une liste chaînée. Une liste chaînée est une structure de données composée de nœuds, chaque nœud contenant une donnée et une référence au nœud suivant dans la liste.

Dans cet article, nous apprendrons un tutoriel complet sur l'échange de nœuds dans une liste chaînée sans échanger de données à l'aide de JavaScript. Définissons donc d’abord le nœud d’échange, puis poursuivons le didacticiel. Alors continuez à apprendre !

Nœud d'échange

Échanger des nœuds dans une liste chaînée signifie que nous échangeons les positions de deux nœuds. Il existe de nombreuses façons d'échanger des nœuds dans une liste chaînée. Une approche consiste à échanger des données entre les nœuds, mais cela peut s'avérer inefficace lorsqu'il s'agit de grandes quantités de données. Une autre approche consiste à échanger des pointeurs vers des nœuds. C'est plus efficace car nous n'avons pas besoin de copier de données.

Comprenons le nœud d'échange à travers un exemple

Exemple

Supposons que nous ayons une liste chaînée comme ci-dessous -

1 -> 2 -> 3 -> 4 -> 5

Nous voulons échanger les deuxième et quatrième nœuds pour obtenir :

1 -> 4 -> 3 -> 2 -> 5

Pour y parvenir sans échanger de données dans les nœuds, nous devons modifier les liens entre les nœuds. La liste chaînée résultante doit contenir les mêmes données que la liste chaînée d'origine, mais l'ordre des nœuds a changé.

Donc, nous identifions d'abord les deux nœuds à échanger : le nœud 2 et le nœud 4. Nous devons également garder une trace des nœuds avant et après ces nœuds dans la liste.

Dans cet exemple, les nœuds avant et après le nœud 2 sont respectivement 1 et 3. Les nœuds avant et après le nœud 4 sont respectivement 3 et 5.

Ensuite, nous devons mettre à jour les liens entre les nœuds. Nous définissons d’abord le pointeur suivant du nœud avant le nœud 2 sur le nœud 4. Nous plaçons ensuite le pointeur suivant du nœud 2 sur le nœud 5 (puisque le nœud 4 est maintenant derrière le nœud 2). Enfin, nous plaçons le pointeur suivant du nœud 4 sur le nœud 3 (puisque le nœud 2 est maintenant derrière le nœud 4).

La liste de liens générée ressemble à ceci -

1 -> 4 -> 3 -> 2 -> 5

Remarque - Les données de chaque nœud ne changent pas, juste l'ordre des nœuds.

Regardons maintenant l'algorithme que nous utiliserons pour échanger des nœuds dans une liste chaînée sans échanger de données.

Algorithme

ÉTAPE 1 : Identifiez les deux nœuds qui doivent être échangés

La première étape consiste à identifier les deux nœuds qui doivent être échangés. Supposons que nous voulions échanger le nœud A et le nœud B.

Étape 2 : Trouvez le nœud précédent des deux nœuds à échanger

Nous devons trouver les nœuds avant les nœuds A et B dans la liste chaînée. Nous appelons respectivement ces nœuds PrevA et PrevB.

Étape 3 : Mettez à jour le pointeur suivant du nœud précédent pour pointer vers un autre nœud

Maintenant, nous devons mettre à jour les prochains pointeurs de PrevA et PrevB pour pointer vers les bons nœuds. Cela implique de mettre à jour le pointeur suivant de PrevA pour pointer vers le nœud B et de mettre à jour le pointeur suivant de PrevB pour pointer vers le nœud A.

Étape 4 : Mettez à jour le pointeur suivant du nœud à échanger afin qu'il pointe vers le bon nœud

Ensuite, nous devons mettre à jour les prochains pointeurs des nœuds A et B pour pointer vers les nœuds corrects. Cela implique de mettre à jour le pointeur suivant du nœud A pour pointer vers le nœud situé à côté du nœud B, et de mettre à jour le pointeur suivant du nœud B pour pointer vers le nœud situé à côté du nœud A.

Étape 5 : Répétez les étapes ci-dessus pour tous les autres nœuds qui doivent être échangés

Si nous devons échanger plus de deux nœuds, nous pouvons répéter les étapes ci-dessus pour chaque paire de nœuds qui doivent être échangés.

Après avoir terminé ces étapes, les nœuds de la liste chaînée seront échangés, mais pas leurs données. Comprenons maintenant l'algorithme ci-dessus avec un exemple de son implémentation en utilisant Javascript.

Exemple

Dans ce programme, nous définissons d'abord une classe "Node" pour créer les nœuds de la liste chaînée, et définissons une classe "LinkedList" pour créer et exploiter la liste chaînée. La fonction "swapNodes" de la classe "LinkedList" implémente l'algorithme de swap décrit précédemment.

// Define a Node class to create nodes of linked list
class Node {
   constructor(data) {
      this.data = data;
      this.next = null;
   }
}
// Define a LinkedList class to create and manipulate the linked list
class LinkedList {
   constructor() {
      this.head = null;
   }
   // Function to swap two nodes in the linked list
   swapNodes(node1, node2) {
      // If both nodes are the same, no need to swap
      if (node1 === node2) {
         return;
      }
      // Find the previous nodes of both nodes to be swapped
      let prevNode1 = null;
      let currentNode1 = this.head;
      while (currentNode1 && currentNode1 !== node1) {
         prevNode1 = currentNode1;
         currentNode1 = currentNode1.next;
      }
      let prevNode2 = null;
      let currentNode2 = this.head;
      while (currentNode2 && currentNode2 !== node2) {
         prevNode2 = currentNode2;
         currentNode2 = currentNode2.next;
      }
      // If either node1 or node2 is not found, return
      if (!currentNode1 || !currentNode2) {
         return;
      }
      // Update the next pointers of the previous nodes to point to the other node
      if (prevNode1) {
         prevNode1.next = currentNode2;
      } else {
         this.head = currentNode2;
      }
      if (prevNode2) {
         prevNode2.next = currentNode1;
      } else {
         this.head = currentNode1;
      }
      // Swap the next pointers of the nodes to be swapped to point to the correct nodes
      let temp = currentNode1.next;
      currentNode1.next = currentNode2.next;
      currentNode2.next = temp;
      // Print the swapped linked list
      console.log("Swapped linked list:");
      let current = this.head;
      while (current) {
         process.stdout.write(current.data + " -> ");
         current = current.next;
      }
      console.log("null");
   }
   // Function to add a Node at the end of the linked list
   addNode(data) {
      let node = new Node(data);
      if (!this.head) {
         this.head = node;
      } else {
         let current = this.head;
         while (current.next) {
            current = current.next;
         }
         current.next = node;
      }
   }
}
// Create a linked list
let linkedList = new LinkedList();
linkedList.addNode(1);
linkedList.addNode(2);
linkedList.addNode(3);
linkedList.addNode(4);
// Print the original linked list
console.log("Original linked list:");
let current = linkedList.head;
while (current) {
   process.stdout.write(current.data + " -> ");
   current = current.next;
}
console.log("null");
// Swap node 2 and node 4
let node2 = linkedList.head.next;
let node4 = linkedList.head.next.next.next;
linkedList.swapNodes(node2, node4);

Conclusion

Dans ce tutoriel, nous montrons un programme JavaScript qui implémente cet algorithme, qui échange avec succès les nœuds d'une liste chaînée sans échanger leurs données. J'espère que cela aidera nos lecteurs. Bon apprentissage !

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!