Insert at End Tail Insert in DSA Python

Mental Model

Add a new item at the very end of a chain by walking to the last item and linking the new one after it.

Analogy: Imagine a line of people holding hands. To add a new person at the end, you walk to the last person and hold their hand.

head -> 1 -> 2 -> 3 -> null
                 ↑
               tail

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> null, insert value 4 at end

Goal: Add the value 4 at the end of the list so it becomes 1 -> 2 -> 3 -> 4 -> null

Step 1: start at head node with value 1

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

Why: We begin at the start to find the end of the list

Step 2: move to next node with value 2

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

Why: We keep moving forward to reach the last node

Step 3: move to next node with value 3

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

Why: We continue until we find the node whose next is null

Step 4: create new node with value 4 and link it after node 3

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

Why: Linking new node at the end completes the insertion

Result:

head -> 1 -> 2 -> 3 -> 4 -> 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 insert_at_end(self, val):
        new_node = Node(val)  # create new node
        if not self.head:
            self.head = new_node  # empty list, new node is head
            return
        curr = self.head
        while curr.next:
            curr = curr.next  # move to last node
        curr.next = new_node  # link new node at end

    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.insert_at_end(1)
ll.insert_at_end(2)
ll.insert_at_end(3)
ll.insert_at_end(4)
print(ll)

new_node = Node(val) # create new node

create a new node to insert

if not self.head: self.head = new_node # empty list, new node is head return

handle empty list by setting head to new node

while curr.next: curr = curr.next # move to last node

advance curr until last node found

curr.next = new_node # link new node at end

link new node after last node

Output

1 -> 2 -> 3 -> 4 -> null

Complexity Analysis

Time: O(n) because we must traverse all nodes to reach the end

Space: O(1) because we only create one new node and use constant extra space

vs Alternative: Compared to inserting at the head which is O(1), tail insertion is slower because it requires traversal

Edge Cases

empty list

new node becomes the head directly

DSA Python

if not self.head:
    self.head = new_node  # empty list, new node is head

single element list

new node is linked after the single existing node

DSA Python

while curr.next:
    curr = curr.next  # move to last node

When to Use This Pattern

When you need to add an item at the end of a linked list, use tail insertion by walking to the last node and linking the new node.

Common Mistakes

Mistake: Not checking if the list is empty before traversal
Fix: Add a condition to set head to new node if list is empty before traversing

Mistake: Linking new node before reaching the last node
Fix: Traverse fully until curr.next is null before linking new node

Summary

Adds a new node at the end of a linked list by traversing to the last node and linking it.

Use when you want to keep the existing order and add new data at the tail.

The key is to find the last node whose next is null, then link the new node there.

Practice

1. What does the "Insert at End (Tail Insert)" operation do in a singly linked list?

easy

A. Adds a new node at the end of the list

B. Removes the last node from the list

C. Adds a new node at the beginning of the list

D. Deletes the first node of the list

Solution

1. Step 1: Understand the operation

   Insert at End means adding a new node after the last node in the list.

2. Step 2: Compare with other operations

   Other options describe removing or adding at the start, which is different.

3. Final Answer:

   Adds a new node at the end of the list -> Option A

4. Quick Check:

   Insert at End = Add node at end [OK]

Hint: Tail insert always adds node after the last one [OK]

Common Mistakes:

• Confusing insert at end with insert at beginning
• Thinking it removes nodes instead of adding
• Mixing up head and tail operations

2. Which of the following is the correct syntax to create a new node and insert it at the end of a singly linked list in Python?

easy

A. new_node = Node(data); new_node.next = head; head = new_node

B. new_node = Node(data); tail = new_node; new_node.next = tail

C. new_node = Node(data); head.next = new_node; head = new_node

D. new_node = Node(data); tail.next = new_node; tail = new_node

Solution

1. Step 1: Create new node and link it after tail

   We create new_node and set tail.next to it, then update tail to new_node.

2. Step 2: Check other options for correctness

   new_node = Node(data); new_node.next = head; head = new_node inserts at head, C wrongly updates head, D sets tail before linking.

3. Final Answer:

   new_node = Node(data); tail.next = new_node; tail = new_node -> Option D

4. Quick Check:

   Tail.next = new_node, tail = new_node [OK]

Hint: Tail insert updates tail.next then tail pointer [OK]

Common Mistakes:

• Assigning new_node.next before linking to tail
• Updating head instead of tail
• Not updating tail pointer after insertion

3. What will be the output linked list after executing this code?

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

head = Node(1)
tail = head

for value in [2, 3, 4]:
    new_node = Node(value)
    tail.next = new_node
    tail = new_node

# Print list
current = head
result = []
while current:
    result.append(current.data)
    current = current.next
print(result)

medium

A. [1, 2, 3, 4]

B. [4, 3, 2, 1]

C. [1, 2, 3]

D. [2, 3, 4]

Solution

1. Step 1: Build linked list by tail insertion

   Start with head=1, then add 2, 3, 4 at tail in order.

2. Step 2: Traverse and collect node data

   Traverse from head, collect [1, 2, 3, 4] in order.

3. Final Answer:

   [1, 2, 3, 4] -> Option A

4. Quick Check:

   Tail insert preserves order [OK]

Hint: Tail insert keeps order same as input list [OK]

Common Mistakes:

• Confusing order and reversing list
• Printing only last inserted nodes
• Not updating tail pointer correctly

4. Identify the error in this tail insert code snippet:

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

head = Node(10)
tail = head

new_node = Node(20)
new_node.next = tail
tail = new_node

medium

A. tail should be updated before assigning new_node.next

B. new_node.next should be None, not tail

C. head should be updated instead of tail

D. No error, code is correct

Solution

1. Step 1: Check linking of new_node

   new_node.next points to tail, which creates a cycle or wrong link.

2. Step 2: Correct linking for tail insert

   new_node.next should be None because it's new tail; tail.next should point to new_node.

3. Final Answer:

   new_node.next should be None, not tail -> Option B

4. Quick Check:

   New tail's next = None [OK]

Hint: New tail node's next must be None [OK]

Common Mistakes:

• Linking new_node.next to old tail
• Not updating tail.next to new_node
• Confusing head and tail pointers

5. Given a singly linked list with nodes containing values [5, 10, 15], write the sequence of steps to insert a new node with value 20 at the end, and then print the list. What will be the final printed output?

hard

A. [5, 10, 15]

B. [20, 5, 10, 15]

C. [5, 10, 15, 20]

D. [5, 10, 20, 15]

Solution

1. Step 1: Traverse to the last node (value 15)

   Start at head (5), move to 10, then 15 which is tail (next is None).

2. Step 2: Create new node with value 20 and link it

   Set last node's next to new node (20), new node's next is None.

3. Step 3: Traverse and print all nodes

   Traverse from head and collect values: 5, 10, 15, 20.

4. Final Answer:

   [5, 10, 15, 20] -> Option C

5. Quick Check:

   Tail insert adds node at end [OK]

Hint: Traverse to tail, link new node, print full list [OK]

Common Mistakes:

• Inserting new node in middle instead of end
• Not setting new node's next to None
• Forgetting to update last node's next pointer