Doubly Linked List in Java
Doubly Linked List in Java Programming
This article explores the concept of Doubly Linked List in Java, their structure, operations, code implementation, algorithmic steps, time and space complexity, and real world use cases.
Doubly Linked List (DLL) is a powerful and flexible data structure that allows efficient insertion and deletion of elements from both ends of the list. Unlike a singly linked list, each node in a doubly linked list has two pointers: one pointing to the next node and the other to the previous node.
Structure of a Doubly Linked List in Java
Difference between a Linked List and a Doubly Linked is that singly linked list just has reference to the next node in the chain while doubly linked list has reference to both previous and next node in the chain.
Doubly Linked List is a type of linear data structure consisting of nodes where each node contains three parts:
- Data
- Pointer to the next node (next)
- Pointer to the previous node (prev)
Bidirectional linkage allows traversal in both directions i.e. forward and backward, making it more versatile than singly linked lists.
Structure of a Node
Here’s how a single node is structured in a DLL:
class Node {
int data;
Node next;
Node prev;
Node(int data) {
this.data = data;
next = null;
prev = null;
}
}
Each node stores a value and two references: one to the next node and one to the previous.
Learn DSA
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Operations on a Doubly Linked List in Java
Following operations can be performed on a doubly linked list:
- Insertion
- Insertion at the beginning.
- Insertion at the end.
- Insertion at a specific position.
- Deletion
- Deletion from the beginning.
- Deletion from the end.
- Deletion from a specific position.
In our examples, we will focus on insertion/deletion at beginning
Code for Adding a Node in Doubly Linked List
Let us look at the code for insertion in a Doubly Linked List, specifically focusing on adding a node at the beginning, which is one of the most common operations. This operation involves a few key checks and pointer updates:
Steps Required:
1. Check if the list is empty
- If the list is empty, the new node becomes the head.
2. Otherwise, the new node should point to the current head.
- The current head’s previous pointer is updated to point back to the new node.
- The head is updated to the new node.
This method uses class instances to call functions.
import java.lang.*;
class DoublyLinkedList {
Node head;
// Node Class
class Node {
int data;
Node next, prev;
Node(int x) // parameterized constructor
{
data = x;
next = null;
prev = null;
}
}
// inserts at first position
public void insertNode(int data) {
// Creating newNode memory & assigning data value
Node newNode = new Node(data);
newNode.next = head;
newNode.prev = null;
// if DLL had already >=1 nodes
if (head != null)
head.prev = newNode;
// changing head to this
head = newNode;
System.out.println(newNode.data + " inserted");
}
public void display() {
Node node = head;
Node end = null;
//as linked list will end when Node reaches Null
System.out.print("\nIn forward: ");
while (node != null) {
System.out.print(node.data + " ");
end = node;
node = node.next;
}
System.out.print("\nIn backward: ");
while (end != null) {
System.out.print(end.data + " ");
end = end.prev;
}
System.out.println("\n");
}
}
class Main{
public static void main(String args[])
{
DoublyLinkedList dll = new DoublyLinkedList();
dll.insertNode(26);
dll.insertNode(25);
dll.insertNode(24);
dll.display();
dll.insertNode(23);
dll.insertNode(22);
dll.insertNode(21);
dll.insertNode(20);
dll.display();
}
}Output
26 inserted 25 inserted 24 inserted In forward: 24 25 26 In backward: 26 25 24 23 inserted 22 inserted 21 inserted 20 inserted In forward: 20 21 22 23 24 25 26 In backward: 26 25 24 23 22 21 20
This method uses static methods to call functions.
import java.lang.*;
// Node Class
class Node {
int data;
Node next, prev;
Node(int x) // parameterized constructor
{
data = x;
next = null;
prev = null;
}
}
class Main
{
static Node insertNode(Node head, int data)
{
// Creating newNode memory & assigning data value
Node newNode = new Node(data);
newNode.next = head;
newNode.prev = null;
// if DLL had already >=1 nodes
if(head !=null)
head.prev = newNode;
// changing head to this
head = newNode;
System.out.println(newNode.data + " inserted");
return head;
}
static void display(Node node) {
Node end = null;
//as linked list will end when Node reaches Null
System.out.print("\nIn forward: ");
while(node!=null)
{
System.out.print(node.data + " ");
end = node;
node = node.next;
}
System.out.print("\nIn backward: ");
while (end != null) {
System.out.print(end.data + " ");
end = end.prev;
}
System.out.println("\n");
}
public static void main(String args[])
{
Node head = null;
head = insertNode(head,26);
head = insertNode(head,25);
head = insertNode(head,24);
display(head);
head = insertNode(head,23);
head = insertNode(head,22);
head = insertNode(head,21);
head = insertNode(head,20);
display(head);
}
}Output
26 inserted 25 inserted 24 inserted In forward: 24 25 26 In backward: 26 25 24 23 inserted 22 inserted 21 inserted 20 inserted In forward: 20 21 22 23 24 25 26 In backward: 26 25 24 23 22 21 20
Code for Deleting a Node in Doubly Linked List
Let us look at the code for deletion, we will for now focus on deletion from the start which is the default nature in a linked list. Which will require the following –
- Checking if the doubly linked list is empty
- No deletion possible
- Checking if the doubly Linked list has a single node
- Changing the head to null
- Otherwise, moving the head node to next node and changing previous of new head to null
This method uses class instances to call functions.
import java.lang.*;
class DoublyLinkedList {
Node head;
// Node Class
class Node {
int data;
Node next, prev;
Node(int x) // parameterized constructor
{
data = x;
next = null;
prev = null;
}
}
// inserts at first position
public void insertNode(int data) {
// Creating newNode memory & assigning data value
Node newNode = new Node(data);
newNode.next = head;
newNode.prev = null;
// if DLL had already >=1 nodes
if (head != null)
head.prev = newNode;
// changing head to this
head = newNode;
}
public void deleteNode(){
Node temp = head;
// if DLL is empty
if(head == null){
System.out.println("Linked List Empty, nothing to delete");
return;
}
// if Linked List has only 1 node
if(temp.next == null){
System.out.println(temp.data + " deleted");
head = null;
return;
}
// move head to next node
head = head.next;
// assign head node's previous to NULL
head.prev = null;
System.out.println(temp.data + " deleted");
}
public void display() {
Node node = head;
Node end = null;
//as linked list will end when Node reaches Null
System.out.print("\nIn forward: ");
while (node != null) {
System.out.print(node.data + " ");
end = node;
node = node.next;
}
System.out.print("\nIn backward: ");
while (end != null) {
System.out.print(end.data + " ");
end = end.prev;
}
System.out.println("\n");
}
}
class Main{
public static void main(String args[])
{
DoublyLinkedList dll = new DoublyLinkedList();
dll.insertNode(26);
dll.insertNode(25);
dll.insertNode(24);
dll.insertNode(23);
dll.insertNode(22);
dll.insertNode(21);
dll.insertNode(20);
dll.display();
dll.deleteNode();
dll.deleteNode();
dll.deleteNode();
dll.display();
}
}Output
In forward: 20 21 22 23 24 25 26 In backward: 26 25 24 23 22 21 20 20 deleted 21 deleted 22 deleted In forward: 23 24 25 26 In backward: 26 25 24 23
This method uses static methods to call functions.
import java.lang.*;
// Node Class
class Node {
int data;
Node next, prev;
Node(int x) // parameterized constructor
{
data = x;
next = null;
prev = null;
}
}
class Main
{
// inserts a node at the first position
static Node insertNode(Node head, int data)
{
// Creating newNode memory & assigning data value
Node newNode = new Node(data);
newNode.next = head;
newNode.prev = null;
// if DLL had already >=1 nodes
if(head !=null)
head.prev = newNode;
// changing head to this
head = newNode;
return head;
}
// deletes the first node in doubly linked list
public static Node deleteNode(Node head)
{
Node temp = head;
// if DLL is empty
if(head == null){
System.out.println("Linked List Empty, nothing to delete");
return head;
}
// if Linked List has only 1 node
if(temp.next == null){
System.out.println(temp.data + " deleted");
head = null;
return head;
}
// move head to next node
head = head.next;
// assign head node's previous to NULL
head.prev = null;
System.out.println(temp.data + " deleted");
return head;
}
static void display(Node node) {
Node end = null;
//as linked list will end when Node reaches Null
System.out.print("\nIn forward: ");
while(node!=null)
{
System.out.print(node.data + " ");
end = node;
node = node.next;
}
System.out.print("\nIn backward: ");
while (end != null) {
System.out.print(end.data + " ");
end = end.prev;
}
System.out.println("\n");
}
public static void main(String args[])
{
Node head = null;
head = insertNode(head,26);
head = insertNode(head,25);
head = insertNode(head,24);
head = insertNode(head,23);
head = insertNode(head,22);
head = insertNode(head,21);
head = insertNode(head,20);
display(head);
head = deleteNode(head);
head = deleteNode(head);
head = deleteNode(head);
display(head);
}
}Output
In forward: 20 21 22 23 24 25 26 In backward: 26 25 24 23 22 21 20 20 deleted 21 deleted 22 deleted In forward: 23 24 25 26 In backward: 26 25 24 23
Merits of Doubly Linked List
- A Doubly Linked List can be traversed in any given Direction Since it has pointers to both the next and the previous Node of the List.
- It is easier to reverse a Doubly Linked List.
- Both Deletion and Insertion and easier in a Doubly Linked List.
Demerits of Doubly Linked List
- Every operation on a Doubly Linked List requires an extra step to perform calculations on that extra address stored with each node.
- Every Node requires extra space in the memory to store that one extra address.
Time and Space Complexity for Doubly Linked List Operations
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| Insertion (begin) | O(1) | O(1) |
| Insertion (end) | O(n) | O(1) |
| Deletion | O(1) | O(1) |
| Traversal | O(n) | O(1) |
To wrap it up….
Doubly linked lists are highly efficient when you need bi directional navigation and frequent insertions/deletions.
While they require more memory due to the extra pointer, the trade off is worth it for applications needing dynamic data manipulation.
In Java, you can create custom doubly linked list implementations or use built-in classes like LinkedList from java.util which internally uses a doubly linked list.
However, understanding the underlying mechanics as shown above is crucial for building efficient algorithms and solving data structure interview problems.
FAQ's related to Doubly Linked List in Java
Answer:
Singly linked list contains nodes with data and a single pointer pointing to the next node. In contrast, a doubly linked list contains nodes with two pointers, one pointing to the next node and another pointing to the previous node, allowing traversal in both directions.
Answer:
You should use a doubly linked list when you need:
- Efficient backward traversal.
- Frequent insertions and deletions from both ends or from the middle of the list.
- It offers more flexibility compared to singly linked lists, especially for complex data structures like Deques or Navigation systems.
Answer:
- Insertion at beginning: O(1)
- Insertion at end: O(n) (unless tail pointer is used, then O(1))
- Deletion of a known node: O(1)
These operations are efficient because the list maintains pointers in both directions.
Answer:
Yes. Each node in a doubly linked list stores an extra pointer (prev) compared to a singly linked list. This additional pointer increases memory usage but allows more flexible and efficient navigation and modifications.
Answer:
Technically yes, but it’s not recommended. Without a head pointer, you lose the ability to easily access the start of the list, making traversal and basic operations less efficient and more complex to implement.
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment