Creating a Singly Linked List from Scratch in DSA C++ - Step-by-Step

Mental Model

A singly linked list is a chain of boxes where each box holds a value and a pointer to the next box. We build it by linking boxes one after another.

Analogy: Imagine a treasure hunt where each clue points to the next clue. Each clue is like a box holding a value and a pointer to the next clue, forming a chain.

head -> [value|next] -> [value|next] -> [value|null]
↑

Dry Run Walkthrough

Input: Create a singly linked list with values 1, 2, 3 in order

Goal: Build a linked list where each node points to the next, ending with null

Step 1: Create first node with value 1 and set head to it

head -> [1|null]
↑

Why: We need a starting point for the list

Step 2: Create second node with value 2 and link first node's next to it

head -> [1|->] -> [2|null]
↑

Why: Link the first node to the second to extend the list

Step 3: Create third node with value 3 and link second node's next to it

head -> [1|->] -> [2|->] -> [3|null]
↑

Why: Link the second node to the third to complete the list

Result:

head -> [1|->] -> [2|->] -> [3|null]
Final list: 1 -> 2 -> 3 -> null

Annotated Code

DSA C++

#include <iostream>
using namespace std;

// Node class for singly linked list
class Node {
public:
    int data;
    Node* next;

    Node(int val) {
        data = val;
        next = nullptr;
    }
};

// Singly linked list class
class SinglyLinkedList {
public:
    Node* head;

    SinglyLinkedList() {
        head = nullptr;
    }

    // Function to add node at the end
    void append(int val) {
        Node* newNode = new Node(val); // create new node
        if (head == nullptr) {
            head = newNode; // list empty, new node is head
            return;
        }
        Node* curr = head;
        while (curr->next != nullptr) {
            curr = curr->next; // move to last node
        }
        curr->next = newNode; // link last node to new node
    }

    // Function to print list
    void printList() {
        Node* curr = head;
        while (curr != nullptr) {
            cout << curr->data << " -> ";
            curr = curr->next;
        }
        cout << "null" << endl;
    }
};

int main() {
    SinglyLinkedList list;
    list.append(1);
    list.append(2);
    list.append(3);
    list.printList();
    return 0;
}

Node* newNode = new Node(val); // create new node

create a new node with given value

if (head == nullptr) { head = newNode; return; }

if list empty, set head to new node and stop

while (curr->next != nullptr) { curr = curr->next; }

move curr to last node in list

curr->next = newNode; // link last node to new node

link last node's next pointer to new node

Output

1 -> 2 -> 3 -> null

Complexity Analysis

Time: O(n) because to append a node we traverse all n nodes to find the end

Space: O(n) because we store n nodes in memory for n elements

vs Alternative: Compared to arrays, linked lists allow easy insertion without shifting elements but require traversal to find the end

Edge Cases

empty list

head is null initially, first append sets head to new node

DSA C++

if (head == nullptr) { head = newNode; return; }

single element list

append adds new node after head correctly

DSA C++

while (curr->next != nullptr) { curr = curr->next; }

When to Use This Pattern

When you need a flexible list that grows dynamically without resizing, reach for singly linked list creation to build nodes linked by pointers.

Common Mistakes

Mistake: Not setting the head pointer when the list is empty
Fix: Check if head is null and assign new node to head before linking

Mistake: Forgetting to set new node's next to null
Fix: Initialize new node's next pointer to null in constructor

Summary

Creates a chain of nodes where each node points to the next, forming a singly linked list.

Use when you want a simple dynamic list that grows by linking nodes one after another.

The key is to keep track of the head and link each new node at the end by updating pointers.

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