Insert at End Tail Insert in DSA Typescript - Time & Space Complexity

Time Complexity: Insert at End Tail Insert

O(n)

Understanding Time Complexity

We want to understand how long it takes to add a new item at the end of a list.

How does the time needed change as the list grows bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

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

This code adds a new node with a given value at the end of a singly linked list.

Identify Repeating Operations

• Primary operation: The while loop that moves through each node until the last one.
• How many times: It runs once for each node in the list until it reaches the end.

How Execution Grows With Input

As the list gets longer, the time to find the end grows too.

Input Size (n)	Approx. Operations
10	About 10 steps to reach the end
100	About 100 steps to reach the end
1000	About 1000 steps to reach the end

Pattern observation: The steps grow directly with the number of nodes; doubling nodes doubles the steps.

Final Time Complexity

Time Complexity: O(n)

This means the time to insert at the end grows linearly with the list size.

Common Mistake

[X] Wrong: "Inserting at the end is always instant, no matter the list size."

[OK] Correct: Because we must walk through all nodes to find the end, the time grows with the list length.

Interview Connect

Knowing how insertion time grows helps you explain trade-offs in list designs and shows you understand linked list basics.

Self-Check

"What if we kept a pointer to the last node? How would the time complexity change?"

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