Creating a Singly Linked List from Scratch in DSA C++ - Visual Walkthrough

Concept Flow - Creating a Singly Linked List from Scratch

Start

↓

Create head node with data

↓

Set head.next = nullptr

↓

Add more nodes?

No→Done

Yes↓

Create new node

↓

Traverse to last node

↓

Set last_node.next = new_node

↓

Repeat Add more nodes?

Start by creating the first node as head. For each new node, traverse to the last node and link the new node at the end. Repeat until no more nodes to add.

Execution Sample

DSA C++

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

Node* head = new Node{1, nullptr};
Node* second = new Node{2, nullptr};
head->next = second;

This code creates two nodes and links the first node's next pointer to the second node, forming a simple linked list.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create head node with data=1	Node1	head -> Node1	1 -> null
2	Create second node with data=2	Node1, Node2	second -> Node2	1 -> null, 2 -> null
3	Link head.next to second	Node1, Node2	head.next = second	1 -> 2 -> null
4	Create third node with data=3	Node1, Node2, Node3	third -> Node3	1 -> 2 -> null, 3 -> null
5	Traverse to last node (Node2)	Node1, Node2, Node3	current = Node2	1 -> 2 -> null, 3 -> null
6	Link last_node.next to third	Node1, Node2, Node3	Node2.next = third	1 -> 2 -> 3 -> null
7	No more nodes to add	Node1, Node2, Node3	No pointer changes	1 -> 2 -> 3 -> null

💡 No more nodes to add, linked list creation complete

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
head	nullptr	Node1	Node1	Node1	Node1	Node1	Node1	Node1
second	nullptr	nullptr	Node2	Node2	Node2	Node2	Node2	Node2
third	nullptr	nullptr	nullptr	nullptr	Node3	Node3	Node3	Node3
current	nullptr	nullptr	nullptr	nullptr	nullptr	Node2	Node2	Node2
Node1.next	undefined	nullptr	nullptr	Node2	Node2	Node2	Node2	Node2
Node2.next	undefined	undefined	nullptr	nullptr	nullptr	nullptr	Node3	Node3
Node3.next	undefined	undefined	undefined	undefined	nullptr	nullptr	nullptr	nullptr

Key Moments - 3 Insights

Why do we need to traverse to the last node before linking a new node?

Because in a singly linked list, each node only knows about the next node. To add at the end, we must find the last node whose next is nullptr (see Step 5 in execution_table).

What happens if we forget to set the new node's next pointer to nullptr?

The new node's next pointer might point to garbage or old memory, causing undefined behavior. In the table, all new nodes start with next = nullptr (see Steps 1, 2, 4).

Why does the head pointer not change after adding more nodes?

The head always points to the first node. Adding nodes at the end does not move the head pointer (see variable_tracker for 'head' across steps).

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, what is the visual state of the list?

A 1 -> null

B 1 -> 2 -> null

C 2 -> 1 -> null

D null

💡 Hint

Check the 'Visual State' column at Step 3 in execution_table

At which step does the last node's next pointer get linked to the new node?

A Step 4

B Step 5

C Step 6

D Step 7

💡 Hint

Look at 'Pointer Changes' column in execution_table for linking last_node.next

If we add a fourth node, which variable will be used to traverse the list to find the last node?

A current

B head

C second

D third

💡 Hint

See variable_tracker and execution_table Step 5 where 'current' is used to traverse

Concept Snapshot

Creating a Singly Linked List:
- Define Node with data and next pointer
- Create head node with data and next=nullptr
- For each new node:
  - Create node with data and next=nullptr
  - Traverse from head to last node
  - Link last_node.next to new node
- Repeat until all nodes added
- Head always points to first node

Full Transcript

To create a singly linked list from scratch, start by defining a Node structure with data and a next pointer. Create the head node with the first data value and set its next pointer to nullptr, meaning it points to nothing yet. For each additional node, create a new node with data and next set to nullptr. Then, traverse the list starting from head to find the last node, which is the node whose next pointer is nullptr. Link this last node's next pointer to the new node. Repeat this process until all nodes are added. The head pointer always points to the first node and does not change when adding nodes at the end. This process builds a chain of nodes connected by next pointers, forming the singly linked list.

Practice

1. What is the primary purpose of a Node in a singly linked list?

easy

A. To store data and a reference to the next node

B. To store data and a reference to the previous node

C. To store data only without any references

D. To store the size of the list

Solution

1. Step 1: Understand the Node structure

   A node in a singly linked list holds data and a pointer to the next node.

2. Step 2: Identify the pointer direction

   Since it is singly linked, the node only points forward to the next node, not backward.

3. Final Answer:

   To store data and a reference to the next node -> Option A

4. Quick Check:

   Node = data + next pointer [OK]

Hint: Node always stores data and next pointer in singly linked list [OK]

Common Mistakes:

• Confusing singly linked list with doubly linked list
• Thinking node stores previous node reference
• Assuming node stores list size

2. Which of the following is the correct way to declare a Node struct in C++ for a singly linked list?

easy

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

B. struct Node { int data; Node next; };

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

D. struct Node { int data; Node& next; };

Solution

1. Step 1: Understand pointer syntax in C++

   To link nodes, we use a pointer to the next node: Node* next;.

2. Step 2: Check each option

   struct Node { int data; Node* next; }; correctly uses Node* next;. Options A, B, and C have invalid syntax for pointers or references.

3. Final Answer:

   struct Node { int data; Node* next; }; -> Option C

4. Quick Check:

   Pointer to next node = Node* next [OK]

Hint: Use * for pointer to next node in struct [OK]

Common Mistakes:

• Using object instead of pointer for next
• Using reference incorrectly for next
• Syntax errors in pointer declaration

3. What will be the output of the following code snippet that creates a singly linked list with nodes containing values 10, 20, 30 and prints them?

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

int main() {
  Node* head = new Node{10, nullptr};
  head->next = new Node{20, nullptr};
  head->next->next = new Node{30, nullptr};

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

medium

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

B. 10 -> 20 -> null

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

D. Compilation error

Solution

1. Step 1: Trace node creation and linking

   Nodes are created with values 10, 20, 30 linked in order: head -> 10 -> 20 -> 30 -> nullptr.

2. Step 2: Trace printing loop

   The loop prints each node's data followed by ' -> ', ending with 'null'. Output is "10 -> 20 -> 30 -> null".

3. Final Answer:

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

4. Quick Check:

   Print nodes in order = 10 -> 20 -> 30 -> null [OK]

Hint: Follow next pointers to print nodes in order [OK]

Common Mistakes:

• Printing nodes in reverse order
• Missing last node in output
• Confusing nullptr with null string

4. Identify the error in the following code that attempts to create a singly linked list with two nodes:

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

int main() {
  Node* head = new Node{1, nullptr};
  head->next = new Node{2, nullptr};
  head->next->next = new Node{3, nullptr};
  return 0;
}

medium

A. Incorrect struct definition

B. head->next->next is assigned but head->next is nullptr

C. Missing initialization of head pointer

D. No error, code runs correctly

Solution

1. Step 1: Check node creation and linking

   head is created with data 1, next nullptr. Then head->next is assigned new node with data 2, next nullptr.

2. Step 2: Assign head->next->next

   head->next is not nullptr, so assigning head->next->next to new node with data 3 is valid.

3. Final Answer:

   No error, code runs correctly -> Option D

4. Quick Check:

   Nodes linked properly, no nullptr dereference [OK]

Hint: Check if pointer is nullptr before accessing next [OK]

Common Mistakes:

• Assuming head->next is nullptr before assignment
• Confusing pointer initialization
• Thinking struct definition is wrong

5. You want to create a function appendNode that adds a new node with given data at the end of a singly linked list. Which of the following implementations correctly appends a node?

void appendNode(Node*& head, int value) {
  Node* newNode = new Node{value, nullptr};
  if (head == nullptr) {
    head = newNode;
  } else {
    Node* temp = head;
    while (temp->next != nullptr) {
      temp = temp->next;
    }
    temp->next = newNode;
  }
}

hard

A. Infinite loop due to wrong while condition

B. Correctly appends node at end

C. Fails to update head when list is empty

D. Does not create new node properly

Solution

1. Step 1: Check new node creation

   New node is created with given value and next set to nullptr, which is correct for end node.

2. Step 2: Check list empty and non-empty cases

   If head is nullptr, head is updated to new node. Otherwise, code traverses to last node and sets its next to new node.

3. Final Answer:

   Correctly appends node at end -> Option B

4. Quick Check:

   Traverse to last node and link new node [OK]

Hint: Traverse to last node, then link new node [OK]

Common Mistakes:

• Not updating head when list is empty
• Wrong loop condition causing infinite loop
• Forgetting to set new node's next to nullptr