Introduction to Doubly Linked List

Memory Representation of Doubly Linked List

A Doubly Linked List is depicted using linear memory arrays where each memory address stores three components: the data, the address of the next element, and the address of the previous element. -1 is used to represent the null. Suppose we have data as P, Q, R, and S with their respective address. Let us look at the memory representation of this doubly linked list:

Basic Operations on Doubly Linked Lists

Following are the basic operations supported by Doubly Linked Lists:

1. Insertion

The insertion can be done at three positions in a doubly linked list: beginning, end, and an arbitrary position. To insert a node at the beginning of a doubly linked list, create a new node, update its forward pointer to the current head, set the backward pointer of the current head to the new node, and update the head pointer. For insertion at the end, create a new node, set its forward pointer to NULL (indicating the new tail), update its backward pointer to the current tail, and adjust the forward pointer of the current tail. To insert at an arbitrary position, find the location, update neighboring nodes' pointers, and insert the new node.

2. Deletion

This operation is used to remove elements from the list. The node to be deleted may be the first node, last node, or any node in between the first and last node. To delete the first node, update the head pointer to the next node, ensuring the new head's pointers are NULL if it's the only node left. Deleting the last node involves updating the tail pointer to the previous node, with NULL pointers if it's the sole node. For deleting a node at a specific position, locate the node, update neighboring nodes' pointers to bypass it, and free its memory.

3. Traversal

This operation is used to access each element of the list. The Linked List is traversed when printing the contents of the linked list. Doubly linked lists support bidirectional traversal. To traverse the list in the forward direction, start at the head node and follow the forward pointers until you reach the end (tail) of the list. To traverse in the reverse direction, start at the tail node and follow the backward pointers until you reach the beginning (head) of the list.

Insertion on a Doubly Linked Lists

A Node in a doubly-linked list has a pointer to both the previous and the next node of the linked list. Insertion of a new node in an existing doubly linked list can be done in the following places:

• Insertion at the Beginning
• Insertion at the End
• Insertion after a given Node

1. Insertion at the Beginning

The head pointer points to the first node of the doubly linked list, and the previous pointer of the first node points to Null. To insert a node at the beginning of the Linked List, the head pointer should point to the new first node, and the next pointer of the new first node must point to the previous first node.

The code for insertion of a new node at the beginning of a doubly linked list in Java is given below:

/* 
	Function for insertion of a new node at the beginning of
	a doubly linked list
*/
public void insertAtBeginning(int data) {
    /* 
   	    Making a new node with the given data. Note that the
   	    previous and next pointer of this node are null 
   */
    Node new_node = new Node(data);

    /* 
    	The next pointer of the new node should point to head of DLL.
    	i.e. the original first node new_node.next = head;
    	The previous pointer of new node should point to Null
    */
    new_node.prev = null;

    /* 
        Change the previous of the node where the head was initially pointing that 
        is the original first node
    */
    if (head != null) {
        head.prev = new_node;
    }

    // Head pointer should point to the new node
    head = new_node;
}

2. Insertion at the End of Doubly Linked Lists

The next pointer of the last node of the DLL points to Null. To insert a new node at the last position of the DLL, three important points need to be taken into consideration:

1. The next pointer of the new node should point to the Null.
    
2. The previous pointer of the new node should point to the old last node.
    
3. The next pointer of the old last node should point to the new last node.
    

Also, there may be a case where the DLL is initially empty. In that case, the newly created node will become both the first and the last node of the doubly linked list.

The code for the insertion of a new node as the last node in Java is given below:

// To insert a node at the end of a Doubly Linked List
public void insertAtLast(int data) {
    // Creating a new node with the given data
    Node newNode = new Node(data);

    // A temporary pointer that will be used for traversing DLL
    Node temp = head;

    // Making the next of newNode as Null
    newNode.next = null;

    /* 
    	If DLL is empty then this node will be both the first as
     	well as the last node
    */
    if (head == null) {
        newNode.prev = null;
        head = newNode;
        return;
    }

    /* 
    	If DLL is not empty, then traverse till the end of DLL. Make
    	the next pointer of the original last node point to the new
    	last node and the previous of the last node to the original 
    	last node
    */

    while (temp.next != null) {
        temp = temp.next;
    } // Now temp points to the original last node

    // Illustarted by Blue color in the diagram
    temp.next = newNode;
    // Illstrated by orange color in the diagram
    newNode.prev = temp;
}

3. Insertion after a given Node

There may be cases wherein a record or data is to be inserted after a given record or data. If the data is stored in a Linked List, the insertion after a given node operation in Linked List is used for such cases.

For inserting a new node after a given node, the following points need to be under consideration:

1. The records next to the previous node should now be linked to the new node to be inserted.
    
2. The previous node’s next pointer should be linked to the new node, and the new node’s previous pointer should be linked to the previous node.
    

The code for insertion of a new node after a given previous node in Java is given below.

public void insertAfter(Node prevNode, int data) {
    // if the previous node is null
    if (prevNode == null) {
        System.out.println("The given previous node cannot be null");
        return;
    }

    // Create a new node with the given data
    Node newNode = new Node(data);

    /* 	
    	The next pointer of this node should point to
    	the next of prevNode
    */
    newNode.next = prevNode.next;

    // The next pointer of prevNode should point to the newNode
    prevNode.next = newNode;

    /* 
    	The previous pointer of newNode should point to the
    	prevNode
    */
    newNode.prev = prevNode;

    // Change previous of newNode's next node 
    if (newNode.next != null)
        newNode.next.prev = newNode;
}

Deletion from a Doubly Linked Lists

There are three cases for deletion of a node in a doubly-linked list:

1. Delete the First Node of Doubly Linked List

To delete the first node of doubly linked list, you need to follow the below steps.

• Check if the head node is NULL, then there is nothing to delete. In this case, deletion is not applicable.
   
• If the list is not empty, point the head pointer to the second node.
   
• After updating the head pointer, set the “prev” pointer of the new head node to “NULL”.
   
• Now you can delete the first node.

2. Deletion of the Inner Node

You need to follow the below steps if you want to delete the inner node.

• Check if the head node is NULL. If NULL, then there is nothing to delete.
   
• Traverse the list until you reach the node to be deleted.
   
• Update the pointers of its adjacent nodes. Set the “next” pointer of the previous node to the next node, and set the “prev” pointer to the next node to the previous node.
   
• After updating pointers, you can delete the selected node.

3. Delete the Last Node of Doubly Linked List

Follow the below steps to delete the last node:

• Check if the head is NULL. If NULL, then there is nothing to delete.
   
• Start from the head and traverse the list until you reach the last node.
   
• Update the “next” pointer of its previous node to NULL. This will remove the connectivity to the last node.
   
• After updating the pointers, you can delete the last node.
   

The Java program for the deletion of a node in a doubly-linked list is given below:

/*	
	A utility function to delete a node of 
	a doubly linked list. The function takes the pointer 
	of the node to be deleted
*/
void deleteNode(Node ptr) {
    // Base case where the List is empty
    if (head == null || ptr == null) {
        System.out.println("The List is empty");
        return;
    }

    /* 	
    	When the node to be deleted is the 
    	head node
    */
    if (ptr == head) {
        // The head pointer will now point to the next node 
        head = ptr.next;
        /* 
        	Since the head node is to be deleted, then the previous of
        	the new head node has to be null
        */
        if (head != null)
            head.prev = null;

    }

    // If node to be deleted is not the last node
    if (ptr.next != null) {
        ptr.next.prev = ptr.prev;
    }

    // If node to be deleted is not the first node
    if (ptr.prev != null) {
        ptr.prev.next = ptr.next;
    }
}

So now you have a clear understanding of the Doubly Linked list and the various operations that can be performed on it. Below is the complete working program to test the above functions.

Traversal/Printing a Doubly Linked Lists

The Linked Lists is traversed using a temporary pointer that initially points to the head of the linked list. The temporary pointer is incremented, and the contents of the Doubly Linked List are printed.

Following is the code to print a doubly-linked list in Java.

/* 
	A utility function to print the contents of 
	a doubly linked list. The function takes the head
	pointer of the linked list
*/
public void printLinkedList(Node head) {
    if (head == null) {
        System.out.println("The List is empty");
        return;
    }
    // A temporary node that will be used for traversal
    Node temp = head;

    System.out.println("Traversal of Linked List");

    // Traverse the DLL by incrementing the pointer
    while (temp != null) {
        System.out.println(temp.data + " --> ");
        temp = temp.next;
    }

}

Doubly Linked List Complexity

Complexity depends on various operations. Below is the time complexity for common operations.

• Insertion: The complexity of insertion at the beginning and at the end is O(1). The complexity of insertion at a specific position is O(n), where n is the number of elements.
• Deletion: The complexity of deletion of the first node and of the last node is O(1). The complexity of deletion at a specific position is O(n), where n is the number of elements.
• Searching: The complexity of searching a specific node is O(n). Where n is the number of elements.

Doubly Linked List Applications

Let's now discuss some applications of a doubly linked list.

• A doubly linked list is used in navigation systems where both the traversal, forward and backwards are required.
   
• Doubly linked lists are used in applications like image editors, paint, and text editors to implement undo/redo functionality.
   
• Caches, such as the least recently used cache, uses doubly linked lists to manage recently used items.
   
• Doubly linked lists are used to implement music players. By using this, users can add or remove songs and perform operations like repeating and shuffling songs.
   
• Doubly linked lists are used in web browsers to maintain the history of visited web pages.

Advantages of Doubly Linked List

Following are the main advantages of Doubly Linked Lists:

1. A DLL can be traversed in both forward and reverse directions
    
2. A new node can be inserted before a given node quite easily by just changing the pointers
    
3. The complete Linked List need not be traversed for deletion operation as in Singly Linked List
    
4. While it uses more memory due to the extra backward pointers, they can be more memory-efficient for certain operations than alternative data structures like dynamic arrays

Disadvantages of Doubly Linked List

Following are the main disadvantages of Doubly Linked Lists:-

1. Additional memory space is required to store the previous pointer and the next pointer and the data to be stored
    
2. All the manipulation operations require both the previous and next pointers to be manipulated, imposing operational overhead
    
3. Despite its versatility, it tends to have slower traversal times than arrays, dynamic arrays, or singly linked lists, particularly when iterating through large collections of data
    
4. Each node in a doubly linked list carries the overhead of maintaining two-pointers, which can be a concern in memory-constrained environments

Applications of Doubly Linked List

• Dynamic memory allocation: Doubly linked lists allow for efficient memory allocation and deallocation, enabling dynamic data structures in applications like memory management systems.
• Undo functionality: Doubly linked lists are used in applications where an undo operation is required, such as text editors or graphic design software, allowing users to revert actions.
• Cache implementation: Doubly linked lists are utilized in cache implementation, where frequent access to recently used data is required for faster retrieval.
• Navigation systems: Doubly linked lists are employed in navigation systems like web browsers to keep track of visited pages, facilitating backward and forward navigation.
• Polynomial manipulation: Doubly linked lists are used in polynomial manipulation algorithms, such as adding, subtracting, multiplying, and dividing polynomials in mathematical software.

Frequently Asked Questions

What is difference between singly and doubly linked list?

A singly linked list consists of nodes where each node points to the next, allowing unidirectional traversal. In contrast, a doubly linked list has nodes pointing to both the next and previous nodes, enabling bidirectional traversal but requiring more memory.

Where is doubly linked list used?

Doubly linked lists find application in scenarios demanding bidirectional navigation, like undo mechanisms in software, facilitating efficient backward and forward traversal. They are also useful in caching and playlist management in applications like music players.

What is doubly circular linked list in data structure?

A doubly circular linked list is a variation of a doubly linked list where the last node points back to the first node, creating a circular structure. This allows traversal from any node in both forward and backward directions.

Conclusion

This blog clearly explained the Doubly Linked Lists, advantages and disadvantages of linked list, and various manipulation techniques were discussed and implemented in Java Programming Language.

It is an important topic, and questions related to DLL are frequently asked in almost all the major companies. It would be best if you practiced questions related to the topic to better understand the concepts studied. While this is one of the most important topics, there are other important topics as well.

Recommended Readings -

• Multithreading in Python
• Reverse a String in C
• Memory Hierarchy
   

You can also consider our Online Coding Courses such as the DSA in Python, C++ DSA Course, DSA in Java Course to give your career an edge over others.

Keep Learning and Keep Exploring!!