Doubly linked lists

We have discussed the singly linked list and the important operation that can be performed on it. Now, we will be focusing on the topic of a doubly linked list in this section. 

A doubly linked list is quite similar to the singly linked list in the sense that we use the same fundamental concept of string nodes together, as we did in a singly linked list. The only difference between a singly linked list and a doubly linked list is that in a singly linked list, there is only one link between each successive node, whereas, in a doubly linked list, we have two pointers—a pointer to the next node and a pointer to the previous node. See the following diagram of a node; there is a pointer to the next node and the previous node, which are set to None as there is no node attached to this node. Consider the following diagram:

A node in a singly linked list can only determine the next node associated with it. However, there is no way or link to go back from this referenced node. The direction of flow is only one way.

In a doubly linked list, we solve this issue and include the ability not only to reference the next node but also to reference the previous node. Consider the following example diagram to understand the nature of the linkages between two successive nodes. Here, node A is referencing node B; in addition, there is also a link back to node A:

With the existence of two pointers that point to the next and previous nodes, doubly linked lists become equipped with certain capabilities.

Doubly linked lists can be traversed in any direction. A node in a doubly linked list can be easily referred to its previous node whenever required without having a variable to keep track of that node. However, in a singly linked list, it may be difficult to move back to the start or beginning of the list in order to make some changes at the start of the list, which is very easy now in the case of a doubly linked list.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset