In this article, we are going to understand what a doubly linked list is. We will also see insertions, deletions, and search in a doubly linked list. We will also implement a doubly linked list in Java.
What is a Doubly linked list in Java
A Doubly Linked List [DLL] contains two pointers instead of one in Singly Linked List, we call them previous and next. Along with these two pointers, it also contains the data. The previous pointer points to the previous node in the list and the next pointers points to the next node in the list. The previous pointer of the first node of the list points to NULL and the next pointer of the last node also points to NULL.
The two pointers help to traverse both in forward and backward direction though it takes extra space for storing the previous pointer.
1. Advantages over a singly linked list
- Major advantage of a doubly linked list is that we can traverse it in both directions.
- Adding a new node is just about changing the pointers.
- Deleting a node is also easy as we need not traverse the entire list to find the previous node as with the singly linked list.
2. Disadvantages over a singly linked list
- Typical disadvantage is that a doubly linked list node requires extra space for storing the previous pointer.
- Insertion or deletion operations require an extra pointer [previous] to be maintained. We need to maintain both the next and previous pointer while inserting a new node.
3. Doubly Linked List Representation
A doubly linked list is made of a sequence of nodes. Each node contains a value [data], a pointer to the next node, and a pointer to the previous node in the sequence.
As per the above illustration, the following are the important points to be considered.
- The Head node points to the first node of the list.
- Each node has a data field, a pointer to previous node and a pointer to the next node.
- The last nodes next pointer points to NULL.
- The first nodes previous pointer points to NULL.
4. Basic Operations
We will go through the major operations of a linked list, and they are insertion, deletion, display, search, and size.
4.1. Insertion
In a doubly linked list, we can insert a node in three different ways.
- Insert the new node as the first node:
I will add the new node before the first node of the doubly linked list and its next will point to previous first node. The previous will point to null. The head will now point to the newly added node. As you can see below, we had a linked list 123 with the head pointing to 1 and we added a new node 0 and the linked list becomes 0123 with the head pointing to node 0 now.
- At a given index:
If we wish to insert a node at any index, we will first check if the index is less than the size of the list, we will then first traverse till the index. Next, we will do four things:
- The new nodes next will point to the current node.
- The current nodes previouss next will point to the new node.
- The new nodes previous will point to currents previous.
- The current nodes previous will point to the new node.
As you can see below, we had a linked list 134 and we want to insert node 2 at index 1, so we will change the pointers as per the above steps and the linked list will become 1234.
- At the end of the linked list:
When we want to insert a node at the end of a doubly linked list, we will traverse the doubly linked list till the currents next points to NULL. At this stage we will do the following 3 things:
- The current last nodes next will point to the new node.
- The new nodes previous will point to the current node.
- The new nodes next will point to NULL now.
As you can see below, we had a linked list 123NULL and we want to insert node 4 at last, so we will change the pointers as per the above steps and the linked list will become 1234NULL.
4.2. Deletion:
Like insertion, we can delete a node from a doubly linked list in 3 ways. To delete a node from the doubly linked list, we need to do the following steps.
- Delete the first node
To delete the first node from the doubly linked list, point the head to the current first nodes next. You can see the illustration in the following diagram.
- Delete at an index:
To delete an element at the index from the doubly linked list, we first check if the index is less than the size of the list. We then traverse till the index [using the current.next != null and by keeping track of current and previous node] and change the previous nodes next to the current nodes next. Also, current nodes nexts previous has to point to previous node.You can see the illustration in the following diagram.
- Delete the last element
To delete the last element from the doubly linked list, traverse till the second last element [using current.next != null and keeping track of the previous node] and change the previous nodes next to null.You can see the illustration in the following diagram.
You can see the code for all the deletion below
4.3. Display
To display the nodes of the doubly linked list, we will need to start from the head and print the nodes data. We will continue doing this until the current nodes next is not equal to null, and that means the end of the list.You can see the code for this below.
4.4. Search
To search for a node of the linked list, we will need to start from the head and check if the current nodes data is equal to the data, or else we will move to the next node in the list. We will continue to go to the next node until the current nodes next is not equal to null and in that case, the data is not present in our linked list, or better, we dont have a node that has the data. You can see the code for this below.
4.5. Display
To calculate the size of a doubly linked list, we will set a counter at 0 and keep incrementing by 1 once we visit a node. We will start with the head and continue to go to the next node until the current nodes next is not equal to NULL. As said, we will increment the counter for each node we traverse. At the end, we will have the size of the list in the counter variable. You can see the code for this below. In our example, we are updating the size variable at every insert and delete, so we can directly use that variable.
5. Time and Space Complexity
6. Doubly linked list in Java Example
Lets look at the double linked list implementation.
package com.javadevjournal.list; public class DoublyLinkedList { static class dllNode { //data int data; // next node in the list dllNode next; // previous node in the list dllNode prev; dllNode[int data] { this.data = data; } public void displayData[] { System.out.print[" " + data]; } } private dllNode head; private dllNode tail; public int getSize[] { return size; } public void setSize[int size] { this.size = size; } private int size = 0; // constructor public DoublyLinkedList[] { this.head = null; this.tail = null; } public boolean isEmpty[] { return head == null; } /** * insertAtFirst * @param data */ public void insertAtFirst[int data] { dllNode newDllNode = new dllNode[data]; // for the first element, head and tail both will point to it. if [isEmpty[]] { tail = newDllNode; } else { head.prev = newDllNode; } newDllNode.next = head; head = newDllNode; size++; } /** * insertAtLast * @param data */ public void insertAtLast[int data] { dllNode newDllNode = new dllNode[data]; // for the first element, head and tail both will point to it. if [isEmpty[]] { head = newDllNode; } else { tail.next = newDllNode; newDllNode.prev = tail; } tail = newDllNode; size++; } /** * * @param data * @param index */ public void insertAtIndex[int data, int index] { if [index >= 0 && index = 0 && index + 1