Insert at End Tail Insert in DSA Typescript

Mental Model

Add a new item at the very end of a chain by following the links until the last one.

Analogy: Imagine a line of people holding hands. To add a new person at the end, you walk down the line until you find the last person, then 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 -> [curr->1] -> 2 -> 3 -> null

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

Step 2: move curr to next node with value 2

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

Why: We keep moving forward to reach the last node

Step 3: move curr to next node with value 3

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

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

Step 4: curr.next is null, attach new node with value 4 here

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

Why: Adding new node at the end completes the insertion

Result:

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

Annotated Code

DSA Typescript

class Node {
  value: number;
  next: Node | null;
  constructor(value: number) {
    this.value = value;
    this.next = null;
  }
}

class LinkedList {
  head: Node | null;
  constructor() {
    this.head = null;
  }

  insertAtEnd(value: number): void {
    const newNode = new Node(value);
    if (this.head === null) {
      this.head = newNode; // empty list, new node is head
      return;
    }
    let curr = this.head;
    while (curr.next !== null) {
      curr = curr.next; // advance curr to next node until last
    }
    curr.next = newNode; // attach new node at end
  }

  printList(): void {
    let curr = this.head;
    let result = '';
    while (curr !== null) {
      result += curr.value + ' -> ';
      curr = curr.next;
    }
    result += 'null';
    console.log(result);
  }
}

// Driver code
const list = new LinkedList();
list.insertAtEnd(1);
list.insertAtEnd(2);
list.insertAtEnd(3);
list.insertAtEnd(4);
list.printList();

if (this.head === null) { this.head = newNode; // empty list, new node is head return; }

handle empty list by setting new node as head

while (curr.next !== null) { curr = curr.next; // advance curr to next node until last }

move curr forward until last node found

curr.next = newNode; // attach new node at end

link new node at the end of the list

Output

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

Complexity Analysis

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

Space: O(1) because we only create one new node and use a few pointers

vs Alternative: Compared to inserting at the head which is O(1), inserting at the end is slower because we must find the last node first

Edge Cases

empty list

new node becomes the head of the list

DSA Typescript

if (this.head === null) {
  this.head = newNode; // empty list, new node is head
  return;
}

single element list

new node is attached after the single existing node

DSA Typescript

while (curr.next !== null) {
  curr = curr.next; // advance curr to next node until last
}

When to Use This Pattern

When you need to add an item at the end of a linked list and only have a head pointer, use tail insertion by traversing to the last node.

Common Mistakes

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

Mistake: Stopping traversal too early and overwriting nodes
Fix: Traverse until curr.next is null, not curr itself

Summary

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

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

The key is to find the last node whose next pointer 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 beginning of the list

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

C. Deletes the last node 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

   Adding at the beginning or deleting nodes are different operations.

3. Final Answer:

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

4. Quick Check:

   Insert at End = Add node at tail [OK]

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

Common Mistakes:

• Confusing tail insert with head insert
• Thinking it deletes nodes
• Assuming it inserts in the middle

2. Which of the following is the correct TypeScript syntax to create a new node for tail insertion in a singly linked list?

easy

A. const newNode = new Node(value);

B. const newNode = Node(value);

C. let newNode = Node.create(value);

D. newNode = new Node();

Solution

1. Step 1: Recall TypeScript class instantiation

   To create an instance of a class, use the 'new' keyword with constructor.

2. Step 2: Check each option

   const newNode = new Node(value); uses 'new Node(value);' which is correct syntax.

3. Final Answer:

   const newNode = new Node(value); -> Option A

4. Quick Check:

   Use 'new' keyword to create class instance [OK]

Hint: Use 'new' keyword to create node instances [OK]

Common Mistakes:

• Omitting 'new' keyword
• Calling class like a function
• Using undefined methods like create()

3. Consider the following TypeScript code for inserting at the end of a singly linked list:

class Node {
  value: number;
  next: Node | null = null;
  constructor(value: number) { this.value = value; }
}

class LinkedList {
  head: Node | null = null;

  insertAtEnd(value: number) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      return;
    }
    let current = this.head;
    while (current.next) {
      current = current.next;
    }
    current.next = newNode;
  }
}

const list = new LinkedList();
list.insertAtEnd(5);
list.insertAtEnd(10);
list.insertAtEnd(15);

// What is the linked list after these insertions?

medium

A. 10 -> 5 -> 15 -> null

B. 15 -> 10 -> 5 -> null

C. 5 -> 15 -> 10 -> null

D. 5 -> 10 -> 15 -> null

Solution

1. Step 1: Insert 5 into empty list

   Since head is null, head becomes node with value 5.

2. Step 2: Insert 10 at end

   Traverse from head (5), next is null, so set next to new node 10.

3. Step 3: Insert 15 at end

   Traverse from head (5) to 10, next is null, set next to new node 15.

4. Final Answer:

   5 -> 10 -> 15 -> null -> Option D

5. Quick Check:

   Nodes added in order at tail [OK]

Hint: Tail insert keeps order of insertion [OK]

Common Mistakes:

• Assuming insertion at head
• Mixing node order
• Not updating next pointers correctly

4. The following TypeScript code attempts to insert a node at the end of a singly linked list but causes an error:

insertAtEnd(value: number) {
  const newNode = new Node(value);
  if (!this.head) {
    this.head = newNode;
  }
  let current = this.head;
  while (current.next) {
    current = current.next;
  }
  current.next = newNode;
}

What is the error in this code?

medium

A. It inserts the new node twice when the list is empty

B. It never updates the head pointer

C. It causes an infinite loop

D. It does not create a new node properly

Solution

1. Step 1: Analyze empty list case

   If head is null, head is set to newNode, but code continues to traverse and insert again.

2. Step 2: Identify double insertion

   After setting head, it still traverses and sets current.next = newNode, adding newNode twice.

3. Final Answer:

   It inserts the new node twice when the list is empty -> Option A

4. Quick Check:

   Missing return after head assignment causes double insert [OK]

Hint: Return immediately after setting head in empty list [OK]

Common Mistakes:

• Not returning after head assignment
• Assuming single insertion always
• Ignoring traversal logic

5. You want to optimize the tail insertion in a singly linked list to avoid traversing the entire list every time. Which modification will achieve this?

hard

A. Insert new nodes at the head instead of the tail

B. Use a doubly linked list instead of singly linked list

C. Keep a tail pointer that always points to the last node

D. Store the list length and use it to find the last node

Solution

1. Step 1: Understand traversal cost

   Without a tail pointer, inserting at end requires traversing all nodes, which is slow for long lists.

2. Step 2: Use tail pointer

   Maintaining a tail pointer lets you directly access the last node and insert in constant time.

3. Step 3: Evaluate other options

   Inserting at head changes order, doubly linked list adds complexity, length doesn't help find last node efficiently.

4. Final Answer:

   Keep a tail pointer that always points to the last node -> Option C

5. Quick Check:

   Tail pointer = O(1) insert at end [OK]

Hint: Tail pointer avoids full list traversal [OK]

Common Mistakes:

• Thinking length helps find last node
• Confusing head insertion with tail insertion
• Ignoring complexity of doubly linked list