You will often deal with data structures, and among them, the Linked List plays a crucial role. Unlike arrays, linked lists allow dynamic memory allocation, efficient insertions, and deletions. Today, we’ll focus on the Doubly Linked List (DLL).

A doubly linked list is a linear data structure where each node contains three parts:

Data – the actual value.
Previous pointer – a reference to the previous node.
Next pointer – a reference to the next node.

This allows traversal in both directions, making it more flexible compared to a singly linked list.

Constructor

Let’s first define the Node class and initialize our doubly linked list.

public class DoublyLinkedList {
    // Declare head of the doubly linked list.
    private Node head;
    // Declare tail of the doubly linked list.
    private Node tail;
    // Declare length of the doubly linked list.
    private int length;

    // Constructor to create a new doubly linked list with a single node.
    public DoublyLinkedList(int value) {
        // Create a new node with the given value.
        Node newNode = new Node(value);
        // Set the head and tail of the list to the new node.
        head = newNode;
        tail = newNode;
        // Set the length of the list to 1.
        length = 1;
    }

    public Node getHead() {
        return head;
    }
    public Node getTail() {
        return tail;
    }
    public int getLength() {
        return length;
    }

    // Nested class for the nodes of the doubly linked list.
    class Node {
        // Declare integer value of the node.
        int value;
        // Declare reference to the next node.
        Node next;
        // Declare reference to the previous node.
        Node prev;

        // Constructor to create a new node with a given value.
        Node(int value) {
            this.value = value;
        }
    }
}

The DoublyLinkedList class has three private member variables:

head: a reference to the first node in the list.
tail: a reference to the last node in the list.
length: an integer that represents the number of nodes in the list.

The DoublyLinkedList class also has a nested class Node that represents a node in the doubly linked list. Each Node object has three member variables:

value: an integer value that represents the data stored in the node.
next: a reference to the next node in the list.
prev: a reference to the previous node in the list.

The Node class has a constructor that takes an integer value and sets the value member variable to that value.

The DoublyLinkedList class has a constructor that takes an integer value and creates a new doubly linked list with a single node. The constructor creates a new Node object with the given value, sets the head and tail member variables to the new node, and sets the length member variable to 1.

Append

Now, we want to add a new node to the end of our DLL(Doubly Linked List). Let’s think, we already have a give doubly linked list and we want to add a node 4 to the end of our DLL.

Now to append the new node 4 to the tail of the DLL, tail will point to the node 4 and 4 will need to arrow back to 7.

Then we have tail point to this new node like this and adds that into our double linked list.

public void append(int value) {
        // Create a new node with the given value.
        Node newNode = new Node(value);
        if (length == 0) {
            // If the list is empty, set both the head and tail to the new node.
            head = newNode;
        } else {
            // Otherwise, add the new node to the end of the list by updating the `next` 
            // and `prev` fields of the relevant nodes.
            // Set the `next` field of the current tail node to the new node.
            tail.next = newNode;
            // Set the `prev` field of the new node to the current tail node.
            newNode.prev = tail;
            // Set the `tail` member variable to the new node.
        }
        tail = newNode;
        // Increment the `length` member variable by 1 to indicate that the list has one more node.
        length++;
    }

The append method adds a new node to the end of the list with the given integer value.

The method creates a new Node object with the given value, and then checks if the length of the list is 0. If the length is 0, the new node is both the head and the tail of the list, so the method sets the head and tail member variables to the new node.

If the length is not 0, the new node is added to the end of the list by setting the next field of the current tail node to the new node, and setting the prev field of the new node to the current tail node. Then, the method sets the tail member variable to the new node.

Finally, the method increments the length member variable by 1 to indicate that the list has one more node.

Remove Last

The remove last operation remove and returns the last node of the list. Let’s take a look of this doubly Linked List (DDL).

Since we need to returning the last node, we will need a variable that is pointing to it that will be temp.

Then we can say that tail = tail.prev and that moves tail pointing to previous node.

Then, we make the next pointer of tail node null, tail.next = null and that breaks it off like that

Then, temp.prev = null and that will break the temp from the list and then return temp.

public Node removeLast() {
        // If the list is empty, return null.
        if(length == 0) return null;
        // Create a new node `temp` to hold the value of the last node.
        Node temp = tail;
        // If the list contains only one node, set both `head` and `tail` to null.
        if (length == 1) {
            head = null;
            tail = null;
        } else {
            // Otherwise, update the `tail` and `prev` fields of the second-to-last node
            // and the `next` and `prev` fields of the last node.
            // Set the `tail` to the previous node of the current tail.
            tail = tail.prev;
            // Set the `next` field of the new tail to `null`.
            tail.next = null;
            // Set the `prev` field of `temp` to `null`.
            temp.prev = null;
        }
        // Decrement the `length` by 1 to indicate that the list has one less node.
        length--;
        // Return the `temp` node, which holds the value of the removed last node.
        return temp;
    }

The removeLast method removes and returns the last node of the list.

The method first checks if the list is empty by testing if length is 0. If the list is empty, the method returns null immediately.

If the list is not empty, the method creates a new Node variable temp to hold a reference to the last node of the list. Then, the method checks if the length of the list is 1. If the length is 1, the list becomes empty after removing the last node, so the method sets both head and tail to null. Otherwise, the method removes the last node from the list by updating the tail and prev fields of the second-to-last node and the next and prev fields of the last node. Specifically, the method sets tail to the previous node of the current tail, sets the next field of the new tail to null, and sets the prev field of temp to null.

Finally, the method decrements length by 1 and returns the temp node, which points to the removed last node.

Prepend

Now we are going to add a new node at the begging of the doubly linked list(DLL).

Next pointer to the new node 4 should point to the first node of the list. In order to do that, we will set that equal to that head pointer.

So then we’ll have that previous pointer from the first node point back to the new node, head.prev = new node.

Then we will move the head node point to the new node and that adds that into our doubly linked list.

public void prepend(int value) {
        // Create a new node with the given value.
        Node newNode = new Node(value);

        // If the list is empty, set both head and tail to the new node.
        if(length == 0) {
            head = newNode;
            tail = newNode;
        }
        // If the list is not empty, insert the new node at the head of the list.
        else {
            // Set the next field of the new node to point to the current head.
            newNode.next = head;
            // Set the prev field of the current head to point to the new node.
            head.prev = newNode;
            // Set the head of the list to be the new node.
            head = newNode;
        }
        // Increment the length of the list.
        length++;
    }

The prepend method adds a new node containing the given value to the head of the doubly linked list.

Here's how it works:

A new node is created with the given value using the Node newNode = new Node(value) statement.
If the list is empty (i.e., length == 0), the new node becomes both the head and tail of the list using the statements head = newNode; and tail = newNode;.
If the list is not empty, the newNode is inserted at the head of the list, before the existing head node, using the following steps:

Set the next field of the newNode to point to the current head node: newNode.next \= head;
Set the prev field of the current head node to point to the newNode: head.prev = newNode;
Set the head of the list to be the newNode: head = newNode;

Finally, the length of the list is incremented by 1: length++;

Remove First

The first thing we will take a temp variable that will point to the head of the node.

Then we will do is move that head pointer over one.

Then we will make null the previous pointer of the head node which breaks the connection.

After that we make temp.next equal to null which break the node from the list.

Then we will return temp, which return the pointer to that node that we just removed.

public Node removeFirst() {
        // If the list is empty, return null
        if(length == 0) return null;

        // Get the first node
        Node temp = head;

        if(length == 1) { // If there is only one node in the list
            head = null;
            tail = null;
        } else { // If there are more than one nodes in the list
            // Set the head to the next node
            head = head.next;
            // Set the previous pointer of the new head to null
            head.prev = null;
            // Set the next pointer of the removed node to null
            temp.next = null;
        }

        // Decrease the length of the list
        length--;

        // Return the removed node
        return temp;
    }

The removeFirst method removes the first node of the list and returns it.

The method first checks if the list is empty (if length == 0), and if so, it immediately returns null since there is no node to remove.

If the list has only one node (if length == 1), then both head and tail are set to null, effectively emptying the list.

If the list has more than one node, the first node (which is currently head) is removed by doing the following:

head is set to the second node in the list (head.next).
The prev reference of the new head node is set to null.
The next reference of the removed node (temp) is set to null.

Finally, the length of the list is decremented, and the removed node (temp) is returned.

Get

To get a node by index, we can make a loop on the list like single linked list and iterate until index and then return the node.

If we want to get the item on index 1, we start with head and move through the list until we get our node. Then we can return the pointer of the node.

What if we want to get this node. Starting from head is not the efficient way to do that, since the node is closer to the tail than the head.

So, it’s going to be more efficient to start at the tail and go the other way.

public Node get(int index) {
    // check if the index is out of bounds, return null if true
    if (index < 0 || index >= length) return null;

    // initialize a temporary node with the value of the head
    Node temp = head;

    // if the index is in the first half of the list
    if (index < length/2) {

        // iterate through the list from the head to the index
        for (int i = 0; i < index; i++) {
            temp = temp.next;
        }
    } else {
        // if the index is in the second half of the list
        // initialize the temporary node with the value of the tail
        temp = tail;

        // iterate through the list from the tail to the index
        for (int i = length - 1; i > index; i--) {
            temp = temp.prev;
        }
    }

    // return the node at the given index
    return temp;
}

The get method is used to retrieve the node at a given index in the list.

The method takes an integer index as input, representing the index of the node to retrieve. The first thing the method does is check if the given index is out of range (i.e. less than zero or greater than or equal to the length of the list), in which case it returns null.

Next, it initializes a temp node variable to point to the head node of the list. The method then checks if the given index is less than half the length of the list. If it is, the method iterates through the list from the head node to find the node at the given index. The for loop starts at 0 and iterates up to index - 1, setting temp to the next node in each iteration.

If the given index is greater than or equal to half the length of the list, the method instead initializes temp to point to the tail node of the list. The for loop starts at the end of the list (i.e. length - 1) and iterates down to index + 1, setting temp to the previous node in each iteration.

Finally, the method returns the temp node variable, which should be pointing to the node at the given index in the list.

Set

If we are going to change the value 3 to 4, we’ll just say temp.value = 4

public boolean set(int index, int value) {

    // Get the node at the specified index
    Node temp = get(index);

    // If the node exists, set its value to the given value and return true
    if(temp != null) {
        temp.value = value;
        return true;
    }

    // If the node does not exist, return false
    return false;
}

The set() method sets the value of the node at the specified index in the doubly linked list to the given value. It takes two parameters: the index of the node to be set, and the value to set it to.

First, it calls the get() method to retrieve the node at the specified index. If the index is out of bounds, get() returns null, which means the set() method cannot proceed and returns false.

If the retrieved node is not null, the value field of the node is updated with the given value. Then, the method returns true to indicate that the value was successfully updated.

Insert

Here we are going to insert a new node with a particular value at particular index and then we’ll return a boolean. Let say we are going to insert 4 into the list.

If we add this at the front, we will just run perpend method.

If we add this to end of the list, we will just run append method.

Now let’s look at adding at item somewhere at the middle.

In order to do that, we are going to need couple of variables. Let’s say after and before.

So we are going to insert this new node in between before and after.

So, lets create this three items starting with creation of new node 4. Now assign before = get(index - 1) and after = before.next.

Now we need to redirect these 4 arrows just like this.

And that adds that into our doubly linked list.

public boolean insert(int index, int value) {

        // Return false if the index is out of range
        if(index < 0 || index > length) return false;

        // If index is 0, prepend the new value to the list
        if(index == 0) {
            prepend(value);
            return true;
        }

        // If index is equal to length, append the new value to the list
        if(index == length) {
            append(value);
            return true;
        }

        // Otherwise, create a new node with the given value
        Node newNode = new Node(value);

        // Get the node before the specified index
        Node before = get(index - 1);

        // Get the node after the specified index
        Node after = before.next;

        // Set the new node's previous and next pointers to the before and after nodes
        newNode.prev = before;
        newNode.next = after;

        // Update the next pointer of the before node and the previous pointer of the after node 
        // to point to the new node
        before.next = newNode;
        after.prev = newNode;

        // Increment the length of the linked list
        length++;

        // Return true to indicate that the value was successfully inserted
        return true;
    }

The insert() method inserts a new node with a given value at a specified index in the doubly linked list.
Here's a breakdown of the code:

First, the method checks if the specified index is valid. If it is not (i.e., if the index is less than 0 or greater than the length of the list), the method returns false.
If the index is 0, the method calls prepend() to add the new node to the beginning of the list and returns true.
If the index is equal to the length of the list, the method calls append() to add the new node to the end of the list and returns true.
If the index is valid and not at the beginning or end of the list, the method creates a new node with the given value and then finds the nodes before and after the specified index.
The method then updates the pointers of the before and after nodes to include the new node, and updates the pointers of the new node to include the before and after nodes.
Finally, the method increments the length of the list and returns true.

Remove

Lets remove an item from a particular position. First we need check if the index in less than zero or greater than or equal to length, we’re going to return null. And then if we try to remove an item at the index of zero, we’ll return removeFirst method and we’ve also written a method for removing an item on the other end. So, we’ll return removeLast if index = length – 1.

Now we are going to remove an item somewhere in the middle of the linked list. We’ll remove the item at the index 2.

So since we will be returning an item, we need a variable to point at this, and at the end of the method, we will return temp.

Now we are going to take 2 variables just like insert, before and after.

Now, when temp is removed, we could say that before.next = after and after.prev = before.

public Node remove(int index) {
    // Check if index is out of range.
    if(index < 0 || index >= length) return null;

    // If index is the first element, remove it.
    if(index == 0) return removeFirst();

    // If index is the last element, remove it.
    if(index == length - 1) return removeLast();

    // Get the node to remove.
    Node temp = get(index);

    // Update the prev and next pointers to remove the node from the linked list.
    temp.next.prev = temp.prev;
    temp.prev.next = temp.next;

    // Set the next and prev pointers of the removed node to null.
    temp.next = null;
    temp.prev = null;

    // Decrement the length of the linked list.
    length--;

    // Return the removed node.
    return temp;
}

The remove() method is used to remove a node at the specified index in the doubly linked list.

The method first checks if the index is valid, i.e., it is not less than zero or greater than or equal to the length of the linked list. If the index is not valid, it returns null.

If the index is zero, it removes the first node by calling the removeFirst() method and returns the removed node.

If the index is length - 1, it removes the last node by calling the removeLast() method and returns the removed node.

Otherwise, the method gets the node at the specified index by calling the get() method, and stores it in a temporary variable called temp.

Next, the method removes the temp node from the list by updating the prev and next pointers of its neighboring nodes.

Finally, it updates the length of the linked list and returns the removed node.

Pros and Cons of Doubly Linked List

Pros

Can be traversed in both directions.
Efficient insertion and deletion at both ends.
Flexible compared to arrays (no fixed size).

Cons

Requires extra memory for prev pointers.
More complex to implement than singly linked lists.
Random access (like arrays) is slower (O(n)).

When to Use Doubly Linked List

When you need frequent insertions and deletions at both ends.
When bidirectional traversal is required.
Useful in implementing stacks, queues, and undo/redo functionality.

Time Complexity

Operation	Best Case	Worst Case	Explanation
Append	Ω(1)	O(1)	Uses `tail` reference, no traversal needed.
Prepend	Ω(1)	O(1)	Inserts directly at `head`.
Remove First	Ω(1)	O(1)	Updates `head` pointer.
Remove Last	Ω(1)	O(1)	Updates `tail` pointer.
Get (by index)	Ω(1) (if at head/tail)	O(n)	Traversal from head or tail depending on index.
Set (by index)	Ω(1) (if at head/tail)	O(n)	Needs traversal before updating node value.
Insert	Ω(1)	O(n)	Requires traversal to reach the position.
Remove	Ω(1)	O(n)	Requires traversal to locate the node.

GitHub Source Code

👉 Check out the complete source code and practice problems on my GitHub:
doubly-linked-list

Problems

👉 Check out the interview problems with solution and explanation

Key Takeaways

A Doubly Linked List (DLL) allows traversal in both directions (forward & backward).
Basic operations: Constructor, Append, Prepend, Remove First, Remove Last, Get, Set.
Time Complexity:
- Append / Prepend → O(1)
- Remove First / Remove Last → O(1)
- Get / Set → O(n)
Use cases: Implementing LRU cache, Undo/Redo functionality, and Browser history.
Great for interview preparation and building strong DSA fundamentals.

Conclusion

A doubly linked list is a fundamental data structure that forms the backbone of many complex systems like LRU caches, text editors, and navigation history. By learning its basic operations, visual structure, and time complexities, you’ll strengthen your problem-solving skills and gain confidence for coding interviews and real-world applications.

Keep practicing by solving problems on linked lists and gradually move towards advanced structures like trees and graphs. Remember, strong fundamentals in data structures make you a much better developer.

Double Linked List: Visuals Explanation, Code and Interview Preparation

Table of contents