JavaScript program to swap nodes in a linked list without exchanging data

JavaScript programs that swap nodes in a linked list without exchanging data is a common problem in web development that involves rearranging the order of nodes in a linked list. A linked list is a data structure composed of nodes, each node containing a piece of data and a reference to the next node in the list.

In this article, we will learn a complete tutorial on exchanging nodes in a linked list without exchanging data using JavaScript. So let's first define the exchange node and then continue with the tutorial. So, keep learning!

Exchange Node

Exchanging nodes in the linked list means that we exchange the positions of two nodes. There are several ways to swap nodes in a linked list. One approach is to swap data across nodes, but this can be inefficient when dealing with large amounts of data. Another approach is to swap pointers to nodes. This is more efficient because we don't need to copy any data.

Let us understand the switching node through an example

Example

Suppose we have a linked list as shown below -

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

We want to swap the second and fourth nodes to get:

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

In order to accomplish this without exchanging data in the nodes, we need to modify the links between nodes. The resulting linked list should have the same data as the original linked list, but with the order of the nodes changed.

So, we first identify the two nodes to be swapped: node 2 and node 4. We also need to keep track of the nodes before and after these nodes in the list.

In this example, the nodes before and after node 2 are 1 and 3 respectively. The nodes before and after node 4 are 3 and 5 respectively.

Next, we need to update the links between nodes. We first set the next pointer of the node before node 2 to node 4. We then set the next pointer of node 2 to node 5 (since node 4 is now behind node 2). Finally, we set the next pointer of node 4 to node 3 (since node 2 is now behind node 4).

The generated link list is as follows -

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

Note - The data in each node does not change, just the order of the nodes.

Now let's look at the algorithm we will use to swap nodes in a linked list without exchanging data.

algorithm

STEP1: Identify the two nodes that need to be exchanged

The first step is to identify the two nodes that need to be exchanged. Suppose we want to swap node A and node B.

Step 2: Find the previous node of the two nodes to be swapped

We need to find the nodes before nodes A and B in the linked list. We call these nodes PrevA and PrevB respectively.

Step 3: Update the next pointer of the previous node to point to another node

Now, we need to update the next pointers of PrevA and PrevB to point to the correct nodes. This involves updating PrevA's next pointer to point to node B, and updating PrevB's next pointer to point to node A.

Step 4: Update the next pointer of the node to be swapped so that it points to the correct node

Next, we need to update the next pointers of nodes A and B to point to the correct nodes. This involves updating node A's next pointer to point to the node next to node B, and updating node B's next pointer to point to the node next to node A.

Step 5: Repeat the above steps for any other nodes that need to be swapped

If we need to swap more than two nodes, we can repeat the above steps for each pair of nodes that need to be swapped.

After completing these steps, the nodes in the linked list will be swapped, but their data will not be swapped. Let us now understand the above algorithm with an example of implementing it using Javascript.

Example

In this program, we first define a "Node" class to create the nodes of the linked list, and define a "LinkedList" class to create and operate the linked list. The "swapNodes" function in the "LinkedList" class implements the swap algorithm described previously.

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

in conclusion

In this tutorial, we show a JavaScript program that implements this algorithm, which successfully swaps nodes in a linked list without exchanging their data. Hope this helps our readers. happy learning!

The above is the detailed content of JavaScript program to swap nodes in a linked list without exchanging data. For more information, please follow other related articles on the PHP Chinese website!