Swapping Elements in a Linked List

Learn how to swap two nodes in a singly linked list in JavaScript.

Since singly linked lists only have pointers from each node to its next node, swapping two nodes in the list isn’t as easy as doing so in an array (where you have access to the indices). You not only have to find the elements, but also reset the pointers around them to maintain the integrity of the list. This means keeping track of the two nodes to be swapped as well as the nodes preceding them.

Given an input of a linked list, data1, and data2, the general steps for doing so is as follows:

  1. Iterate through the list looking for the node that matches data1 to be swapped (node1), keeping track of the node’s previous node as you iterate (node1Prev)
  2. Repeat step 1 looking for the node that matches data2 (giving you node2 and node2Prev)
  3. If node1Prev is null, node1 was the head of the list, so set the list’s head to node2
  4. Otherwise, set node1Prev‘s next node to node2
  5. If node2Prev is null, set the list’s head to node1
  6. Otherwise, set node2Prev‘s next node to node1
  7. Set node1‘s next node to node2‘s next node
  8. Set node2‘s next node to node1‘s next node

Finding the Matching and Preceding Nodes

Let’s look at what implementing steps 1 and 2 looks like. In order to swap the two nodes, we must first find them. We also need to keep track of the nodes that precede them so that we can properly reset their pointers. (We will use the Node classes .getNextNode() method in order to access the next node.)

We will start by setting node1 equal to the head of the list, and then creating a while loop that runs while node1 isn’t null. Inside the loop, we will check if node1‘s data matches data1. If so, we break out of the loop as we have found the correct node. If there is no match, we update node1Prev to be node1 and move node1 to its next node:

function swapNodes(list, data1, data2) { let node1 = list.head; let node2 = list.head; let node1Prev = null; let node2Prev = null; while (node1 !== null) { if (node1.data === data1) { break; } node1Prev = node1; node1 = node1.getNextNode(); } }

At the end of this, we have found our matching node, and also saved its previous node, which we will use in the next step.