Delete from End of Doubly Linked List in DSA Go

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 of connected cars. To remove the last car, you disconnect it from the second last car, leaving the rest of the train intact.

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 to node 4

Step 1: start at head node 1

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

Why: We begin traversal from the start to find the last node

Step 2: move to node 2

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

Why: Keep moving forward to reach the last node

Step 3: move to node 3

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

Why: Continue traversal towards the tail

Step 4: move to node 4

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

Why: Next node before the last, needed to update tail pointer

Step 5: move to node 5 (tail)

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

Why: Found the last node to delete

Step 6: unlink node 5 by setting node 4's next to null and update tail to node 4

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

Why: Removing last node and updating tail keeps list consistent

Result:

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

Annotated Code

DSA Go

package main

import "fmt"

type Node struct {
	value int
	next  *Node
	prev  *Node
}

type DoublyLinkedList struct {
	head *Node
	tail *Node
}

func (dll *DoublyLinkedList) Append(val int) {
	newNode := &Node{value: val}
	if dll.head == nil {
		dll.head = newNode
		dll.tail = newNode
		return
	}
	dll.tail.next = newNode
	newNode.prev = dll.tail
	dll.tail = newNode
}

func (dll *DoublyLinkedList) DeleteFromEnd() {
	if dll.tail == nil {
		return // empty list, nothing to delete
	}
	if dll.head == dll.tail {
		dll.head = nil
		dll.tail = nil
		return // single node deleted
	}
	prevNode := dll.tail.prev
	prevNode.next = nil // unlink last node
	dll.tail = prevNode // update tail
}

func (dll *DoublyLinkedList) PrintList() {
	curr := dll.head
	for curr != nil {
		fmt.Printf("%d", curr.value)
		if curr.next != nil {
			fmt.Print(" ↔ ")
		}
		curr = curr.next
	}
	fmt.Println()
}

func main() {
	dll := &DoublyLinkedList{}
	dll.Append(1)
	dll.Append(2)
	dll.Append(3)
	dll.Append(4)
	dll.Append(5)
	fmt.Print("Original list: ")
	dll.PrintList()
	dll.DeleteFromEnd()
	fmt.Print("After deleting from end: ")
	dll.PrintList()
}

if dll.tail == nil { return }

handle empty list by returning early

if dll.head == dll.tail { dll.head = nil; dll.tail = nil; return }

handle single node list by clearing head and tail

prevNode := dll.tail.prev

find node before tail to update pointers

prevNode.next = nil

unlink last node by removing next pointer

dll.tail = prevNode

update tail pointer to new last node

Output

Original list: 1 ↔ 2 ↔ 3 ↔ 4 ↔ 5

After deleting from end: 1 ↔ 2 ↔ 3 ↔ 4

Complexity Analysis

Time: O(1) because we directly access the tail and its previous node without traversal

Space: O(1) because no extra space is used besides a few pointers

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

Edge Cases

empty list

no deletion occurs, list remains empty

DSA Go

if dll.tail == nil { return }

single node list

node is deleted, list becomes empty

DSA Go

if dll.head == dll.tail { dll.head = nil; dll.tail = nil; return }

When to Use This Pattern

When you need to remove the last element quickly from a list, use a doubly linked list because it keeps a tail pointer and backward links for O(1) deletion.

Common Mistakes

Mistake: Trying to delete the last node by traversing from head instead of using tail pointer
Fix: Use the tail pointer directly to access and remove the last node in O(1) time

Mistake: Not updating the tail pointer after deletion
Fix: Always update the tail pointer to the previous node after unlinking the last node

Summary

Deletes the last node from a doubly linked list by unlinking it and updating the tail pointer.

Use when you want to remove the last element efficiently without traversing the whole list.

The key insight is that the tail pointer and backward links let you delete from the end in constant time.

Practice

1. What happens to the tail pointer when you delete the last node from a doubly linked list?

easy

A. The tail pointer becomes null immediately.

B. The tail pointer moves to the next node.

C. The tail pointer does not change.

D. The tail pointer moves to the previous node.

Solution

1. Step 1: Understand the tail pointer role

   The tail pointer points to the last node in the doubly linked list.

2. Step 2: Effect of deleting the last node

   When the last node is deleted, the tail pointer must move to the previous node to remain valid.

3. Final Answer:

   The tail pointer moves to the previous node. -> Option D

4. Quick Check:

   Tail moves backward after deletion [OK]

Hint: Tail always points to last node; update to previous on delete [OK]

Common Mistakes:

• Not updating tail pointer after deletion
• Setting tail to next node which is null
• Leaving tail pointer unchanged

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

easy

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

B. dll.tail = dll.tail.prev; dll.tail.next = nil

C. dll.head = dll.head.next; dll.head.prev = nil

D. dll.head = dll.tail; dll.tail = nil

Solution

1. Step 1: Identify correct pointer updates for tail deletion

   Deleting last node means tail moves to previous node and new tail's next is nil.

2. Step 2: Check code correctness

   dll.tail = dll.tail.prev; dll.tail.next = nil sets tail to previous node and sets tail.next to nil, which is correct.

3. Final Answer:

   dll.tail = dll.tail.prev; dll.tail.next = nil -> Option B

4. Quick Check:

   Tail moves back, next cleared [OK]

Hint: Tail moves to prev; set tail.next to nil [OK]

Common Mistakes:

• Moving tail forward instead of backward
• Not setting tail.next to nil
• Changing head pointer instead of tail

3. What is the output of the following Go code that deletes the last node from a doubly linked list?

package main
import "fmt"

type Node struct {
    data int
    prev *Node
    next *Node
;
}

type DoublyLinkedList struct {
    head *Node
    tail *Node
;
}

func (dll *DoublyLinkedList) DeleteFromEnd() {
    if dll.tail == nil {
        return
    }
    if dll.tail.prev == nil {
        dll.head = nil
        dll.tail = nil
        return
    }
    dll.tail = dll.tail.prev
    dll.tail.next = nil
}

func (dll *DoublyLinkedList) Print() {
    current := dll.head
    for current != nil {
        fmt.Print(current.data, " -> ")
        current = current.next
    }
    fmt.Println("null")
}

func main() {
    n1 := &Node{data: 1}
    n2 := &Node{data: 2}
    n3 := &Node{data: 3}
    n1.next = n2
    n2.prev = n1
    n2.next = n3
    n3.prev = n2
    dll := DoublyLinkedList{head: n1, tail: n3}
    dll.DeleteFromEnd()
    dll.Print()
}

medium

A. 1 -> 2 -> null

B. 1 -> 2 -> 3 -> null

C. 2 -> 3 -> null

D. null

Solution

1. Step 1: Initial list and deletion

   List is 1 -> 2 -> 3 -> null. DeleteFromEnd removes last node (3).

2. Step 2: After deletion

   Tail moves to node with data 2, tail.next set to nil. List becomes 1 -> 2 -> null.

3. Final Answer:

   1 -> 2 -> null -> Option A

4. Quick Check:

   Last node removed, tail updated [OK]

Hint: Deleting end removes last node, tail moves back [OK]

Common Mistakes:

• Not updating tail.next to nil causing dangling pointer
• Printing old list without deletion
• Confusing head and tail pointers

4. The following Go code attempts to delete the last node from a doubly linked list but causes a runtime panic. What is the error?

func (dll *DoublyLinkedList) DeleteFromEnd() {
    if dll.tail == nil {
        return
    }
    dll.tail = dll.tail.prev
    dll.tail.next = nil
}

medium

A. It should delete from the head, not the tail.

B. It incorrectly sets tail.next to nil before moving tail.

C. It does not handle the case when the list has only one node.

D. It should set head to nil instead of tail.

Solution

1. Step 1: Analyze edge case for single node list

   If list has one node, tail.prev is nil, so after tail = tail.prev, tail is nil.

2. Step 2: Cause of panic

   Next line tries to access tail.next but tail is nil, causing runtime panic.

3. Final Answer:

   It does not handle the case when the list has only one node. -> Option C

4. Quick Check:

   Missing single-node check causes nil pointer panic [OK]

Hint: Check for single-node list before updating tail [OK]

Common Mistakes:

• Not checking if tail.prev is nil before access
• Assuming list always has multiple nodes
• Ignoring head pointer update when list becomes empty

5. You have a doubly linked list with nodes: 10 <-> 20 <-> 30 <-> 40. After deleting the last node twice using the correct delete from end method, what will be the printed list?

hard

A. 10 -> 20 -> null

B. 10 -> 20 -> 30 -> null

C. 20 -> 30 -> null

D. 10 -> 30 -> null

Solution

1. Step 1: Initial list and first deletion

   List is 10 <-> 20 <-> 30 <-> 40. First deletion removes 40, list becomes 10 <-> 20 <-> 30.

2. Step 2: Second deletion

   Second deletion removes 30, list becomes 10 <-> 20.

3. Step 3: Print list

   Printing from head: 10 -> 20 -> null.

4. Final Answer:

   10 -> 20 -> null -> Option A

5. Quick Check:

   Two deletions remove last two nodes [OK]

Hint: Each delete removes last node, tail moves back [OK]

Common Mistakes:

• Deleting only once instead of twice
• Confusing node values after deletion
• Not updating tail pointer correctly