Push Using Linked List Node in DSA C++ - Execution Trace

Concept Flow - Push Using Linked List Node

Create new node with data

↓

Set new node's next to current head

↓

Update head to new node

↓

Done

This flow shows how a new node is created and added at the start of the linked list by adjusting pointers.

Execution Sample

DSA C++

struct Node {
  int data;
  Node* next;
};

void push(Node*& head, int val) {
  Node* newNode = new Node{val, head};
  head = newNode;
}

This code creates a new node with the given value and inserts it at the beginning of the linked list.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Start with empty list	None	head = nullptr	head -> null
2	Create new node with data=10	Node(10)	newNode->data=10, newNode->next=nullptr	head -> null
3	Set newNode->next = head (nullptr)	Node(10)	newNode->next = nullptr	head -> null
4	Update head = newNode	Node(10)	head points to newNode	head -> 10 -> null
5	Create new node with data=20	Node(10)	newNode->data=20, newNode->next=nullptr	head -> 10 -> null
6	Set newNode->next = head (Node(10))	Node(20) -> Node(10)	newNode->next = head	head -> 10 -> null
7	Update head = newNode	Node(20) -> Node(10)	head points to newNode	head -> 20 -> 10 -> null
8	Create new node with data=30	Node(20) -> Node(10)	newNode->data=30, newNode->next=nullptr	head -> 20 -> 10 -> null
9	Set newNode->next = head (Node(20))	Node(30) -> Node(20) -> Node(10)	newNode->next = head	head -> 20 -> 10 -> null
10	Update head = newNode	Node(30) -> Node(20) -> Node(10)	head points to newNode	head -> 30 -> 20 -> 10 -> null
11	End of push operations	Node(30) -> Node(20) -> Node(10)	head points to Node(30)	head -> 30 -> 20 -> 10 -> null

💡 All push operations complete; head points to the newest node at the start.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 5	After Step 7	After Step 8	After Step 10	Final
head	nullptr	nullptr	Node(10)	Node(10)	Node(20)	Node(20)	Node(30)	Node(30)
newNode	undefined	Node(10)	Node(10)	Node(20)	Node(20)	Node(30)	Node(30)	Node(30)
newNode->next	undefined	nullptr	nullptr	Node(10)	Node(10)	Node(20)	Node(20)	Node(20)

Key Moments - 3 Insights

Why do we set newNode->next to head before updating head?

Because newNode needs to point to the current first node to keep the list connected. This is shown in steps 3, 6, and 9 where newNode->next is set to head before head changes (steps 4, 7, 10).

What happens if the list is empty when we push a new node?

If the list is empty, head is nullptr. Setting newNode->next = head means newNode->next = nullptr, so the new node points to nothing, becoming the only node. This is shown in steps 1 to 4.

Why does head always point to the newest node after push?

Because after setting newNode->next to the old head, we update head to newNode (steps 4, 7, 10). This makes the new node the first node in the list.

Visual Quiz - 3 Questions

Look at the execution table at step 7. What does head point to?

A Node with data 10

B Node with data 30

C Node with data 20

D nullptr

💡 Hint

Check the 'Pointer Changes' and 'Visual State' columns at step 7.

At which step does the list first contain two nodes?

A Step 7

B Step 4

C Step 6

D Step 10

💡 Hint

Look at the 'Nodes in List' column to see when two nodes appear.

If we skip setting newNode->next = head, what happens to the list after push?

A List remains unchanged

B New node points to nullptr, old list lost

C Head points to old first node

D New node points to itself

💡 Hint

Consider how the 'Pointer Changes' column shows the importance of linking newNode to head.

Concept Snapshot

Push Using Linked List Node:
- Create new node with data
- Set newNode->next to current head
- Update head to newNode
- New node becomes first in list
- Works even if list is empty

Full Transcript

This concept shows how to add a new node at the start of a linked list. We create a new node with the given data. Then we link this new node's next pointer to the current head of the list. Finally, we update the head pointer to point to this new node. This way, the new node becomes the first node in the list. If the list was empty, the new node points to null and becomes the only node. The execution table traces each step of this process, showing how the list grows from empty to having multiple nodes. The variable tracker shows how pointers change after each step. Key moments clarify why we set newNode->next before changing head and what happens when the list is empty. The visual quiz tests understanding of pointer updates and list state changes.

Practice

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

easy

A. Deletes the entire linked 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 inserts a new node at the start (head) of the linked list.

2. Step 2: Effect of push on list structure

   The new node becomes the head, and its next pointer points to the previous head node.

3. Final Answer:

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

4. Quick Check:

   Push means insert at head = D [OK]

Hint: Push always adds node at the start (head) [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 at the head in C++ linked list?

easy

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

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

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

D. Node* newNode = Node(data); head = newNode->next;

Solution

1. Step 1: Create new node dynamically

   Use new Node(data) to allocate memory and initialize node.

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:

   Dynamic allocation + pointer update = B [OK]

Hint: Use pointer and 'new' keyword to create and link node [OK]

Common Mistakes:

• Not using pointer (*) for new node
• Using dot (.) instead of arrow (->) for pointers
• Assigning head incorrectly

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

struct Node {
  int data;
  Node* next;
  Node(int val) : data(val), next(nullptr) {}
};

Node* head = nullptr;

// Push 10
Node* newNode1 = new Node(10);
newNode1->next = head;
head = newNode1;

// Push 20
Node* newNode2 = new Node(20);
newNode2->next = head;
head = newNode2;

// Push 30
Node* newNode3 = new Node(30);
newNode3->next = head;
head = newNode3;

// Print list
Node* temp = head;
while(temp != nullptr) {
  std::cout << temp->data << " -> ";
  temp = temp->next;
}
std::cout << "null";

medium

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

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

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

D. null

Solution

1. Step 1: Trace push operations

   First push 10: list is 10 -> null. Then push 20: list becomes 20 -> 10 -> null. Then push 30: list becomes 30 -> 20 -> 10 -> null.

2. Step 2: Print linked list

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

3. Final Answer:

   30 -> 20 -> 10 -> null -> Option B

4. Quick Check:

   Push adds at head, last pushed is first = C [OK]

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

Common Mistakes:

• Assuming push adds at tail
• Mixing order of nodes
• Not updating head pointer correctly

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

void push(Node* head, int data) {
  Node* newNode = new Node(data);
  newNode->next = head;
  head = newNode;
}

medium

A. head is passed by value, so original list head is not updated

B. newNode is not allocated dynamically

C. newNode->next should be nullptr

D. Function should return void* instead of void

Solution

1. Step 1: Analyze parameter passing

   head is passed by value, so changes inside function do not affect original head pointer.

2. Step 2: Effect on linked list

   Assigning head = newNode only changes local copy; original list head remains unchanged.

3. Final Answer:

   head is passed by value, so original list head is not updated -> Option A

4. Quick Check:

   Pass pointer by reference or pointer to pointer [OK]

Hint: Pass head by reference or pointer to update original [OK]

Common Mistakes:

• Ignoring parameter passing method
• Not returning new head if passed by value
• Incorrect pointer usage

5. You want to implement a stack using a singly linked list with push operation. Which approach correctly maintains the stack's LIFO order?

hard

A. Push new nodes at the tail and update head pointer

B. Push new nodes at the tail of the linked list without tail pointer

C. Push new nodes at the head of the linked list

D. Insert new nodes randomly in the list

Solution

1. Step 1: Understand stack LIFO behavior

   Stack requires last-in, first-out order, so newest element must be accessed first.

2. Step 2: Push at head maintains LIFO

   Adding new nodes at head means newest node is always at front, enabling O(1) push and pop.

3. Step 3: Problems with tail insertion

   Inserting at tail without tail pointer is inefficient and does not maintain LIFO easily.

4. Final Answer:

   Push new nodes at the head of the linked list -> Option C

5. Quick Check:

   Stack push = insert at head = A [OK]

Hint: Stack push uses head insertion for O(1) LIFO [OK]

Common Mistakes:

• Pushing at tail without tail pointer (slow)
• Not maintaining LIFO order
• Inserting nodes randomly