Reversing a Doubly Linked List

Written by: Anagha Bharadwaj (3rd Sem CSE)

A double linked list is a type of linked list in which each node apart from storing its data has two links. The first link points to the previous node in the list and the second link points to the next node in the list. The first node of the list has its previous link pointing to NULL and is nicknamed as ‘HEAD’ similarly the last node of the list has its next node pointing to NULL and is nicknamed as ‘TAIL’.

The students of 3rd semester Computer Science Engineering under the guidance of our teacher, Mr. Srinidhi Kulkarni, illustrated the action of reversing a double linked list. In the picture below the action of reversing is explained by Arul Joshua. There are three nodes represented (Node A, B&C).

Node A consists of: –

Giridhar – data value of 10

Deepanshu – address of previous node (In this case Null)

Devika – address of the next node (2000)

Node B:

Krishna Koustab – data value of 20

Ananya D – address of the previous node (1000)

Pooja – address of the next node (3000)

Node C:

Gayathri – data value of 30

Ajay – address of the next node (In this case Null)

Manish – address of the previous node (2000)

The linked list before reversing has its head at the first node (10) and tail at (20). The role of ‘Head’ is played by Bhoomika and ‘Tail’ is played by Ananya B.

So in the picture above we have a head node(10) pointing to the next node (20) and then also has a previous pointer but there’s nothing there that’s why it’s NULL. If we go to the node (20), you can see it’s pointing to the next node (30) as well as it’s pointing to the previous node (20). Similarly, we have the tail node (30) pointing to the previous node (20) and the next node pointing to NULL as there’s no node next.

The main aim of the activity was to reverse the head to the tail position and tail to the head position. In order to do so, we begin by swapping the addresses of 2000(Devika) and NULL (Deepanshu). Then we swap 1000 (Ananya D) and 3000 (Pooja). Lastly, we swap 2000 (Manish) and NULL (Ajay). For the reverse to be complete, we lastly interchange the location of head (Bhoomika) and tail (Ananya B).

The picture above shows the end of the illustration. Reversal of the double linked list is complete with the positions of the head and tail interchanged. We also observe the addresses in the next and previous positions of the nodes have changed thus reversing the linkage.

The activity which was conducted by my fellow students under the guidance of our teacher, Mr. Srinidhi Kulkarni, was a fun learning exercise for all. The activity truly gave us a realistic idea on how the reversal of the linked list works thus enhancing our knowledge in this particular topic of data structures. I can positively conclude that the activity was a huge success in achieving its main objective for the class. The class really appreciates the opportunity as it helped us to introduce personal talents, master and help others master the subject.