Reverse Double Linked List in C#

This is a question that often comes up in an interview.

The solution is simple, but under pressure it’s easy to get confused.

To begin with, initialise three node references:

  • current points to the head node
  • previous points to null
  • next points to null

Remember to point the tail to the head before we begin:

  • tail = head;

Now, iterate over the nodes using current, until there are no more:

  • while (current is not null)

Within the loop, first initialise next to look ahead:

  • next = current.next;

Now set current.next to previous:

  • current.next = previous;

Set current.previous to next:

  • current.previous = next;

Advance previous to current:

  • previous = current;

Lastly, advance current to next:

  • current = next;

That’s the loop finished. Outside the loop remember to set the head:

  • head = previous;

Here is the code, starting with the main method:

This is the output:

Iterating list from head to tail (normal)
        [1, 2, 3, 4, 5]

Iterating list from tail to head (reverse)
        [5, 4, 3, 2, 1]

Reversing List

Iterating list from head to tail (normal)
        [5, 4, 3, 2, 1]

Iterating list from tail to head (reverse)
        [1, 2, 3, 4, 5]

The very simple Node Class:

The rest of the code is in the LinkedList, beginning with initialisation:

Next, we have a method to add a node:

And then the method which reverses the list:

Lastly, the method to walk the list and print out the nodes:

And that’s it, in a nutshell.

Advertisement

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s