Insert at End of Circular Linked List in DSA Typescript - Time & Space Complexity

Time Complexity: Insert at End of Circular Linked List

O(n)

Understanding Time Complexity

We want to know how the time to insert a new node at the end of a circular linked list changes as the list grows.

How does the number of steps grow when the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

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

This code inserts a new node at the end of a circular linked list by traversing the list to find the last node.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that moves through each node to find the last node.
• How many times: It runs once for each node until it reaches the last node, so it runs n-1 times if there are n nodes.

How Execution Grows With Input

As the list grows, the time to find the last node grows linearly because we check each node once.

Input Size (n)	Approx. Operations
10	About 9 steps to find the end
100	About 99 steps to find the end
1000	About 999 steps to find the end

Pattern observation: The steps increase directly with the number of nodes, so doubling nodes doubles the steps.

Final Time Complexity

Time Complexity: O(n)

This means the time to insert grows in direct proportion to the number of nodes in the list.

Common Mistake

[X] Wrong: "Inserting at the end is always quick because we just add a node."

[OK] Correct: We must first find the last node by checking each node, which takes time proportional to the list size.

Interview Connect

Understanding this helps you explain how linked list operations scale and shows you can analyze simple loops clearly.

Self-Check

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

Practice

1. What happens when you insert a new node at the end of an empty circular linked list?

easy

A. The new node points to null, ending the list.

B. The new node points to itself, becoming the only node in the list.

C. The list remains empty because insertion is not possible.

D. The new node points to the head, but the list has multiple nodes.

Solution

1. Step 1: Understand empty circular linked list

   An empty circular linked list has no nodes, so inserting the first node means it must point to itself to maintain circularity.

2. Step 2: Insert new node and set its next pointer

   The new node's next pointer is set to itself, making it the only node and the head of the list.

3. Final Answer:

   The new node points to itself, becoming the only node in the list. -> Option B

4. Quick Check:

   Empty list insertion = node points to itself [OK]

Hint: First node in circular list points to itself [OK]

Common Mistakes:

• Setting next pointer to null instead of itself
• Assuming list remains empty after insertion
• Not updating head pointer to new node

2. Which of the following TypeScript code snippets correctly inserts a new node at the end of a circular linked list?

easy

A. newNode.next = head; head.next = newNode; tail = newNode;

B. newNode.next = null; tail.next = newNode; tail = newNode;

C. newNode.next = head; tail.next = newNode; tail = newNode;

D. newNode.next = tail; head.next = newNode; tail = newNode;

Solution

1. Step 1: Set new node's next to head

   In a circular linked list, the last node points to the head, so newNode.next must point to head.

2. Step 2: Update tail's next and tail pointer

   Tail's next is updated to newNode, and tail pointer moves to newNode to mark new end.

3. Final Answer:

   newNode.next = head; tail.next = newNode; tail = newNode; -> Option C

4. Quick Check:

   New node points to head, tail updated [OK]

Hint: New node's next always points to head in circular list [OK]

Common Mistakes:

• Setting newNode.next to null breaks circularity
• Updating head.next instead of tail.next
• Not moving tail pointer to new node

3. Given the circular linked list: 10 -> 20 -> 30 -> (back to 10), what is the list after inserting 40 at the end?

medium

A. 10 -> 20 -> 30 -> 40 -> 10

B. 40 -> 10 -> 20 -> 30 -> 40

C. 10 -> 20 -> 30 -> 40 -> null

D. 10 -> 20 -> 30 -> 10 -> 40

Solution

1. Step 1: Understand circular list structure

   Original list loops from 30 back to 10, so last node 30 points to head 10.

2. Step 2: Insert 40 at end and update pointers

   New node 40 points to head 10, old tail 30 points to 40, maintaining circularity.

3. Final Answer:

   10 -> 20 -> 30 -> 40 -> 10 -> Option A

4. Quick Check:

   New node added before head, tail points to new node [OK]

Hint: New tail points to head, list stays circular [OK]

Common Mistakes:

• Adding null at end breaks circularity
• Inserting new node at head instead of tail
• Incorrect pointer updates causing loops

4. Identify the error in this TypeScript code snippet for inserting at the end of a circular linked list:

function insertEnd(tail: Node | null, data: number): Node {
  const newNode = new Node(data);
  if (!tail) {
    newNode.next = null;
    return newNode;
  }
  newNode.next = tail.next;
  tail.next = newNode;
  return newNode;
}

medium

A. newNode.next should point to itself when list is empty

B. Returning newNode instead of tail breaks list reference

C. newNode.next should point to tail.next, not null when list is empty

D. tail.next should not be updated in insertion

Solution

1. Step 1: Check empty list insertion

   When tail is null (empty list), newNode.next should point to itself to maintain circularity, not null.

2. Step 2: Verify pointer updates for non-empty list

   For non-empty list, newNode.next = tail.next (head), tail.next = newNode is correct.

3. Final Answer:

   newNode.next should point to itself when list is empty -> Option A

4. Quick Check:

   Empty list node points to itself [OK]

Hint: Empty circular list node points to itself, not null [OK]

Common Mistakes:

• Setting newNode.next to null breaks circularity
• Returning newNode instead of updating tail reference
• Not updating tail.next pointer

5. You have a circular linked list with nodes 5 -> 15 -> 25 -> (back to 5). You want to insert 35 at the end and then insert 2 at the beginning. What is the correct final circular linked list?

hard

A. 35 -> 2 -> 5 -> 15 -> 25 -> 35

B. 5 -> 15 -> 25 -> 35 -> 2 -> 5

C. 2 -> 5 -> 15 -> 25 -> 35 -> 5

D. 2 -> 5 -> 15 -> 25 -> 35 -> 2

Solution

1. Step 1: Insert 35 at end

   After inserting 35, list is 5 -> 15 -> 25 -> 35 -> back to 5.

2. Step 2: Insert 2 at beginning

   Insert at beginning means new node 2 points to current head 5, tail's next updated to 2, making 2 the new head.

3. Step 3: Final circular list

   The list is 2 -> 5 -> 15 -> 25 -> 35 -> back to 2, maintaining circularity.

4. Final Answer:

   2 -> 5 -> 15 -> 25 -> 35 -> 2 -> Option D

5. Quick Check:

   New head inserted, tail points to new head [OK]

Hint: Tail's next always points to head in circular list [OK]

Common Mistakes:

• Not updating tail.next after inserting at beginning
• Inserting new node at end but not updating tail
• Breaking circular link by pointing to wrong node