The purpose of a doubly linked list is to enable both-way traversal while still allowing non-contiguous memory storage. Just like a singly linked list, we need to have a starting pointer pointing to the first node. The last node in the list points to NULL.<\/p>\n
Representation of Doubly Linked List<\/h3>\n
A doubly linked list is represented as follows:<\/p>\n
The above list is comprised of 4 nodes having four data points- A, B, C, D. Each node has two links one pointing forward and one pointing backwards.<\/p>\n Each node has the following structure:<\/p>\n <\/p>\n It comprises of two pointers and a data field.<\/p>\n a. Data<\/strong>: It constitutes the value of the data item inside the list.<\/p>\n b. Prev:<\/strong> It is a pointer pointing towards the previous node. For the first node, Prev points to NULL.<\/p>\n c. Next:<\/strong> It links the current node to the next node in the linked list. The \u2018Next\u2019 of the last node points towards NULL.<\/p>\n The basic set of operations that we can perform on a doubly linked list are:<\/p>\n 1. Traverse forward:<\/strong> It means visiting each node from the beginning till the end with the help of the \u2018Next\u2019 pointer.<\/p>\n 2. Traverse backwards:<\/strong> This operation is performed to visit each node but in the reverse direction. It will traverse the list from the end to the beginning.<\/p>\n 3. Insertion:<\/strong> This operation inserts an element at any given position in the list.<\/p>\n 4. Deletion<\/strong>: Deletion operation helps in deleting a node from the linked list.<\/p>\n 5. Display forward:<\/strong> This operation is used to print\/display all the data elements of the linked list from beginning till the end.<\/p>\n 6. Display backwards:<\/strong> it will display the elements from the end to the beginning.<\/p>\n 7. Search:<\/strong> Search operation helps in searching an element by traversing it.<\/p>\n 1. Each node in a doubly-linked list consists of 3 parts- two-pointers and a node.<\/p>\n 2. Due to two-pointers additional to data values, a doubly-linked list takes a lot of space as compared to other data structures.<\/p>\n 3. The following image shows the memory representation of a linked list.<\/p>\n 4. Here, -1 represents NULL.<\/p>\n 5. The Prev of the first node i.e. A and the Next of the last node i.e. D point towards NULL.<\/p>\n 6. This memory representation shows that the values need not be stored contiguously.<\/p>\n 7. The values 1000, 1056, 2004 and so on represent addresses in the memory.<\/p>\n 8. We traverse the list until we find -1 in the Next of a node.<\/p>\n Each node in a doubly linked list has data as well pointers. Therefore, we use a structure to create the node. Traversal refers to linearly visiting each node. In a doubly linked list, we can traverse in both forward and backward directions.<\/p>\n The function to perform the traversal is as follows:<\/p>\n The time complexity for the traversal operation is O(n).<\/p>\n There are various inbuilt methods defined inside the doubly-linked list class. A few of these methods are:<\/p>\n 1. add_front:<\/strong> This method adds a new node at the beginning of the doubly linked list.<\/p>\n 2. add_after:<\/strong> It adds a new node after a particular node.<\/p>\n 3. add_before:<\/strong> It is used to add a new node before a particular node in the list.<\/p>\n 4. add_end:<\/strong> This method will add a new node at the end of the doubly linked list.<\/p>\n 5. forward_traverse:<\/strong> It helps in traversing the list in the forward direction.<\/p>\n 6. backward_traverse:<\/strong> It helps in traversing the list in the backward direction.<\/p>\n 7. delete:<\/strong> This method deletes a node from the linked list.<\/p>\n Their implementation inside the class is shown below:<\/p>\n Insertion in a linked list occurs at three different positions:<\/p>\n 1. Insertion at the beginning of the list<\/p>\n 2. Insertion after a particular node.<\/p>\n 3. Insertion at the end of the list<\/p>\n We insert a node at the beginning such that the next pointer points to the node which was at first before. The previous pointer points to NULL.<\/p>\n Here, we have tried to insert M at the beginning.<\/p>\n The pseudo-code for this operation will be:<\/p>\n Here, we will make use of an extra pointer \u2018temp\u2019 to perform the insertion operation.<\/p>\n If the list is empty, we will insert a node right after the Head. If the list is not empty, we first need to traverse the whole list to insert a node at the end of the list.<\/p>\n In the above diagram, we are inserting M at the end.<\/p>\n The function for insertion at the end is:<\/p>\n Insertion after a particular node involves traversing all nodes before that node. We will make use of an extra pointer \u2018temp\u2019 for traversing the node up to a particular position.<\/p>\n For example, suppose we wish to insert a node having data value \u2018M\u2019 between node \u2018B\u2019 and node \u2018C\u2019, we will do it as follows:<\/p>\n The function will be:<\/p>\n![\"Doubly](\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/sites\/2\/2021\/06\/TechVidvan-Doubly-linked-list-normla-image.jpg\")
<\/a><\/p>\n<\/a><\/p>\nBasic Operations on Double Linked List<\/h3>\n
Memory Representation of Doubly Linked List<\/h3>\n
<\/a><\/p>\nCreating a Node in Doubly Linked List<\/h3>\n
\nThe structure template for the node looks as follows:<\/p>\nstruct Node\n{\n int data; \/\/The data point\n struct Node *Prev; \/\/Pointer to the previous node\n struct Node *Next; \/\/Pointer to the next node\n};\n<\/pre>\nTraversal in a Doubly Linked List<\/h3>\n
List_traversal(struct Node *Head)\n{\n Prev = (struct Node *)malloc(sizeof(struct Node));\n Next = (struct Node *)malloc(sizeof(struct Node));\n if(Head == NULL) \/\/If the list is empty\n return;\n while(Next->data != NULL)\n {\n Print(Next->data); \/\/The display operation\n Next = Next->data;\n }\n}\n<\/pre>\nDoubly Linked List Methods<\/h3>\n
class doubly_linked_list\n{\n node *First; \t\/\/ It points to the first node of the list\n node *Last; \t\/\/ It points to the last node of the list\n \n public:\n Doubly_Linked_List()\n {\n front = NULL;\n end = NULL;\n }\n void add_front(int ); \/\/Adds a new node at the beginning\n void add_after(node* , int ); \/\/Adds a new node after the given node\n void add_before(node* , int ); \/\/Adds a new node before a given node\n void add_end(int ); \/\/Adds a new node at the end of the list\n void delete_node(node*); \/\/Ddeletes a particular node\n void forward_traverse(); \/\/traverses the doubly-linked list in forward direction\n void backward_traverse(); \/\/traverses the doubly-linked list in backward direction\n};\n<\/pre>\nInsertion in a Linked List<\/h3>\n
Insertion at the beginning<\/h4>\n
<\/a><\/p>\nInsertion_at_beginning(struct Node *Head, int key)\n{\n Prev = (struct Node *)malloc(sizeof(struct Node));\n Next = (struct Node *)malloc(sizeof(struct Node));\n temp = (struct Node *)malloc(sizeof(struct Node));\n if(Head == NULL)\n return;\n while(Next->data != NULL)\n {\n temp->data = key;\n temp->Next = Head;\n Head->Prev = temp;\n Head = temp;\n temp->Prev = NULL;\n }\n}\n<\/pre>\nInsertion at the End<\/h4>\n
<\/a><\/p>\nInsertion_at_end(struct Node *Head, int key)\n{\n Ptr = (struct Node *) malloc(sizeof(struct node)); \n Ptr->Next = NULL; \n Ptr->Prev=NULL; \n Ptr->data = key; \n Head = Ptr; \n Temp = head; \n while (temp != NULL) \n temp = temp -> next; \n temp->Next = Ptr; \n Ptr->Prev = temp; \n Ptr->Next = NULL; \n}\n<\/pre>\nInsertion after a particular node<\/h4>\n
<\/a><\/p>\nInsert_after_particular_position(struct Node *Head, int key)\n{\n Ptr = (struct Node *) malloc(sizeof(struct node)); \/\/Allocating memory for the new node\n temp = Head; \n Ptr->data = key;\n for(i=0; i<position; i++) \n { \n temp = temp->Next; \n if(temp == NULL) \/\/ i.e. if the list is empty \n return; \n }\n Ptr->Next = temp->Next; \n Ptr->Prev = temp; \n temp->Next = Ptr; \n temp->Next->Prev = Ptr; \n}\n<\/pre>\nTime complexity of Insertion:<\/span><\/h3>\n