Push Using Linked List Node in DSA Javascript - 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 item to 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 {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

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

  push(value) {
    const newNode = new Node(value);
    newNode.next = this.head;
    this.head = newNode;
  }
}
    

This code adds a new node at the start of the linked list by adjusting pointers.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

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

How Execution Grows With Input

Adding a node always takes the same steps, no matter how big the list is.

Input Size (n)	Approx. Operations
10	3 (create node, set next, update head)
100	3 (same steps, no change)
1000	3 (still the same fixed steps)

Pattern observation: The number of steps stays the same regardless of list size.

Final Time Complexity

Time Complexity: O(1)

This means adding a node at the start takes a constant amount of time no matter how big the list is.

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 stays constant.

Interview Connect

Knowing that pushing to the front of a linked list is fast and constant time shows you understand efficient data structure operations.

Self-Check

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

Practice

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

easy

A. Removes the last node from the list

B. Adds a new node at the beginning of 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: Compare with other operations

   Removing or searching nodes are different operations, not push.

3. Final Answer:

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

4. Quick Check:

   Push = Add at head [OK]

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

Common Mistakes:

• Confusing push with pop or delete
• Thinking push adds at the end
• Mixing push with search operation

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

easy

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

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

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

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

Solution

1. Step 1: Create new node and link it to current head

   We create a new node, set its next to current head, then update head to new node.

2. Step 2: Check each option

   let newNode = new Node(value); newNode.next = head; head = newNode; correctly does this. Others either reverse assignments or miss new keyword.

3. Final Answer:

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

4. Quick Check:

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

Hint: New node's next points to old head, then update head [OK]

Common Mistakes:

• Forgetting to use 'new' keyword
• Assigning head before setting newNode.next
• Mixing order of assignments

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

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

let head = null;

function push(value) {
  let newNode = new Node(value);
  newNode.next = head;
  head = newNode;
}

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

medium

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

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

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

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

Solution

1. Step 1: Trace push calls and list updates

   First push(10): head = 10 -> null
   Second push(20): head = 20 -> 10 -> null
   Third push(30): head = 30 -> 20 -> 10 -> null

2. Step 2: Confirm final linked list order

   New nodes are added at front, so list is 30 -> 20 -> 10 -> null.

3. Final Answer:

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

4. Quick Check:

   Last pushed is first in list [OK]

Hint: Last pushed node becomes new head [OK]

Common Mistakes:

• Assuming push adds at end
• Confusing order of nodes
• Ignoring that head updates each push

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

function push(value) {
  let newNode = Node(value);
  newNode.next = head;
  head = newNode;
}

medium

A. Missing 'new' keyword when creating newNode

B. Incorrect assignment of newNode.next

C. head should be assigned before newNode.next

D. Function should return the new head

Solution

1. Step 1: Check node creation syntax

   Node is a class; must use 'new' keyword to create instance. Missing here.

2. Step 2: Verify other assignments

   newNode.next = head and head = newNode are correct order and assignments.

3. Final Answer:

   Missing 'new' keyword when creating newNode -> Option A

4. Quick Check:

   Use 'new' to create class instance [OK]

Hint: Always use 'new' with class constructors [OK]

Common Mistakes:

• Forgetting 'new' causes runtime error
• Swapping assignment order
• Expecting push to return head

5. Given a linked list with nodes 5 -> 15 -> 25 -> null, what will be the list after pushing a new node with value 10 using the push function?

function push(value) {
  let newNode = new Node(value);
  newNode.next = head;
  head = newNode;
}

Assume head points to the first node (5).

medium

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

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

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

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

Solution

1. Step 1: Understand push adds node at front

   Push creates new node with value 10, sets its next to current head (5), then updates head to new node.

2. Step 2: Visualize new list order

   New head is 10, followed by old list 5 -> 15 -> 25 -> null, so final list is 10 -> 5 -> 15 -> 25 -> null.

3. Final Answer:

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

4. Quick Check:

   Push adds new node at front [OK]

Hint: Push inserts new node before current head [OK]

Common Mistakes:

• Appending new node at end instead of front
• Not updating head pointer
• Mixing node order after push