Doubly Linked List
Welcome!! In this article, we will learn about Doubly Linked List
I strongly recommend you to go through the Linked List Data structure as a pre-requisite for this article.
Doubly LinkedList is a type of Linked List in which a node contains a pointer to the previous node as well as the next node in the sequence. Unlike Singly Linked List, In Doubly Linked List a node consists of three parts: node data, a pointer to the next node in sequence (next pointer), a pointer to the previous node (previous pointer).
The previous pointer of the first node and the next pointer of the last node always represent NULL indicating the end at each side. In singly Linked List we can only traverse in a forward direction since a node has a pointer that carries the address of the next pointer but it doesn't have a pointer pointing to the previous node. This limitation of Singly Linked List is overcome by Doubly Linked List.
Read this to know about more Singly Linked List
Memory representation of Doubly Linked List.
Since each node contains two pointers consisting of addresses of previous and next nodes, it consumes more space for every node when compared to a singly Linked List.
In the below-given image, the first element of Linked List i.e., 14 stored at the address 1. Since it is the first node, the previous is NULL. The next node of the list resides at address 3 therefore the first node contains 3 in its next pointer.
Read this to know more about memory management of Linked List
Inserting a node in a Doubly Linked List
A node can be inserted into a Linked List in 4 ways
- At front of the DLL
- After a given node.
- At the end of the DLL.
- Before a given node.
Add a node at the front:
To add a new node at the front, we need to make the previous of the new node as null and make the head point to the new node. Say for example there is a linked list 2 ->3->4 and we want to add 1 at the front then point head to 1 and point next pointer of 1 to 2 and point the previous pointer of 2 to 1.
public void push(int new_data){ /* 1. allocate node * 2. put in the data */ Node new_Node = new Node(new_data); /* 3. Make next of new node as head and previous as NULL */ new_Node.next = head; new_Node.prev = null; /* 4. change prev of head node to new node */ if (head != null) head.prev = new_Node; /* 5. move the head to point to the new node */ head = new_Node;}
Add after a given node
Now, we have a pointer given to a node as the prev_node and we need to add the new_node after the given node.
/* Given a node as prev_node, insert a new node after the given node */public void InsertAfter(Node prev_Node, int new_data){ /*1. check if the given prev_node is NULL */ if (prev_Node == null) { System.out.println("The given previous node cannot be NULL ");
return; } /* 2. allocate node * 3. put in the data */ Node new_node = new Node(new_data); /* 4. Make next of new node as next of prev_node */ new_node.next = prev_Node.next; /* 5. Make the next of prev_node as new_node */ prev_Node.next = new_node; /* 6. Make prev_node as previous of new_node */ new_node.prev = prev_Node; /* 7. Change previous of new_node's next node */ if (new_node.next != null) new_node.next.prev = new_node;}
Add a node at the end
To add a node at the end of a doubly-linked list we need to point the next of current last node to the new node and mark the new node’s next as null.
// Add a node at the end of the listvoid append(int new_data){ /* 1. allocate node * 2. put in the data */ Node new_node = new Node(new_data); Node last = head; /* used in step 5*/ /* 3. This new node is going to be the last node, so * make next of it as NULL*/ new_node.next = null; /* 4. If the Linked List is empty, then make the new * node as head */ if (head == null) { new_node.prev = null; head = new_node; return; } /* 5. Else traverse till the last node */ while (last.next != null) last = last.next; /* 6. Change the next of last node */ last.next = new_node; /* 7. Make last node as previous of new node */ new_node.prev = last;}
Add a node before a given node
Steps
Let the pointer to this given node be next_node and the data of the new node to be added as new_data.
- Check if the next_node is NULL or not. If it’s NULL, return from the function because any new node can not be added before a NULL
- Allocate memory for the new node, let it be called new_node
- Set new_node->data = new_data
- Set the previous pointer of this new_node as the previous node of the next_node, new_node->prev = next_node->prev
- Set the previous pointer of the next_node as the new_node, next_node->prev = new_node
- Set the next pointer of this new_node as the next_node, new_node->next = next_node;
- If the previous node of the new_node is not NULL, then set the next pointer of this previous node as new_node, new_node->prev->next = new_node
- Else, if the prev of new_node is NULL, it will be the new head node. So, make (*head_ref) = new_node.
public void InsertBefore(Node next_node, int new_data){ /*Check if the given nx_node is NULL*/ if (next_node == null) {
System.out.println("The given next node can not be NULL");
return; } // Allocate node, put in the data Node new_node = new Node(new_data); // Making prev of new node as prev of next node new_node.prev = next_node.prev; // Making prev of next node as new node next_node.prev = new_node; // Making next of new node as next node new_node.next = next_node; // Check if new node is added as head if (new_node.prev != null) new_node.prev.next = new_node; else head = new_node;}
Conclusion
In this article, we have seen about the doubly Linked list and their memory allocation. Also, we have seen how to add a node at different places in a doubly-linked list using java code.
