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

Creating a Singly Linked List from Scratch

📖 Scenario: Imagine you want to keep track of your daily tasks in order. A singly linked list is like a chain where each task points to the next one. You will build this chain step-by-step.

🎯 Goal: Build a simple singly linked list in C++ that holds three tasks as strings. You will create nodes, link them, and finally print the list to see all tasks in order.

📋 What You'll Learn

Create a Node struct with a string data and a Node* next pointer

Create three nodes with exact task strings: "Task 1: Wake up", "Task 2: Brush teeth", "Task 3: Eat breakfast"

Link the nodes so that the first points to the second, and the second points to the third

Print the linked list in the format: Task 1: Wake up -> Task 2: Brush teeth -> Task 3: Eat breakfast -> null

💡 Why This Matters

🌍 Real World

Singly linked lists are used in many applications like task scheduling, undo functionality in software, and managing playlists.

💼 Career

Understanding linked lists is fundamental for software developers, especially when working with dynamic data and memory management.

1

Create the Node struct and three nodes

Create a struct Node with a string data and a Node* next. Then create three Node variables called node1, node2, and node3 with data set to "Task 1: Wake up", "Task 2: Brush teeth", and "Task 3: Eat breakfast" respectively. Set their next pointers to nullptr.

DSA C++

#include 
#include 

using namespace std;

// Define Node struct
// Create node1, node2, node3 with given data and next = nullptr
// Your code here

Hint

Think of Node as a box holding a task and a pointer to the next box. Initialize each node's next to nullptr because they are not linked yet.

2

Link the nodes to form the list

Inside main(), set node1.next to point to &node2 and node2.next to point to &node3. Leave node3.next as nullptr.

DSA C++

#include 
#include 

using namespace std;

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

int main() {
    Node node1 {"Task 1: Wake up", nullptr};
    Node node2 {"Task 2: Brush teeth", nullptr};
    Node node3 {"Task 3: Eat breakfast", nullptr};

    // Link node1 to node2 and node2 to node3
    // Your code here

    return 0;
}

Hint

Use the arrow operator -> or dot operator . to set the next pointers. Here, since nodes are variables, use node1.next = &node2;.

3

Create a pointer to the head of the list

Create a Node* pointer called head and set it to point to &node1. This pointer will represent the start of the linked list.

DSA C++

#include 
#include 

using namespace std;

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

int main() {
    Node node1 {"Task 1: Wake up", nullptr};
    Node node2 {"Task 2: Brush teeth", nullptr};
    Node node3 {"Task 3: Eat breakfast", nullptr};

    node1.next = &node2;
    node2.next = &node3;

    // Create head pointer to node1
    // Your code here

    return 0;
}

Hint

The head pointer helps us start walking through the list from the first node.

4

Print the linked list

Use a Node* pointer called current to traverse the list starting from head. Use a while loop to print each node's data followed by " -> ". After the loop, print "null" to show the end of the list.

DSA C++

#include 
#include 

using namespace std;

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

int main() {
    Node node1 {"Task 1: Wake up", nullptr};
    Node node2 {"Task 2: Brush teeth", nullptr};
    Node node3 {"Task 3: Eat breakfast", nullptr};

    node1.next = &node2;
    node2.next = &node3;

    Node* head = &node1;

    // Traverse and print the list
    // Your code here

    return 0;
}

Hint

Use a pointer to move from one node to the next until you reach nullptr. Print each task followed by an arrow, then print null at the end.

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