Swapping Elements

Swapping An Adjacent Element (Single Link)

Given the parameter “target”, in order to swap a node with it’s adjacent sibling (target + 1):

int i = 0;
node* prev = NULL;
node* walk = head;

if ( target == 0)
  return // We'll explain this later

while ( i < target ) {
  if walk != NULL {
    prev = walk;
    walk = walk->next;
    i++;
  }
  else
    return;

prev->next = walk->next;
walk->next = walk->next->next
prev->next->next = walk;

let target = 1

walk represents our target node, and prev refers to the last target node assigned at each iteration of our while loop.

As our counter iterates, we “walk” our list forward, keeping track of the last node passed on the way until we’ve reached our target index.

Here is where we swap:

Have our previous element “skip over” the target element

prev->next = walk->next;

Have our target element “skip over” the adjacent element

walk->next = walk->next->next;

Finally, point our adjacent element at the target element

prev->next->next = walk;

Swapping Adjacent Elements (Double Link)

Try to ignore the prev references, and you’ll see the swap operation was successful, yet leaves those prev references intact.

Now if focus is placed on the prev references…

It is now trivial to finish the swap operation

prev->next->prev = prev;

walk->next->prev = walk;

walk->prev = prev->next;