Delete from End of Doubly Linked List in DSA Java

Mental Model

To remove the last item, find the tail and unlink it from the list so the second last becomes the new tail.

Analogy: Imagine a train with cars linked front and back. To remove the last car, you detach it from the second last car, making the second last car the new end.

head -> 1 ↔ 2 ↔ 3 ↔ 4 ↔ 5 ← tail
null ← 1 ↔ 2 ↔ 3 ↔ 4 ↔ 5 -> null

Dry Run Walkthrough

Input: list: 1 ↔ 2 ↔ 3 ↔ 4 ↔ 5, delete from end

Goal: Remove the last node (5) and update the list tail

Step 1: start at head and move to tail node 5

head -> 1 ↔ 2 ↔ 3 ↔ 4 ↔ [5↑] ← tail

Why: We need to find the last node to remove it

Step 2: unlink node 5 by setting node 4's next to null

head -> 1 ↔ 2 ↔ 3 ↔ [4↑] ← tail
null ← 1 ↔ 2 ↔ 3 ↔ 4 -> null

Why: Removing last node means second last node becomes new tail

Step 3: set node 5's prev to null to fully detach

head -> 1 ↔ 2 ↔ 3 ↔ 4 ← tail
5 (detached)

Why: Clean up pointers to avoid dangling links

Result:

head -> 1 ↔ 2 ↔ 3 ↔ 4 ← tail
null ← 1 ↔ 2 ↔ 3 ↔ 4 -> null

Annotated Code

DSA Java

public class DoublyLinkedList {
    static class Node {
        int data;
        Node prev, next;
        Node(int data) {
            this.data = data;
            this.prev = null;
            this.next = null;
        }
    }

    Node head, tail;

    public void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = tail = newNode;
            return;
        }
        tail.next = newNode;
        newNode.prev = tail;
        tail = newNode;
    }

    public void deleteFromEnd() {
        if (tail == null) return; // empty list
        if (head == tail) { // single node
            head = tail = null;
            return;
        }
        Node oldTail = tail;
        tail = tail.prev; // move tail back
        tail.next = null; // detach old tail from list
        oldTail.prev = null; // detach old tail's prev pointer
    }

    public void printList() {
        Node curr = head;
        while (curr != null) {
            System.out.print(curr.data);
            if (curr.next != null) System.out.print(" ↔ ");
            curr = curr.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        DoublyLinkedList dll = new DoublyLinkedList();
        dll.append(1);
        dll.append(2);
        dll.append(3);
        dll.append(4);
        dll.append(5);
        dll.deleteFromEnd();
        dll.printList();
    }
}

if (tail == null) return; // empty list

handle empty list by doing nothing

if (head == tail) { head = tail = null; return; }

handle single node by clearing head and tail

tail = tail.prev; // move tail back

move tail pointer to second last node

tail.next.prev = null; // detach old tail's prev pointer

remove backward link from old tail

tail.next = null; // detach old tail from list

remove forward link from new tail to old tail

Output

1 ↔ 2 ↔ 3 ↔ 4

Complexity Analysis

Time: O(n) because we traverse from head to tail if tail pointer is not maintained, but here tail pointer is maintained so O(1) to delete last node

Space: O(1) because no extra space is used, only pointers are updated

vs Alternative: Compared to singly linked list where deleting last node requires O(n) traversal, doubly linked list with tail pointer allows O(1) deletion from end

Edge Cases

empty list

deleteFromEnd does nothing, list remains empty

DSA Java

if (tail == null) return; // empty list

single node list

deleteFromEnd removes the only node, list becomes empty

DSA Java

if (head == tail) { head = tail = null; return; }

When to Use This Pattern

When you need to remove the last element quickly from a list, and you have both forward and backward links, use the doubly linked list delete from end pattern for O(1) removal.

Common Mistakes

Mistake: Not updating the tail pointer after deletion
Fix: Always move tail to tail.prev to keep tail correct

Mistake: Not detaching old tail's prev pointer causing dangling backward link
Fix: Set oldTail.prev = null after moving tail and detaching next pointer

Summary

Deletes the last node from a doubly linked list by updating tail and pointers.

Use when you want to remove the end element efficiently in a doubly linked list.

The key is to move tail back and detach the old tail's links to fully remove it.

Practice

1. What happens when you delete the last node from a doubly linked list that has multiple nodes?

easy

A. The second last node becomes the new tail and its next pointer is set to null.

B. The head pointer is set to null.

C. The list becomes circular.

D. The first node is deleted instead.

Solution

1. Step 1: Identify the last node and its previous node

   In a doubly linked list, the last node's previous node is the second last node.

2. Step 2: Update the second last node's next pointer

   Set the second last node's next pointer to null, making it the new tail.

3. Final Answer:

   The second last node becomes the new tail and its next pointer is set to null. -> Option A

4. Quick Check:

   Deleting last node updates tail's next to null [OK]

Hint: Tail's previous node next pointer becomes null after deletion [OK]

Common Mistakes:

• Setting head to null instead of updating tail
• Not updating the previous node's next pointer
• Deleting the first node by mistake

2. Which of the following Java code snippets correctly deletes the last node from a doubly linked list named dll?

easy

A. dll.tail.next = dll.tail.prev; dll.tail = null;

B. dll.head = dll.head.next; dll.head.prev = null;

C. dll.tail = dll.tail.prev; dll.tail.next = null;

D. dll.head.prev = dll.tail; dll.tail = dll.tail.next;

Solution

1. Step 1: Move tail pointer to previous node

   Set dll.tail to dll.tail.prev to remove last node reference.

2. Step 2: Set new tail's next pointer to null

   Update dll.tail.next to null to mark end of list.

3. Final Answer:

   dll.tail = dll.tail.prev; dll.tail.next = null; -> Option C

4. Quick Check:

   Correct tail update and next pointer null [OK]

Hint: Tail moves back, next pointer set to null [OK]

Common Mistakes:

• Updating head instead of tail
• Setting tail to null without updating pointers
• Confusing next and prev pointers

3. Consider the following Java code for deleting the last node from a doubly linked list:

class Node {
  int data;
  Node prev, next;
  Node(int d) { data = d; prev = next = null; }
}

class DoublyLinkedList {
  Node head, tail;

  void deleteFromEnd() {
    if (tail == null) return;
    if (head == tail) {
      head = tail = null;
      return;
    }
    tail = tail.prev;
    tail.next = null;
  }
}

DoublyLinkedList dll = new DoublyLinkedList();
dll.head = new Node(1);
Node second = new Node(2);
dll.head.next = second;
second.prev = dll.head;
dll.tail = second;
dll.deleteFromEnd();
System.out.println(dll.head.data + " -> " + (dll.head.next == null ? "null" : dll.head.next.data));

What is the output?

medium

A. 1 -> 2

B. null -> null

C. 2 -> null

D. 1 -> null

Solution

1. Step 1: Setup list with two nodes 1 and 2

   Head points to node 1, tail points to node 2, linked properly.

2. Step 2: Delete last node (node 2)

   Tail moves to node 1, tail.next set to null, removing node 2.

3. Final Answer:

   1 -> null -> Option D

4. Quick Check:

   After deletion, only node 1 remains with next null [OK]

Hint: After deleting tail, tail.prev.next is null [OK]

Common Mistakes:

• Printing old tail node data
• Not updating tail.next to null
• Confusing head and tail pointers

4. The following code attempts to delete the last node from a doubly linked list but causes a runtime error:

void deleteFromEnd() {
  if (tail == null) return;
  tail = tail.prev;
  tail.next = null;
}

What is the error and how to fix it?

medium

A. Compilation error due to missing semicolon; fix by adding semicolon.

B. NullPointerException when list has one node; fix by checking if tail.prev is null.

C. Logical error deleting head instead of tail; fix by updating head pointer.

D. No error; code works fine.

Solution

1. Step 1: Identify cause of NullPointerException

   If list has one node, tail.prev is null, so tail becomes null, then tail.next causes error.

2. Step 2: Fix by checking single node case

   Add condition: if head == tail, set head and tail to null before updating pointers.

3. Final Answer:

   NullPointerException when list has one node; fix by checking if tail.prev is null. -> Option B

4. Quick Check:

   Check single node case before pointer update [OK]

Hint: Check if tail.prev is null before accessing tail.next [OK]

Common Mistakes:

• Not handling single node list
• Assuming tail.prev always exists
• Ignoring null pointer exceptions

5. You have a doubly linked list with nodes: 10 <-> 20 <-> 30 <-> 40. After deleting the last node twice using the correct deleteFromEnd method, what is the final list?

hard

A. 10 <-> 20

B. 10 <-> 20 <-> 30

C. 20 <-> 30

D. 30 <-> 40

Solution

1. Step 1: Delete last node once

   Deleting last node 40 removes it; list becomes 10 <-> 20 <-> 30.

2. Step 2: Delete last node second time

   Deleting last node 30 removes it; list becomes 10 <-> 20.

3. Final Answer:

   10 <-> 20 -> Option A

4. Quick Check:

   Two deletions remove last two nodes [OK]

Hint: Each deleteFromEnd removes tail node [OK]

Common Mistakes:

• Deleting from head instead of tail
• Not updating tail pointer after deletion
• Confusing node values after deletion