The first node of the linked list is called the head, and the last node of the list is called the tail of the list. Each node contains two fields: data and pointer to the next field. The linked list is a linear data structure that can be described as the collection of nodes.

We can also have another attribute size to store the size of the doubly linked list.Doubly Linked List is a variation of the linked list.

Then we will have the class DoublyLinkedList, which will have the head pointer, initialized to None. 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. 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. We can traverse a Doubly Linked List in both forward and backward directions.Īlso, 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. Advantages over Singly Linked Listīefore we move on with the implementation let's understand the advantages of a Doubly Linked List over a Singly Linked List. 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. 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. It is not necessary that all the nodes get saved in contiguous memory locations. Next Address Part: Holds the address of the next node.īelow we have a simple pictorial representation of Nodes connected to form a Doubly Linked List.Īs 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. Prev Address Part: Holds the address of the previous node. It will become easier for you to understand Doubly Linked List if you already know how a Singly Linked list works.Ī 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: We suggest you to go over the implementation of Singly Linked List before starting with Doubly Linked List. 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.

Double pointer linked list