Some time ago, I worked on a small project where I implemented a doubly linked list. I thought it was a great way for me to really understand this data structure and its many applications in programming. For example, Linked lists are most commonly used to implement stacks, queues, and other abstract data types.

However, many challenges arise in the use of Linked lists, one of the most contrived problems is being able to reverse the list. And so, this is what I will be discussing in this post. To begin, let us redefine what a linked list is to refresh our memory.

Linked List: A linked list consists of nodes where each node contains a data field and a reference(link) to the next node in the list.

In a singly linked list each node holds a value and a link to the next node. In a doubly linked list each node also holds a link to the previous node. Reversing a linked list is no simple task as it requires lots of pointer tracking but this is precisely the reason why learning this is so important, it really enforces the practice of variable/pointer manipulation. Data manipulation is an essential skill to have as a programmer and being able to manipulate many variables at the same time is crucial to solving complex problems.

Let us now take a look at how to solve this problem and reverse a singly linked list. The most common approach is to change the head node such that the tail becomes the head. Now that we are starting from the end, we can traverse the list and change each nodes next value so that it points to its preceeding node prev, reversing the order. Here is some pseudocode to show us how it is done.

function reverseSingly(head)
  prev ← null
  while head.next is not null
    head.next ← prev
    prev ← head
    head ← old value of head.next
  head.next ← prev
  return head

By doing this, we are essentially enabling the last node to become the head and all nodes point to its preceeding node until we reach the tail, which is the first node. Such is seen in the following image of a given singly linked list:

Next lets discuss how we can reverse a doubly linked list. This problem is slightly simpler than the singly list because we already have pointers that handle both the next and previous node. To reverse a doubly list we can loop through the list and just swap each nodes prev and next values. Here is some pseudocode displaying this method.

function reverseDoubly (head)
  loop {
    swap head.next and head.prev values
    if head.prev is null
      return head
    head ← head.prev
  }

Following this method will yield the results shown in this drawing of a given doubly linked list. As you can see, reversing the doubly linked list was much easier as all the pointer tracking is already handled for us, we just needed to perform a simple swap of values.

Overall, Linked List problems are very common interview questions and seem pretty simple at first. However, it is very easy to get lost in all the pointers we are dealing with. I hope this article helps enhance your understanding of the Linked list data structure and how to reverse one.