Push Using Linked List Node in DSA Java - 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.

public class LinkedList {
    Node head;

    static class Node {
        int data;
        Node next;

        Node(int d) { data = d; next = null; }
    }

    public void push(int new_data) {
        Node new_node = new Node(new_data);
        new_node.next = head;
        head = new_node;
    }
}

This code adds a new node at the beginning of the linked list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

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

How Execution Grows With Input

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

Input Size (n)	Approx. Operations
10	3 steps (create node, set next, update head)
100	3 steps (same as above)
1000	3 steps (same as above)

Pattern observation: The time stays the same no matter how many nodes are in the list.

Final Time Complexity

Time Complexity: O(1)

This means adding a node at the start takes a constant amount of time regardless of 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; no traversal is needed.

Interview Connect

Knowing that push on a linked list is fast helps you design efficient data structures and answer questions confidently.

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. Deletes the first node of the list

B. Removes the last node from the list

C. Searches for a node with a specific value

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

Solution

1. Step 1: Understand push operation in linked list

   The push operation adds a new element to the start of the linked list by creating a new node and linking it before the current head.

2. Step 2: Compare with other operations

   Removing or searching nodes are different operations; push specifically adds at the front.

3. Final Answer:

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

4. Quick Check:

   Push = Add at start [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 syntax to create a new node and push it onto the linked list in Java?

easy

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

B. Node newNode = Node(data); newNode.next = head; head = newNode;

C. Node newNode = new Node(); newNode.data = data; head = newNode.next;

D. Node newNode = new Node(data); head = newNode.next; newNode = head;

Solution

1. Step 1: Create new node with data

   Use new Node(data) to create a node with the given data.

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:

   Node newNode = new Node(data); newNode.next = head; head = newNode; -> Option A

4. Quick Check:

   Correct syntax for push = Node newNode = new Node(data); newNode.next = head; head = newNode; [OK]

Hint: Use 'new Node(data)' and update next and head correctly [OK]

Common Mistakes:

• Forgetting 'new' keyword
• Assigning head before setting newNode.next
• Incorrect order of assignments

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

class Node {
  int data;
  Node next;
  Node(int d) { data = d; next = null; }
}

Node head = null;

// Push 10
Node newNode = new Node(10);
newNode.next = head;
head = newNode;

// Push 20
newNode = new Node(20);
newNode.next = head;
head = newNode;

// Push 30
newNode = new Node(30);
newNode.next = head;
head = newNode;

// Print list
Node temp = head;
while(temp != null) {
  System.out.print(temp.data + " -> ");
  temp = temp.next;
}
System.out.print("null");

medium

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

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

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

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

Solution

1. Step 1: Trace push operations

   First push 10: list is 10 -> null.
   Second push 20: new node 20 points to 10, list is 20 -> 10 -> null.
   Third push 30: new node 30 points to 20, list is 30 -> 20 -> 10 -> null.

2. Step 2: Print list

   Printing from head prints 30, then 20, then 10, then null.

3. Final Answer:

   30 -> 20 -> 10 -> null -> Option A

4. Quick Check:

   Push adds at front, last pushed is first [OK]

Hint: Last pushed node appears first in the list [OK]

Common Mistakes:

• Assuming push adds at end
• Confusing order of nodes after pushes
• Printing null at start instead of end

4. Identify the error in the following push method for a linked list and select the correct fix.

void push(int data) {
  Node newNode = new Node(data);
  newNode.next = null;
  head = newNode;
}

medium

A. Assign head = null before creating newNode

B. Set newNode.next = head before updating head

C. Remove newNode.next assignment completely

D. Use newNode.data = data instead of constructor

Solution

1. Step 1: Analyze current push method

   Currently, newNode.next is set to null, then head is set to newNode. This breaks the link to existing list.

2. Step 2: Correct linking for push

   To push correctly, newNode.next should point to current head before head is updated to newNode.

3. Final Answer:

   Set newNode.next = head before updating head -> Option B

4. Quick Check:

   Link newNode to old head before updating head [OK]

Hint: Always link new node to old head before changing head [OK]

Common Mistakes:

• Setting newNode.next to null breaks list
• Updating head before linking newNode.next
• Not linking new node to existing list

5. You have a linked list with nodes containing values 5 -> 15 -> 25 -> null. You want to push a new node with value 10 such that the list remains sorted in ascending order. Which code snippet correctly pushes the node to maintain sorted order?

hard

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

B. Node newNode = new Node(10);
newNode.next = null;
head.next = newNode;

C. Node newNode = new Node(10);
Node current = head;
while(current.next != null && current.next.data < 10) {
current = current.next;
}
newNode.next = current.next;
current.next = newNode;

D. Node newNode = new Node(10);
newNode.next = head.next;
head = newNode;

Solution

1. Step 1: Understand sorted push requirement

   To keep list sorted, find the correct position where new node's data fits between nodes.

2. Step 2: Traverse and insert node

   Traverse list until next node's data is greater or null, then insert newNode between current and current.next.

3. Final Answer:

   Node newNode = new Node(10); Node current = head; while(current.next != null && current.next.data < 10) { current = current.next; } newNode.next = current.next; current.next = newNode; -> Option C

4. Quick Check:

   Traverse to insert in sorted order [OK]

Hint: Traverse to find correct spot, then insert new node [OK]

Common Mistakes:

• Always pushing at head ignores sorting
• Not updating next pointers correctly
• Inserting at wrong position breaks order