JS - Swapping Element in Singly Linked List

Conceptually

  1. Iterate through the list to find the 2 element to swap
  2. Keep track of the nodes preceding the 2 elements
  3. Update preceding nodes'pointers
  4. Updating the nodes' next pointers
Swapping Nodes
function swapNodes(list, data1, data2) {
  console.log(`Swapping ${data1} and ${data2}:`);
 
  let node1Prev = null;
  let node2Prev = null;
  let node1 = list.head;
  let node2 = list.head;
 
  if (data1 === data2) {
    console.log('Elements are the same - no swap to be made');
    return;
  }
 
  while (node1 !== null) {
    if (node1.data === data1) {
      break;
    }
    node1Prev = node1;
    node1 = node1.getNextNode();
  }
 
  while (node2 !== null) {
    if (node2.data === data2) {
      break;
    }
    node2Prev = node2;
    node2 = node2.getNextNode();
  }
 
  if (node1 === null || node2 === null) {
    console.log('Swap not possible - one or more element is not in the list');
    return;
  }
 
  if (node1Prev === null) {
    list.head = node2;
  } else {
    node1Prev.setNextNode(node2);
  }
 
  if (node2Prev === null) {
    list.head = node1;
  } else {
    node2Prev.setNextNode(node1);
  }
 
  let temp = node1.getNextNode();
  node1.setNextNode(node2.getNextNode());
  node2.setNextNode(temp);
}

Time and Space Complexity

  • The worst case for time complexity in swapNodes() is if both while loops must iterate all the way.
  • Either if there are no matching nodes, or if the matching node is the tail.
  • This means that it has a linear big O runtime of O(n),
  • since each while loop has a O(n) runtime, and constants are dropped.
  • There are four new variables created in the function regardless of the input.
  • It has a constant space complexity of O(1),