Creating a Singly Linked List from Scratch in DSA C++ - Algorithm Mechanics

Overview - Creating a Singly Linked List from Scratch

What is it?

A singly linked list is a simple chain of elements where each element points to the next one. It starts with a head element and ends when there is no next element. This structure allows easy insertion and removal of elements without shifting others. It is a basic way to organize data in a sequence.

Why it matters

Without linked lists, managing sequences of data would be less flexible and efficient, especially when adding or removing items in the middle. Arrays require shifting elements, which can be slow. Linked lists solve this by linking elements directly, making dynamic data handling smoother. This helps in many real-world applications like music playlists, undo features, and more.

Where it fits

Before learning linked lists, you should understand basic programming concepts like variables, pointers or references, and simple data types. After mastering linked lists, you can explore more complex structures like doubly linked lists, trees, and graphs, which build on similar ideas.

Mental Model

Core Idea

A singly linked list is a chain of nodes where each node holds data and a link to the next node, forming a simple, flexible sequence.

Think of it like...

Imagine a treasure hunt where each clue leads you to the next one. Each clue is like a node holding information and a pointer to where the next clue is hidden.

Head -> [Data | Next] -> [Data | Next] -> [Data | null]

Each box is a node with two parts: data and a pointer to the next node. The last node points to null, meaning the end.

Build-Up - 7 Steps

1

Foundation

Understanding Node Structure

Concept: Learn what a node is and how it stores data and a pointer to the next node.

In C++, a node can be a struct or class with two parts: one for data (like an integer) and one for a pointer to the next node. For example: struct Node { int data; Node* next; }; This means each node knows its value and where the next node is.

Result

You can create a single node that holds a value and points to nothing (null).

Understanding the node is key because the entire linked list is built by connecting these nodes.

2

Foundation

Creating the First Node (Head)

Concept: Learn how to create the first node and set it as the head of the list.

To start a linked list, create a node and make a pointer called head point to it: Node* head = new Node(); head->data = 10; head->next = nullptr; This means the list has one element with value 10 and no next node.

Result

A linked list with one node: 10 -> null

The head pointer is the entry point to the list; without it, you can't access the list.

3

Intermediate

Adding Nodes at the End

🤔Before reading on: do you think adding a node at the end requires changing the head pointer? Commit to your answer.

Concept: Learn how to add new nodes at the end by updating the last node's next pointer.

To add a node at the end, you must find the last node (where next is null) and link it to the new node: Node* newNode = new Node(); newNode->data = 20; newNode->next = nullptr; Node* temp = head; while (temp->next != nullptr) { temp = temp->next; } temp->next = newNode; Now the list is 10 -> 20 -> null.

Result

List after adding: 10 -> 20 -> null

Knowing how to traverse the list to find the end is essential for dynamic growth.

4

Intermediate

Traversing and Printing the List

🤔Before reading on: do you think you can print all elements without changing the list? Commit to your answer.

Concept: Learn how to visit each node from head to end to read or print data.

Start from head and move through each node using the next pointer until you reach null: Node* temp = head; while (temp != nullptr) { std::cout << temp->data << " -> "; temp = temp->next; } std::cout << "null" << std::endl; This prints the list contents in order.

Result

Printed output: 10 -> 20 -> null

Traversal is the basic operation to access or display all elements in the list.

5

Intermediate

Inserting Nodes at the Beginning

🤔Before reading on: do you think inserting at the beginning changes the head pointer? Commit to your answer.

Concept: Learn how to add a new node at the start by updating the head pointer.

Create a new node and make it point to the current head, then update head to this new node: Node* newNode = new Node(); newNode->data = 5; newNode->next = head; head = newNode; Now the list is 5 -> 10 -> 20 -> null.

Result

List after insertion at start: 5 -> 10 -> 20 -> null

Changing the head pointer is necessary to keep the list connected when adding at the front.

6

Advanced

Deleting a Node by Value

🤔Before reading on: do you think deleting a node requires updating pointers of neighboring nodes? Commit to your answer.

Concept: Learn how to remove a node by adjusting pointers to skip it and free memory.

To delete a node with a specific value: - If it's the head, move head to next node and delete old head. - Otherwise, find the node before the target, link it to target's next, then delete target. Example deleting 10: if (head->data == 10) { Node* temp = head; head = head->next; delete temp; } else { Node* temp = head; while (temp->next && temp->next->data != 10) { temp = temp->next; } if (temp->next) { Node* toDelete = temp->next; temp->next = toDelete->next; delete toDelete; } } List updates accordingly.

Result

List after deleting 10: 5 -> 20 -> null

Proper pointer updates prevent breaking the list and memory leaks.

7

Expert

Memory Management and Avoiding Leaks

🤔Before reading on: do you think forgetting to delete nodes causes problems? Commit to your answer.

Concept: Understand the importance of freeing memory to avoid leaks in manual memory management languages like C++.

Each new node uses dynamic memory (new). If you don't delete nodes when removing them or at the end, memory stays occupied unnecessarily. To free the whole list: Node* temp = head; while (temp) { Node* next = temp->next; delete temp; temp = next; } head = nullptr; This cleans all nodes and prevents memory leaks.

Result

Memory freed, no leaks after list destruction.

Managing memory manually is critical in C++ to keep programs efficient and stable.

Under the Hood

Each node is a small block of memory holding data and a pointer to the next node's memory address. The head pointer stores the address of the first node. Traversing means following these addresses from one node to the next until a null pointer signals the end. Adding or removing nodes changes these pointers to maintain the chain without moving actual data blocks.

Why designed this way?

Linked lists were designed to allow flexible memory use without needing contiguous blocks like arrays. This design lets programs grow or shrink lists dynamically without costly data copying. Alternatives like arrays require fixed sizes or expensive resizing, so linked lists trade direct access speed for flexible memory use.

Head
  ↓
+-------+     +-------+     +-------+     +-------+
| Data  | --> | Data  | --> | Data  | --> | null  |
| Next  |     | Next  |     | Next  |     |       |
+-------+     +-------+     +-------+     +-------+

Myth Busters - 3 Common Misconceptions

Quick: Does a singly linked list allow moving backward easily? Commit yes or no.

Common Belief: A singly linked list lets you move forward and backward through the list easily.

Reality: A singly linked list only allows moving forward because each node points only to the next node, not the previous one.

Why it matters: Trying to move backward without extra data causes errors or inefficient workarounds, leading to bugs or slow code.

Quick: Is accessing the middle element in a linked list as fast as in an array? Commit yes or no.

Common Belief: Accessing any element in a linked list is as fast as in an array.

Reality: Linked lists require starting at the head and moving node by node to reach the middle, which is slower than direct array access.

Why it matters: Assuming fast random access can cause poor performance in programs that need frequent middle element access.

Quick: Does deleting a node automatically free its memory in C++? Commit yes or no.

Common Belief: Deleting a node pointer automatically frees the memory it used.

Reality: In C++, you must explicitly use delete to free memory; just removing pointers doesn't free memory.

Why it matters: Not freeing memory causes leaks, which can crash or slow down programs over time.

Expert Zone

1

Understanding that pointer manipulation errors can silently corrupt the list without immediate crashes, making debugging tricky.

2

Knowing that singly linked lists have O(n) time for searching and insertion at the end unless you maintain a tail pointer.

3

Recognizing that manual memory management requires careful design to avoid dangling pointers and double deletes.

When NOT to use

Singly linked lists are not ideal when you need fast random access or backward traversal; arrays or doubly linked lists are better. For very large data or frequent middle insertions, balanced trees or skip lists may outperform linked lists.

Production Patterns

In real systems, singly linked lists are used for simple queues, stacks, or adjacency lists in graphs. They often include a tail pointer for efficient appends and use smart pointers or garbage collection to manage memory safely.

Connections

Arrays

Linked lists and arrays both store sequences but differ in memory layout and access speed.

Knowing arrays helps understand why linked lists trade direct access speed for flexible size and insertion.

Pointer Arithmetic

Linked lists rely on pointers to connect nodes, making pointer arithmetic and memory addresses fundamental.

Understanding pointers deeply clarifies how linked lists manage dynamic memory and node connections.

Supply Chain Management

Like linked lists, supply chains connect steps in a sequence where each step depends on the previous one.

Seeing linked lists as chains of dependencies helps grasp their sequential and linked nature beyond programming.

Common Pitfalls

#1 Forgetting to set the next pointer of the last node to null.

Wrong approach:

Node* newNode = new Node();
newNode->data = 30;
// Missing newNode->next = nullptr;
Node* temp = head;
while (temp->next != nullptr) {
temp = temp->next;
}
temp->next = newNode;

Correct approach:

Node* newNode = new Node();
newNode->data = 30;
newNode->next = nullptr;
Node* temp = head;
while (temp->next != nullptr) {
temp = temp->next;
}
temp->next = newNode;

Root cause:

Not initializing the next pointer leads to unpredictable behavior or infinite loops during traversal.

#2 Deleting a node without updating the previous node's next pointer.

Wrong approach:

Node* toDelete = head->next;
delete toDelete; // head->next still points to deleted memory

Correct approach:

Node* toDelete = head->next;
head->next = toDelete->next;
delete toDelete;

Root cause:

Failing to update links breaks the chain and causes dangling pointers, leading to crashes.

#3 Using a local variable for a node pointer and returning it.

Wrong approach:

Node createNode(int val) {
Node node;
node.data = val;
node.next = nullptr;
return node; // returns a copy, not a pointer
}

Correct approach:

Node* createNode(int val) {
Node* node = new Node();
node->data = val;
node->next = nullptr;
return node;
}

Root cause:

Returning local variables causes invalid memory access; dynamic allocation is needed for persistent nodes.

Key Takeaways

A singly linked list is a chain of nodes where each node points to the next, allowing flexible data sequences.

The head pointer is essential as the entry point to the list; changing it updates the list start.

Traversing the list means following next pointers until reaching null, which marks the end.

Adding or removing nodes requires careful pointer updates to maintain the chain and avoid memory issues.

Manual memory management in C++ demands explicit deletion of nodes to prevent memory leaks.

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