Doubly Linked In C++As in the singly linked list, the doubly linked list also has a head and a tail. The previous pointer of the head is set to NULL as this is the first node. The next pointer of the tail node is set to NULL as this is the last node. Show A basic layout of the doubly linked list is shown in the below diagram. Following is representation of a DLL node in C language. C++
C
Java
Python3
C#
Javascript
Following are advantages/disadvantages of doubly linked list over singly linked list. Disadvantages over singly linked list Recommended: Please solve it on “PRACTICE” first, before moving on to the solution. 1) Add a node at the front: (A 5 steps process) Following are the 5 steps to add node at the front. C++
C
Java
Python3
C#
Javascript
Four steps of the above five steps are same as the 4 steps used for inserting at the front in singly linked list. The only extra step is to change previous of head. C++
C
Java
Python3
C#
Javascript
Five of the above steps step process are same as the 5 steps used for inserting after a given node in singly linked list. The two extra steps are needed to change previous pointer of new node and previous pointer of new node’s next node. Following are the 7 steps to add node at the end. C++
C
Java
Python3
C#
Javascript
Six of the above 7 steps are same as the 6 steps used for inserting after a given node in singly linked list. The one extra step is needed to change previous pointer of new node. Steps
Below is the implementation of the above approach: Code block Output: Created DLL is: Traversal in forward Direction 9 1 5 7 6 Traversal in reverse direction 6 7 5 1 9 A complete working program to test above functions. C++
C
Java
Python3
C#
Javascript
Output: Created DLL is: Traversal in forward Direction 1 7 5 8 6 4 Traversal in reverse direction 4 6 8 5 7 1Also see: Delete a node in double Link List
Article Tags :
Data Structures Linked List
doubly linked list Visa Practice Tags :
Visa Data Structures Linked List Doubly Linked ListDoubly linked list is a type of linked list in which each node apart from storing its data has two links. The first link points to the previous node in the list and the second link points to the next node in the list. The first node of the list has its previous link pointing to NULL similarly the last node of the list has its next node pointing to NULL. The two links help us to traverse the list in both backward and forward direction. But storing an extra link requires some extra space. Doubly linked listDoubly linked list is a complex type of linked list in which a node contains a pointer to the previous as well as the next node in the sequence. Therefore, in a doubly linked list, a node consists of three parts: node data, pointer to the next node in sequence (next pointer) , pointer to the previous node (previous pointer). A sample node in a doubly linked list is shown in the figure. A doubly linked list containing three nodes having numbers from 1 to 3 in their data part, is shown in the following image. In C, structure of a node in doubly linked list can be given as : The prev part of the first node and the next part of the last node will always contain null indicating end in each direction. In a singly linked list, we could traverse only in one direction, because each node contains address of the next node and it doesn't have any record of its previous nodes. However, doubly linked list overcome this limitation of singly linked list. Due to the fact that, each node of the list contains the address of its previous node, we can find all the details about the previous node as well by using the previous address stored inside the previous part of each node. Doubly Linked ListIn this tutorial, you will learn about the doubly linke list and its implementation in Python, Java, C, and C++. A doubly linked list is a type of linked list in which each node consists of 3 components:
Note: Before you proceed further, make sure to learn about pointers and structs. |