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!
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
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.
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.
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 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!