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 node’s next pointer points to
NULL. - The first node’s 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 1<->2<->3 with the head pointing to 1 and we added a new node 0 and the linked list becomes 0<->1<->2<->3 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 node’s next will point to the current node.
- The current node’s previous’s next will point to the new node.
- The new node’s previous will point to current’s previous.
- The current node’s previous will point to the new node.
As you can see below, we had a linked list 1<->3<->4 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 1<->2<->3<->4.
- 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 current’s next points to NULL. At this stage we will do the following 3 things:
- The current last node’s next will point to the new node.
- The new node’s previous will point to the current node.
- The new node’s next will point to NULL now.
As you can see below, we had a linked list 1<->2<->3<->NULL 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 1<->2<->3<->4<->NULL.
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 node’s next to the current node’s next. Also, current node’s next’s 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 node’s 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 node’s data. We will continue doing this until the current node’s 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 node’s 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 node’s next is not equal to null and in that case, the data is not present in our linked list, or better, we don’t 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 node’s 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
Let’s 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 <= size) {
dllNode newDllNode = new dllNode(data);
dllNode current = head;
if (index == 0) {
insertAtFirst(data);
} else if (index == size) {
insertAtLast(data);
} else {
for (int j = 0; j < index && current.next != null; j++) {
current = current.next;
}
newDllNode.next = current;
current.prev.next = newDllNode;
newDllNode.prev = current.prev;
current.prev = newDllNode;
size++;
}
} else {
System.out.println("Index " + index + " not valid for linked list of size " + size);
}
}
/**
*
* @return
*/
public void deleteFirstNode() {
if (head == null) {
System.out.println("List is empty");
}
dllNode first = head;
if (head.next == null) {
tail = null;
} else {
head.next.prev = null;
}
head = head.next;
size--;
}
/**
*
* @return
*/
public void deleteLastNode() {
if (tail == null) {
throw new RuntimeException("List is empty");
}
dllNode last = tail;
if (head.next == null) {
head = null;
} else {
tail.prev.next = null;
}
tail = tail.prev;
size--;
}
/**
*
* @param index
* @return
*/
public void deleteAtIndex(int index) {
if (index + 1 >= 0 && index + 1 <= size) {
dllNode current = head;
//remove at the start
if (index == 0) {
deleteFirstNode();
}
// remove at last
else if (index == size - 1) {
deleteLastNode();
} else {
for (int j = 0; j < index && current.next != null; j++) {
current = current.next;
}
current.prev.next = current.next;
current.next.prev = current.prev;
size--;
}
} else {
System.out.println("Index " + index + " not valid for linked list of size " + size);
}
}
/**
* Display forward
*/
public void displayFirstToLast() {
dllNode current = head;
System.out.print("The doubly linked list is --> ");
while (current != null) {
current.displayData();
current = current.next;
}
System.out.println("");
}
/**
* Display backwards
*/
public void displayLastToFirst() {
dllNode current = tail;
System.out.print("The doubly linked list is --> ");
while (current != null) {
current.displayData();
current = current.prev;
}
System.out.println("");
}
/**
* Search the given node in doubly linked list
* @param data
*/
public void searchNode(int data) {
//Node current will point to head
dllNode current = head;
if (head == null) {
System.out.println("Doubly linked list is empty");
return;
}
System.out.println("Search node with data " + data + " in doubly linked list");
while (current != null) {
if (current.data == data) {
System.out.println("node with data " + data + " found");
break;
}
current = current.next;
}
}
public static void main(String[] args) {
DoublyLinkedList list = new DoublyLinkedList();
list.insertAtFirst(1);
list.displayFirstToLast();
System.out.println("size :" + list.getSize());
list.displayFirstToLast();
list.insertAtFirst(2);
list.displayFirstToLast();
System.out.println("size :" + list.getSize());
list.insertAtLast(3);
list.displayFirstToLast();
System.out.println("size :" + list.getSize());
list.displayFirstToLast();
list.insertAtLast(4);
System.out.println("size :" + list.getSize());
list.displayFirstToLast();
list.insertAtIndex(5, 3);
System.out.println("size :" + list.getSize());
System.out.println("Linked list backward traversal");
list.displayLastToFirst();
System.out.println("Linked list forward traversal");
list.displayFirstToLast();
list.deleteAtIndex(2);
System.out.println("Node at index 2 has been deleted");
System.out.println("size :" + list.getSize());
list.displayFirstToLast();
list.deleteFirstNode();
System.out.println("First Node has been deleted");
System.out.println("size :" + list.getSize());
list.displayFirstToLast();
list.deleteLastNode();
System.out.println("Last Node has been deleted");
System.out.println("size :" + list.getSize());
list.displayFirstToLast();
list.searchNode(5);
list.displayFirstToLast();
}
}The Output:
Summary
In this article, we have learnt:
- The basics of Doubly Linked List.
- The usage of a Doubly Linked List.
- The benefits of a Doubly Linked List.
- The limitations of a Doubly Linked List.
- Comparison with Singly Linked List.
- The insertion and deletion in a Doubly Linked List
- The search and size of a Doubly Linked List
- The Java program to create a Singly-Linked List and perform all the operations.
- The test class and program output.
We can find the source code for this example at GitHub.
