In the last article, we discussed the custom implementation of a single linked list in Java. Now, let us discuss how can we implement doubly linked lists in Java. We will provide a custom implementation of doubly-linked lists and perform multiple operations such as insertion, deletion, and traversal. At the end of the post, you should be able to insert and delete a node at head, tail or any specified position.
What is Doubly Linked List
Linked list is a linear data structure containing interconnected nodes through pointers. Each node contains 2 fields - data and a pointer to the next node. Since there is no concept of pointers in Java, each node holds the reference of another node. Whereas, the doubly-linked list is a type of linked list in which each node contains 3 fields - two pointers and data. The left pointer points to the previous node of the current node and the right pointer point to the next node of the current node.
Below is a visualization of a doubly-linked list.
Image Ref: Wikipedia
The main advantage of a doubly linked list is that given a node in the list, we can navigate in both directions. Hence, the different operations on a doubly-linked list becomes easier such as we can delete a node even if we don't have previous nodes address. But the insertion or deletion of a node takes a bit longer due to more pointer operations. Also, doubly-linked list requires more space as each node requires an extra pointer to point to the previous node of the current node.
Doubly Linked List Node Implmentation
As a doubly linked list contains 3 fields, the node implementation has also 3 fields - the data, a reference to the previous node and a reference to next node.
public class DLLNode { private int data; private DLLNode prev; private DLLNode next; public DLLNode(int data){ this.data = data; prev = null; next = null; } //setters and getters }
Doubly Linked Lists Declaration
Now, once we have the node implemented, let us declare the template of doubly linked list. We have references to head and tail node and the method signature of all the operations that we will be performing on the list.
public class DoubleLinkedList {
private DLLNode head;
private DLLNode tail;
public DoubleLinkedList(){
}
public void insertHead(int data){
}
public void insertAtTail(int data){
}
public void insertAt(int position, int data){
}
public void deleteHead(){
}
public void deleteTail(){
}
public void deleteAt(int position){
}
public void traverse(){
}
}
Doubly Linked Lists Operations
Insertion Operation
The first insertion is at the beginning of the list. In this case, new node is inserted before the head node. For that, update the right pointer of new node to point the current head node and make the left pointer of new node as NULL.
Update head node left pointer to point to the new node and make the new node as head.
public void insertHead(int data){
DLLNode nodeToBeInserted = new DLLNode(data);
if(head == null){
tail = nodeToBeInserted;
}else {
head.setPrev(nodeToBeInserted);
}
nodeToBeInserted.setNext(head);
head = nodeToBeInserted;
}
Now, let us insert a node at tail. For that, new node right pointer should point to NULL and left pointer points to the end of the list.
public void insertTail(int data){
DLLNode nodeToBeInserted = new DLLNode(data);
tail.setNext(nodeToBeInserted);
nodeToBeInserted.setPrev(tail);
this.tail = nodeToBeInserted;
}
For insertion of a node at a given position, new node right pointer points to the next node of the position node and new node left pointer points to the position node. Next, the position node right pointer should point to the new node and the next node of position node left pointer should point to the new node.
public void insertAt(int position, int data){
DLLNode nodeToBeInserted = new DLLNode(data);
DLLNode temp = head;
for(int i = 0; i < position; i++){
temp = temp.getNext();
}
nodeToBeInserted.setPrev(temp);
nodeToBeInserted.setNext(temp.getNext());
temp.setNext(nodeToBeInserted);
nodeToBeInserted.getNext().setPrev(nodeToBeInserted);
}
Deletion Operation
We can either delete the head or tail or at a particular node.
To delete the head first create a temp node from the head node. Now move the pointer of next node of temp node to head.
public void deleteHead(){
DLLNode temp = head;
this.head = temp.getNext();
this.head.setPrev(null);
}
To delete the last node, update tail node previous node next pointer with NULL.
public void deleteTail(){
DLLNode previous = tail.getPrev();
previous.setNext(null);
this.tail = previous;
}
Let us delete a node at a particular position. Once, we reach at that position, change the previous node next pointer to the next node of the node to be deleted and then dispose the current node to be deleted.
public void deleteAt(int position){
DLLNode temp = head;
for(int i = 0; i < position; i++){
temp = temp.getNext();
}
temp.getPrev().setNext(temp.getNext());
temp.getNext().setPrev(temp.getPrev());
}
Doubly Linked List Traversal
Visit each node recursively until we find the tail node whose next pointer is pointing to null.
public void traverse(){
StringBuilder result = new StringBuilder("[");
DLLNode temp = head;
while (temp.getNext() != null){
result.append(temp.getData() + ", ");
temp = temp.getNext();
}
result.append(temp.getData() + "]");
System.out.println(result.toString());
}
Doubly Linked List Runner
Below is the runner class with main method to perform all the linked list operations.
public class DoubleLinkedListRunner {
public static void main(String[] args) {
DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
doubleLinkedList.insertHead(3);
doubleLinkedList.insertHead(9);
doubleLinkedList.insertHead(40);
doubleLinkedList.insertHead(17);
doubleLinkedList.insertHead(91);
doubleLinkedList.insertTail(4);
doubleLinkedList.insertAt(1, 33);
System.out.println("Print the list");
doubleLinkedList.traverse();
System.out.println("Deleting head");
doubleLinkedList.deleteHead();
System.out.println("Print the list after deleting head.");
doubleLinkedList.traverse();
System.out.println("Deleting tail");
doubleLinkedList.deleteTail();
System.out.println("Print the list after deleting tail.");
doubleLinkedList.traverse();
System.out.println("Deleting from position 3");
doubleLinkedList.deleteAt(2);
System.out.println("Print the list after deleting at position 3.");
doubleLinkedList.traverse();
}
}
Conclusion
In this article, we discussed how can we implement doubly linked lists in Java. We provided a custom implementation of doubly-linked lists and perform multiple operations such as insertion, deletion, and traversal.
