Doubly Linked List with Python Examples
This is the third article in the series of articles on implementing linked list with Python. In Part 1 and Part 2 of the series we studied single linked list in detail. In this article, we will start our discussion about doubly linked list, which is actually an extension of single linked list.
In single linked list each node of the list has two components, the actual value of the node and the reference to the next node in the linked list. In the doubly linked list, each node has three components: the value of the node, the reference to the previous node, and the reference to the next node. For the start node of the doubly linked list, the reference to the previous node is null. Similarly, for the last node in the doubly linked list, the reference to next node is null.
Pros and Cons of a Doubly Linked List
Following are some of the pros and cons of a doubly linked list:
Pros
- Unlike a single linked list, the doubly linked list can be traversed and searched in both directions. The reference to the next node helps in traversing the