A Doubly Linked List is an advanced version of Singly Linked List which has an additional pointer
prev to store the location of the previous node.
We suggest you to go over the implementation of Singly Linked List before starting with Doubly Linked List. It will become easier for you to understand Doubly Linked List if you already know how a Singly Linked list works.
A Doubly Linked list is also made up of nodes, but as compared to the node used in the Singly linked list, node in case of the doubly linked list has 3 parts:
Data Part: Holds the data
Prev Address Part: Holds the address of the previous node.
Next Address Part: Holds the address of the next node.
Below we have a simple pictorial representation of Nodes connected to form a Doubly Linked List.
As you can see, every node has some data stored in it, and it also stores the location of the next node and the previous node. It is not necessary that all the nodes get saved in contiguous memory locations. Also, the first node's
prev pointer and the last node's
next pointer points to
NULL because there is no node before the first node and after the last node.
Head is a pointer that always points to the first node of the list if Head points to nothing, it means the linked list is empty.
Before we move on with the implementation let's understand the advantages of a Doubly Linked List over a Singly Linked List.
We can traverse a Doubly Linked List in both forward and backward directions.
Also, when we have to delete any node in a Singly Linked List, we have to declare an additional pointer to keep track of the previous node, which is not required in the case of Doubly Linked List.
The major disadvantage is maintaining an extra
prev pointer, which not only demands extra memory space but also adds extra steps to carry out basic operations on the Doubly Linked list as we have to update two pointers every time we insert a new node or delete a node.
To implement a Doubly Linked List, we will first define a class for
Node which will have three attributes, namely
next is the pointer to store the location of the next node and
prev is the pointer to store the location of the previous node.
Then we will have the class
DoublyLinkedList, which will have the head pointer, initialized to
None. We can also have another attribute
size to store the size of the doubly linked list.