Delete Node at End in DSA Python

Mental Model

To remove the last item, find the one before it and make it the new end by cutting off the last.

Analogy: Imagine a line of people holding hands. To remove the last person, the second last person lets go of their hand, so the last person leaves the line.

head -> 1 -> 2 -> 3 -> null

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> null, delete node at end

Goal: Remove the last node so the list ends at node 2

Step 1: start at head node 1

head -> [curr->1] -> 2 -> 3 -> null

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

Step 2: move curr to node 2

head -> 1 -> [curr->2] -> 3 -> null

Why: We move forward to find the node before the last node

Step 3: curr.next points to last node 3, so set curr.next to null to remove last node

head -> 1 -> 2 -> null

Why: Disconnect last node by making second last node the new end

Result:

head -> 1 -> 2 -> null

Annotated Code

DSA Python

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, val):
        new_node = Node(val)
        if not self.head:
            self.head = new_node
            return
        curr = self.head
        while curr.next:
            curr = curr.next
        curr.next = new_node

    def delete_at_end(self):
        if not self.head:
            return  # empty list, nothing to delete
        if not self.head.next:
            self.head = None  # only one node, delete it
            return
        curr = self.head
        while curr.next.next:
            curr = curr.next  # move to second last node
        curr.next = None  # remove last node

    def __str__(self):
        vals = []
        curr = self.head
        while curr:
            vals.append(str(curr.val))
            curr = curr.next
        return ' -> '.join(vals) + ' -> null'

# Driver code
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
print("Before deletion:", ll)
ll.delete_at_end()
print("After deletion:", ll)

if not self.head:

check if list is empty to avoid errors

if not self.head.next:

handle single node list by setting head to None

while curr.next.next:

move curr to second last node by checking next's next

curr.next = None

remove last node by disconnecting it

Output

Before deletion: 1 -> 2 -> 3 -> null

After deletion: 1 -> 2 -> null

Complexity Analysis

Time: O(n) because we must traverse the list to find the second last node

Space: O(1) because we only use a few pointers, no extra space grows with input

vs Alternative: Compared to deleting from start which is O(1), deleting at end requires traversal making it O(n)

Edge Cases

empty list

no deletion occurs, list remains empty

DSA Python

if not self.head:

single node list

head is set to None, list becomes empty

DSA Python

if not self.head.next:

When to Use This Pattern

When asked to remove the last item in a singly linked list, use traversal to find the second last node and disconnect the last.

Common Mistakes

Mistake: Trying to delete last node without checking if list is empty or has one node
Fix: Add checks for empty list and single node list before traversal

Mistake: Stopping traversal at last node instead of second last node
Fix: Traverse until curr.next.next is None to reach second last node

Summary

Deletes the last node from a singly linked list by disconnecting it.

Use when you need to remove the end element of a linked list.

Remember to find the second last node to safely remove the last node.