Insert at End Tail Insert in DSA Javascript - 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.

function insertAtEnd(head, value) {
  let newNode = { data: value, next: null };
  if (!head) {
    return newNode;
  }
  let current = head;
  while (current.next) {
    current = current.next;
  }
  current.next = newNode;
  return head;
}
    

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

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• 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 the end is reached.

How Execution Grows With Input

As the list gets longer, the time to find the end grows in a straight line with the number of nodes.

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 increase 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 always takes the same time no matter the list size."

[OK] Correct: Without a direct pointer to the last node, we must walk through all nodes, so bigger lists take more time.

Interview Connect

Understanding this helps you explain how linked lists work and why keeping track of the last node can speed up insertions.

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 linked list?

easy

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

B. Removes the first node from the linked list

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

D. Deletes the last node from the linked list

Solution

1. Step 1: Understand the operation

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

2. Step 2: Compare with other operations

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

3. Final Answer:

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

4. Quick Check:

   Insert at End = Add node at tail [OK]

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

Common Mistakes:

• Confusing tail insert with head insert
• Thinking it removes nodes instead of adding
• Assuming it inserts in the middle

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 JavaScript?

easy

A. let newNode = { data: value }; newNode.next = head;

B. let newNode = { data: value, next: null }; tail.next = newNode; tail = newNode;

C. let newNode = new Node(value); newNode.next = head; head = newNode;

D. let newNode = { value: data, nextNode: null }; head.next = newNode;

Solution

1. Step 1: Identify correct node creation

   Node should have data and next properties; next set to null for tail.

2. Step 2: Insert at end

   Set current tail's next to newNode, then update tail to newNode.

3. Final Answer:

   let newNode = { data: value, next: null }; tail.next = newNode; tail = newNode; -> Option B

4. Quick Check:

   Correct node creation and tail update [OK]

Hint: Tail insert needs next=null and tail pointer update [OK]

Common Mistakes:

• Using wrong property names like nextNode
• Inserting at head instead of tail
• Not updating tail pointer

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

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }
  insertAtEnd(data) {
    const newNode = new Node(data);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
  }
}

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

let current = list.head;
let result = '';
while(current) {
  result += current.data + ' -> ';
  current = current.next;
}
result += 'null';
console.log(result);

medium

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

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

C. 5 -> 10 -> null

D. null

Solution

1. Step 1: Insert nodes at end

   Nodes 5, 10, 15 are inserted sequentially at the tail.

2. Step 2: Traverse and print list

   Traversal prints nodes in insertion order: 5 -> 10 -> 15 -> null.

3. Final Answer:

   5 -> 10 -> 15 -> null -> Option A

4. Quick Check:

   Tail insert preserves order [OK]

Hint: Tail insert keeps order; print from head to tail [OK]

Common Mistakes:

• Confusing head and tail order
• Missing last node in output
• Printing reversed list

4. Find the error in the following tail insert method and select the correct fix:

insertAtEnd(data) {
  const newNode = new Node(data);
  if (this.head === null) {
    this.head = newNode;
  } else {
    this.tail.next = newNode;
  }
  // Missing update of tail pointer
}

medium

A. Change 'this.head = newNode;' to 'this.tail = newNode;' in if block

B. Set 'newNode.next = this.tail;' before insertion

C. Remove the else block completely

D. Add 'this.tail = newNode;' after setting tail.next

Solution

1. Step 1: Identify missing tail update

   After inserting newNode at tail.next, tail pointer must update to newNode.

2. Step 2: Fix by adding tail update

   Add 'this.tail = newNode;' after 'this.tail.next = newNode;' to keep tail correct.

3. Final Answer:

   Add 'this.tail = newNode;' after setting tail.next -> Option D

4. Quick Check:

   Tail pointer must update after insertion [OK]

Hint: Always update tail pointer after inserting at end [OK]

Common Mistakes:

• Not updating tail pointer causes broken list
• Changing head instead of tail in else block
• Incorrectly setting newNode.next to tail

5. You have a singly linked list with nodes: 1 -> 2 -> 3 -> null and a tail pointer correctly pointing to node 3. You want to insert a new node with value 4 at the end. Which sequence of operations correctly updates the list and tail pointer?

hard

A. Create newNode(4), newNode.next = tail, tail = newNode

B. Create newNode(4), head.next = newNode, tail = newNode

C. Create newNode(4), tail.next = newNode, tail = newNode

D. Create newNode(4), tail = newNode, tail.next = null

Solution

1. Step 1: Create new node with value 4

   Initialize newNode with data=4 and next=null.

2. Step 2: Link newNode after current tail and update tail

   Set tail.next = newNode to link, then update tail = newNode to move tail pointer.

3. Final Answer:

   Create newNode(4), tail.next = newNode, tail = newNode -> Option C

4. Quick Check:

   Tail insert requires linking and tail update [OK]

Hint: Link new node after tail, then update tail pointer [OK]

Common Mistakes:

• Linking new node to head instead of tail
• Setting newNode.next to tail (wrong direction)
• Updating tail before linking new node