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.
Advantages over Singly Linked List
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.
Disadvantages over Singly 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.
Implementing Doubly Linked List
To implement a Doubly Linked List, we will first define a class for Node which will have three attributes, namely data, prev and next, where 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.
Inserting Nodes
You may also like:
