In this article we will discuss the Doubly Linked List Data structure in Java.
You can also check this tutorial in the following video:
1. What is a Doubly Linked List in Java?
A Doubly Linked List is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes.
2. Difference b/w Singly Linked List and Doubly Linked List
This list (often abbreviated as DLL) is similar to a regular singly linked list (SLL).
Both DLL and SLL contain a pointer to the next node, as well as a data field to represent the actual value stored in the node.
Only difference between DLL and SLL is that the DLL also contains a pointer to the previous node, not just the next node.
A DDL must contain three variables:
- data variable
- next node variable
- previous node variable
3. Benefits of using Doubly Linked List
A DLL offers the following benefits over the Singly Linked List.
- Traversal is easy in both forward and backward direction.
- The delete operation is more efficient if pointer to the node to be deleted is given, because only 2 pointer reference of the target node needs to be changed, both of which are accessible from the target node.
- Insert a new node before a given node is faster.
In singly linked list, to delete a node, pointer to the previous node is needed. To get this previous node, sometimes the list is traversed. In DLL, we can get the previous node using previous pointer.
From the above points the, traversal in both direction proves to be the biggest benefits of DLL as it compliments all the other operations in the DLL.
4. Drawbacks of using Doubly Linked List
A DLL has certain drawbacks as well.
- Every node of DLL Require extra space for a previous pointer.
- All operations require an extra pointer previous to be maintained.
For the most part the drawback seems to be related to the expense of an extra space needed for the previous pointer.
5. Ideal Use cases for Doubly Linked List
In this section we will discuss, some of the common use cases for the DLL. A Linked List can be used in any situation where data needs to be stored but the size of the data is variable and fast retrieval of the data is required.
DLL can be used as a way to represent a deck of cards in a card game. Another real time usage will be the browser cache which allows you to hit the BACK button (a linked list of URLs). Although the browser cache can be implemented using the Stack Data structure alone as well, DLL is still being used for this use case.
DLLis used in constructing MRU/LRU (Most/Least Recently Used) cache. You can find the implementation using HashMap and DoublyLinkedList here.
6. Implementing Doubly Linked List
In this section, we will discuss the various operations supported by a DLL.
6.1 Insert At Start
Using insertAtStart() function we insert an element in the beginning of doubly Linked List. Details of the function is shared in DLL.java.
6.2 Insert At End
Using insertAtEnd() function we insert an element at the end of doubly Linked List. Details of the function is shared in DLL.java.
6.3 Insert at Pos
Using insertAtPos() function we insert an element at a position in doubly Linked List. Details of the function is shared in DLL.java.
6.4 Delete At Start
Using delete at start function we delete an element from the start of DLL. Detailed implementation is in deleteAtPos() function in DLL.java.
6.5 Delete At End
Using delete at end function we delete an element from the end of DLL. Detailed implementation is in deleteAtPos() function in DLL.java.
6.6 Delete At Pos
Using delete at pos function we delete an element from the end of DLL. Detailed implementation is in deleteAtPos() function in DLL.java.
For the deletion of a node from the doubly linked list, all 3 cases (start, end and pos) are covered in deleteAtPos() function in DLL.java.
Node.java
public class Node {
protected int data;
protected Node next, prev;
public Node() {
next = null;
prev = null;
data = 0;
}
public Node(int d, Node n, Node p) {
data = d;
next = n;
prev = p;
}
public void setLinkNext(Node n) {
next = n;
}
public void setLinkPrev(Node p) {
prev = p;
}
public Node getLinkNext() {
return next;
}
public Node getLinkPrev() {
return prev;
}
public void setData(int d) {
data = d;
}
public int getData() {
return data;
}
}
LinkedList.java
public class LinkedList {
protected Node start;
protected Node end;
public int size;
public LinkedList() {
start = null;
end = null;
size = 0;
}
public boolean isEmpty() {
return start == null;
}
public int getSize() {
return size;
}
public void insertAtStart(int val) {
Node nptr = new Node(val, null, null);
if (start == null) {
start = nptr;
end = start;
} else {
start.setLinkPrev(nptr);
nptr.setLinkNext(start);
start = nptr;
}
size++;
}
public void insertAtEnd(int val) {
Node nptr = new Node(val, null, null);
if (start == null) {
start = nptr;
end = start;
} else {
nptr.setLinkPrev(end);
end.setLinkNext(nptr);
end = nptr;
}
size++;
}
public void insertAtPos(int val, int pos) {
Node nptr = new Node(val, null, null);
if (pos == 1) {
insertAtStart(val);
return;
}
Node ptr = start;
for (int i = 2; i <= size; i++) {
if (i == pos) {
Node tmp = ptr.getLinkNext();
ptr.setLinkNext(nptr);
nptr.setLinkPrev(ptr);
nptr.setLinkNext(tmp);
tmp.setLinkPrev(nptr);
}
ptr = ptr.getLinkNext();
}
size++;
}
public void deleteAtPos(int pos) {
if (pos == 1) {
if (size == 1) {
start = null;
end = null;
size = 0;
return;
}
start = start.getLinkNext();
start.setLinkPrev(null);
size--;
return;
}
if (pos == size) {
end = end.getLinkPrev();
end.setLinkNext(null);
size--;
}
Node ptr = start.getLinkNext();
for (int i = 2; i <= size; i++) {
if (i == pos) {
Node p = ptr.getLinkPrev();
Node n = ptr.getLinkNext();
p.setLinkNext(n);
n.setLinkPrev(p);
size--;
return;
}
ptr = ptr.getLinkNext();
}
}
public void display() {
System.out.print("\nDoubly Linked List = ");
if (size == 0) {
System.out.print("empty\n");
return;
}
if (start.getLinkNext() == null) {
System.out.println(start.getData());
return;
}
Node ptr = start;
System.out.print(start.getData() + " <-> ");
ptr = start.getLinkNext();
while (ptr.getLinkNext() != null) {
System.out.print(ptr.getData() + " <-> ");
ptr = ptr.getLinkNext();
}
System.out.print(ptr.getData() + "\n");
}
}
DLL.java
public class DLL {
public static void main(String[] args) {
linkedList list = new linkedList();
System.out.println("Doubly Linked List Test");
System.out.println("Insert at Start");
list.insertAtStart(0);
list.display();
System.out.println("Insert at End");
list.insertAtEnd(5);
list.display();
System.out.println("Insert at Position");
list.insertAtPos(1, 2);
list.insertAtPos(2, 3);
list.insertAtPos(3, 4);
list.display();
System.out.println("Deleting at Position 1");
list.deleteAtPos(1);
list.display();
}
}
Output is shown in the snapshot below.
7. Summary
To Summarise, we have covered all the basic functionalities of DLL, with implementation from scratch in Java, in this Article. In Java, we have libraries which contains the optimised implementation of doubly linked list, most famous of those is LinkedList class in Java Collection Framework.
8. Download The Source Code
This was a Doubly Linked List Java example.
You can download the full source code of this example here: Doubly Linked List Java Example
