Push Using Linked List Node in DSA Typescript - Time & Space Complexity

Time Complexity: Push Using Linked List Node

O(1)

Understanding Time Complexity

We want to understand how long it takes to add a new node at the start of a linked list.

How does the time needed change as the list grows?

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 push(head: Node | null, value: number): Node {
  const newNode = new Node(value);
  newNode.next = head;
  return newNode;
}
    

This code adds a new node at the front of a linked list by creating it and linking it to the current head.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Creating a new node and updating pointers.
• How many times: This happens once per push call, no loops or recursion involved.

How Execution Grows With Input

Adding a node always takes the same steps regardless of list size.

Input Size (n)	Approx. Operations
10	3 (create node, set next, return)
100	3 (same steps, no extra work)
1000	3 (still the same fixed steps)

Pattern observation: The time stays the same no matter how big the list is.

Final Time Complexity

Time Complexity: O(1)

This means adding a node at the front takes a constant amount of time, no matter the list size.

Common Mistake

[X] Wrong: "Adding a node takes longer as the list grows because we have to move through the list."

[OK] Correct: We only change the head pointer and the new node's next pointer; we never traverse the list, so time does not grow with list size.

Interview Connect

Knowing that pushing to the front of a linked list is quick and constant time helps you explain efficient data structure operations clearly.

Self-Check

"What if we had to add a node at the end of the linked list instead? How would the time complexity change?"

Practice

1. What does the push operation do in a linked list when using nodes?

easy

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

B. Removes the last node from the list

C. Searches for a node with a specific value

D. Deletes the first node of the list

Solution

1. Step 1: Understand push operation in linked list

   The push operation adds a new node to the start (head) of the linked list.

2. Step 2: Effect of push on linked list

   The new node becomes the new head, pointing to the previous first node.

3. Final Answer:

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

4. Quick Check:

   Push means add at head = D [OK]

Hint: Push always adds node at the start of the list [OK]

Common Mistakes:

• Confusing push with pop (removal)
• Thinking push adds at the end
• Mixing push with search or delete

2. Which of the following is the correct TypeScript syntax to create a new node and push it to the front of a singly linked list?

easy

A. newNode = new Node(value); head = newNode.next;

B. const newNode = Node(value); head.next = newNode; head = newNode;

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

D. head = new Node(value); head.next = null;

Solution

1. Step 1: Create a new node with given value

   Use new Node(value) to create a node instance.

2. Step 2: Link new node to current head and update head

   Set newNode.next = head and then head = newNode to push at front.

3. Final Answer:

   const newNode = new Node(value); newNode.next = head; head = newNode; -> Option C

4. Quick Check:

   New node points to old head, head updated = A [OK]

Hint: New node next points to head, then head updated [OK]

Common Mistakes:

• Forgetting to link new node's next to old head
• Assigning head.next instead of newNode.next
• Not updating head to new node

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

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

let head: Node | null = null;

function push(value: number) {
  const newNode = new Node(value);
  newNode.next = head;
  head = newNode;
}

push(10);
push(20);
push(30);

medium

A. null -> 10 -> 20 -> 30

B. 10 -> 20 -> 30 -> null

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

D. 30 -> 20 -> 10 -> null

Solution

1. Step 1: Push 10 to empty list

   Head becomes node with value 10, next is null.

2. Step 2: Push 20 and then 30

   Each new node points to previous head, so order is 30 -> 20 -> 10 -> null.

3. Final Answer:

   30 -> 20 -> 10 -> null -> Option D

4. Quick Check:

   Last pushed is head = A [OK]

Hint: Last pushed node is always new head [OK]

Common Mistakes:

• Assuming push adds at tail
• Reading list in wrong order
• Confusing next pointers

4. Identify the error in this push function for a singly linked list:

function push(value: number) {
  const newNode = new Node(value);
  head.next = newNode;
  head = newNode;
}

medium

A. head might be null causing runtime error

B. head.next = newNode is missing

C. head is assigned before linking newNode

D. Node constructor is called incorrectly

Solution

1. Step 1: Check head usage before assignment

   The code uses head.next without checking if head is null.

2. Step 2: Consequence of head being null

   If list is empty (head null), accessing head.next causes runtime error.

3. Final Answer:

   head might be null causing runtime error -> Option A

4. Quick Check:

   Accessing head.next without null check = B [OK]

Hint: Always check if head is null before accessing head.next [OK]

Common Mistakes:

• Not checking for empty list before push
• Forgetting to set newNode.next
• Assigning head incorrectly

5. Given a linked list with nodes containing values [5, 15, 25] (5 is head), what will be the list after pushing 35 and then 45 using the push function?
Also, explain how the head changes after each push.

hard

A. 35 -> 45 -> 5 -> 15 -> 25 -> null; head moves to 35 then 45

B. 45 -> 35 -> 5 -> 15 -> 25 -> null; head moves to newest node each push

C. 5 -> 15 -> 25 -> 35 -> 45 -> null; head stays at 5

D. null; list is cleared after push

Solution

1. Step 1: Initial list and push 35

   Original head is 5. Push 35 creates new node 35 pointing to 5. Head updates to 35.

2. Step 2: Push 45 and update head

   Push 45 creates new node 45 pointing to 35. Head updates to 45. Final list: 45 -> 35 -> 5 -> 15 -> 25 -> null.

3. Final Answer:

   45 -> 35 -> 5 -> 15 -> 25 -> null; head moves to newest node each push -> Option B

4. Quick Check:

   Push adds at front, head updates = C [OK]

Hint: Head always points to last pushed node [OK]

Common Mistakes:

• Assuming push adds at tail
• Not updating head after push
• Confusing node order after pushes