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 connected items called nodes. Each node holds some data and a link to the next node in the chain. This structure allows easy insertion and removal of items without moving other elements. It is a basic way to organize data in a sequence.

Why it matters

Without linked lists, programs would struggle to efficiently add or remove items in the middle of a list because arrays require shifting elements. Linked lists solve this by linking nodes directly, making dynamic data management smoother. This helps in many real-world applications like undo features, music playlists, and navigation paths.

Where it fits

Before learning linked lists, you should understand basic programming concepts like variables, classes, and pointers or references. After mastering singly linked lists, you can explore more complex structures like doubly linked lists, stacks, queues, and trees.

Mental Model

Core Idea

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

Think of it like...

Imagine a treasure hunt where each clue (node) tells you where to find the next clue. You follow the chain one step at a time until you reach the treasure.

Head -> [Data | Next] -> [Data | Next] -> [Data | null]
Each box is a node holding 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 reference to the next node.

In C#, a node is a class with two parts: a data field to hold the value and a reference field to point to the next node. For example: class Node { public int Data; public Node Next; public Node(int data) { Data = data; Next = null; } } This creates a single node that can hold a number and link to another node.

Result

You can create a node with a value and see that its next pointer is null, meaning it doesn't link to anything yet.

Understanding that each node holds both data and a link is the foundation for building the entire linked list.

2

Foundation

Creating the Linked List Class

Concept: Build a class to manage the chain of nodes, starting with an empty list.

The linked list class keeps track of the first node, called the head. Initially, the list is empty, so head is null: class SinglyLinkedList { private Node head; public SinglyLinkedList() { head = null; } } This class will hold methods to add, remove, and display nodes.

Result

You have a container ready to hold nodes, but it starts empty with no nodes linked.

Knowing the list starts empty and uses a head pointer helps you control where the list begins.

3

Intermediate

Adding Nodes at the Front

🤔Before reading on: do you think adding a node at the front changes the head pointer or the last node? Commit to your answer.

Concept: Learn how to insert a new node at the beginning of the list and update the head.

To add a node at the front: 1. Create a new node with the data. 2. Point its next to the current head. 3. Update head to this new node. Example method: public void AddFirst(int data) { Node newNode = new Node(data); newNode.Next = head; head = newNode; } This inserts the new node before all others.

Result

After adding 3, then 5, the list looks like: 5 -> 3 -> null

Understanding that the head pointer moves to the new node is key to correctly adding nodes at the front.

4

Intermediate

Traversing the List to Display

🤔Before reading on: do you think you can access nodes randomly by index in a singly linked list? Commit to your answer.

Concept: Learn how to walk through the list from head to end to read all data.

To display all nodes: 1. Start at head. 2. While current node is not null, print its data. 3. Move to next node. Example method: public void PrintList() { Node current = head; while (current != null) { Console.Write(current.Data + " -> "); current = current.Next; } Console.WriteLine("null"); } This prints the list in order.

Result

Output for list 5 -> 3 -> null is: 5 -> 3 -> null

Knowing you must follow links one by one explains why linked lists don't support quick random access.

5

Intermediate

Adding Nodes at the End

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

Concept: Learn how to add a new node at the end by finding the last node and linking it.

To add at the end: 1. Create a new node. 2. If list is empty, set head to new node. 3. Otherwise, start at head and move through nodes until you find the last (next is null). 4. Set last node's next to new node. Example method: public void AddLast(int data) { Node newNode = new Node(data); if (head == null) { head = newNode; return; } Node current = head; while (current.Next != null) { current = current.Next; } current.Next = newNode; } This appends the node at the end.

Result

Adding 7 to list 5 -> 3 -> null results in 5 -> 3 -> 7 -> null

Understanding traversal to the last node is essential for appending nodes in a singly linked list.

6

Advanced

Removing Nodes by Value

🤔Before reading on: do you think removing a node requires changing the head if the node is first? Commit to your answer.

Concept: Learn how to find and remove a node with a specific value, updating links to keep the chain intact.

To remove a node: 1. Check if head is null (empty list). 2. If head holds the value, move head to next node. 3. Otherwise, traverse nodes keeping track of previous. 4. When node with value found, set previous node's next to current node's next. Example method: public void Remove(int data) { if (head == null) return; if (head.Data == data) { head = head.Next; return; } Node current = head; while (current.Next != null && current.Next.Data != data) { current = current.Next; } if (current.Next != null) { current.Next = current.Next.Next; } } This removes the first node with the given value.

Result

Removing 3 from 5 -> 3 -> 7 -> null results in 5 -> 7 -> null

Knowing how to update links around a removed node prevents breaking the chain and losing data.

7

Expert

Handling Edge Cases and Null Safety

🤔Before reading on: do you think forgetting to check for null pointers can crash your program? Commit to your answer.

Concept: Learn to safely handle empty lists, single-node lists, and null references to avoid errors.

Edge cases include: - Empty list (head is null) - Removing from empty list - Adding to empty list - Removing head node Always check if head or current nodes are null before accessing their members. For example, in Remove method, checking if head is null avoids crashes. Also, when traversing, ensure current.Next is not null before accessing current.Next.Data. These checks keep the program stable and prevent runtime exceptions.

Result

Program runs safely without crashes even when list is empty or operations target missing nodes.

Understanding and handling edge cases is crucial for building robust linked list implementations.

Under the Hood

Each node is an object stored in memory with two parts: data and a reference (pointer) to the next node's memory address. The list itself holds a reference to the first node (head). Traversing means following these references from one node to the next until a null reference signals the end. Memory is allocated dynamically for each node, allowing flexible list size.

Why designed this way?

Linked lists were designed to overcome fixed-size limitations of arrays and costly element shifting. By linking nodes with pointers, insertion and deletion become efficient without moving other elements. This design trades off random access speed for flexibility and dynamic sizing.

Singly Linked List Structure:

[Head] --> [Node1: Data | Next] --> [Node2: Data | Next] --> [Node3: Data | null]

Traversal:
Start at Head
  ↓
Follow Next pointers
  ↓
Stop when Next is null

Myth Busters - 4 Common Misconceptions

Quick: Does a singly linked list allow direct access to the middle element by index? Commit yes or no.

Common Belief: You can access any element in a singly linked list directly by its position like an array.

Reality: Singly linked lists do not support direct access by index; you must start at the head and follow links one by one.

Why it matters: Assuming direct access leads to inefficient code or bugs when trying to jump to nodes without traversal.

Quick: When adding a node at the end, do you need to update the head pointer? Commit yes or no.

Common Belief: Adding a node at the end always requires changing the head pointer.

Reality: The head pointer only changes when adding the first node; otherwise, you update the last node's next pointer.

Why it matters: Misunderstanding this causes incorrect list structure and lost nodes.

Quick: Can you remove a node without updating any pointers? Commit yes or no.

Common Belief: You can remove a node by just deleting it without changing other nodes.

Reality: Removing a node requires updating the previous node's next pointer to skip the removed node.

Why it matters: Failing to update pointers breaks the chain, causing data loss or runtime errors.

Quick: Is it safe to access the next node without checking if it exists? Commit yes or no.

Common Belief: You can always access the next node's data without checking if the next node is null.

Reality: Accessing next node without null checks can cause runtime errors (null reference exceptions).

Why it matters: Ignoring null checks leads to program crashes and unstable behavior.

Expert Zone

1

The choice between singly and doubly linked lists depends on whether backward traversal is needed, trading memory for flexibility.

2

Maintaining a tail pointer can optimize adding nodes at the end from O(n) to O(1), but requires extra care in updates.

3

Garbage collection in managed languages like C# automatically frees unreferenced nodes, but in unmanaged languages, manual memory management is critical.

When NOT to use

Singly linked lists are not ideal when you need fast random access or frequent backward traversal. In such cases, arrays or doubly linked lists are better alternatives.

Production Patterns

In real systems, singly linked lists are used for lightweight queues, adjacency lists in graphs, and implementing stacks. They often include optimizations like tail pointers or sentinel nodes to simplify edge cases.

Connections

Arrays

Arrays and linked lists both store sequences but differ in memory layout and access speed.

Understanding arrays helps appreciate why linked lists trade direct access for flexible insertion and deletion.

Pointers and References

Linked lists rely on pointers or references to connect nodes.

Grasping how pointers work is essential to understanding how linked lists link nodes dynamically.

Supply Chain Management

Both involve a sequence of connected steps or items where each depends on the previous.

Seeing linked lists like a supply chain clarifies how each node depends on the previous link to maintain order and flow.

Common Pitfalls

#1 Forgetting to update the head when adding the first node.

Wrong approach:

public void AddFirst(int data) {
Node newNode = new Node(data);
newNode.Next = head;
// Missing head = newNode;
}

Correct approach:

public void AddFirst(int data) {
Node newNode = new Node(data);
newNode.Next = head;
head = newNode;
}

Root cause:

Not realizing the head pointer must point to the new first node to keep the list connected.

#2 Accessing current.Next.Data without checking if current.Next is null.

Wrong approach:

while (current.Next.Data != data) {
current = current.Next;
}

Correct approach:

while (current.Next != null && current.Next.Data != data) {
current = current.Next;
}

Root cause:

Ignoring null checks leads to runtime exceptions when reaching the list end.

#3 Removing a node without updating the previous node's next pointer.

Wrong approach:

public void Remove(int data) {
Node current = head;
while (current != null) {
if (current.Data == data) {
current = current.Next; // Just moves current, does not unlink
return;
}
current = current.Next;
}
}

Correct approach:

public void Remove(int data) {
if (head == null) return;
if (head.Data == data) {
head = head.Next;
return;
}
Node current = head;
while (current.Next != null && current.Next.Data != data) {
current = current.Next;
}
if (current.Next != null) {
current.Next = current.Next.Next;
}
}

Root cause:

Misunderstanding that removing requires changing links, not just skipping nodes.

Key Takeaways

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

Each node contains data and a reference to the next node, and the list is managed by a head pointer.

Adding or removing nodes involves updating pointers carefully to maintain the chain without breaking it.

Traversal requires starting at the head and following links one by one; random access is not possible.

Handling edge cases and null checks is essential to avoid errors and build robust linked list implementations.

Practice

1. What is the main purpose of a Singly Linked List in data structures?

easy

A. To store elements in a linear order where each element points to the next

B. To store elements in a tree-like hierarchical structure

C. To store elements with direct access by index like an array

D. To store elements in a key-value pair format

Solution

1. Step 1: Understand the structure of a singly linked list

   A singly linked list stores elements in nodes where each node points to the next node, forming a chain.

2. Step 2: Compare with other data structures

   Unlike trees or arrays, singly linked lists do not have hierarchical or direct index access but maintain a linear sequence through pointers.

3. Final Answer:

   To store elements in a linear order where each element points to the next -> Option A

4. Quick Check:

   Singly Linked List = linear chain of nodes [OK]

Hint: Remember: singly linked list nodes point only forward [OK]

Common Mistakes:

• Confusing linked lists with arrays having direct index access
• Thinking linked lists store key-value pairs
• Assuming linked lists have hierarchical structure like trees

2. Which of the following is the correct way to declare a node class for a singly linked list in C#?

easy

A. public class Node { public int data; public Node previous; }

B. public class Node { int data; int next; }

C. public class Node { public int data; public int next; }

D. public class Node { public int data; public Node next; }

Solution

1. Step 1: Identify the correct node structure for singly linked list

   A node must store data and a reference to the next node, so the next pointer type should be Node.

2. Step 2: Check each option's correctness

   public class Node { public int data; public Node next; } correctly declares data as int and next as Node. Options B and C incorrectly use int for next. public class Node { public int data; public Node previous; } uses previous which is for doubly linked lists.

3. Final Answer:

   public class Node { public int data; public Node next; } -> Option D

4. Quick Check:

   Node next pointer type = Node [OK]

Hint: Next pointer must be Node type, not int [OK]

Common Mistakes:

• Using int type for next pointer instead of Node
• Confusing singly linked list with doubly linked list (previous pointer)
• Omitting access modifiers making members inaccessible

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

public class Node {
    public int data;
    public Node next;
    public Node(int d) { data = d; next = null; }
}

public class LinkedList {
    public Node head;
    public void Add(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
        } else {
            Node temp = head;
            while (temp.next != null) {
                temp = temp.next;
            }
            temp.next = newNode;
        }
    }
    public void PrintList() {
        Node temp = head;
        while (temp != null) {
            Console.Write(temp.data + " -> ");
            temp = temp.next;
        }
        Console.WriteLine("null");
    }
}

class Program {
    static void Main() {
        LinkedList list = new LinkedList();
        list.Add(10);
        list.Add(20);
        list.Add(30);
        list.PrintList();
    }
}

medium

A. null

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

C. 10 -> 20 -> null

D. 30 -> 20 -> 10 -> null

Solution

1. Step 1: Trace the Add method calls

   Adding 10 sets head to node with data 10. Adding 20 appends node with data 20 at end. Adding 30 appends node with data 30 at end.

2. Step 2: Trace the PrintList method

   PrintList starts at head and prints each node's data followed by ' -> ' until null is reached, printing "10 -> 20 -> 30 -> null".

3. Final Answer:

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

4. Quick Check:

   Nodes added in order = printed in order [OK]

Hint: Add appends at end; print shows nodes in insertion order [OK]

Common Mistakes:

• Assuming Add inserts at head instead of tail
• Forgetting to print 'null' at end
• Printing nodes in reverse order

4. Identify the error in the following C# code snippet for adding a node to a singly linked list:

public void Add(int data) {
    Node newNode = new Node(data);
    if (head == null) {
        head = newNode;
    } else {
        Node temp = head;
        while (temp != null) {
            temp = temp.next;
        }
        temp.next = newNode;
    }
}

medium

A. The while loop condition should be 'temp.next != null' instead of 'temp != null'

B. The newNode should be created outside the method

C. The head should be set to null inside the else block

D. The method should return the newNode

Solution

1. Step 1: Analyze the while loop condition

   The loop currently runs while temp != null, so it stops when temp is null, meaning temp.next is not accessible.

2. Step 2: Correct the loop to stop at last node

   The loop should run while temp.next != null to stop at the last node, so we can set temp.next = newNode safely.

3. Final Answer:

   The while loop condition should be 'temp.next != null' instead of 'temp != null' -> Option A

4. Quick Check:

   Traverse until last node (temp.next != null) [OK]

Hint: Loop until temp.next is null to find last node [OK]

Common Mistakes:

• Looping until temp is null causes null reference error
• Trying to assign next on null reference
• Misplacing node creation outside method

5. You want to create a method Reverse() in your singly linked list class that reverses the list in place. Which approach correctly reverses the list?

hard

A. Swap data values between head and tail nodes repeatedly until the middle is reached.

B. Create a new list and copy nodes from the original list in reverse order.

C. Iterate through the list, for each node set its next pointer to the previous node, updating previous and current pointers until the end.

D. Set head to null and re-add nodes in reverse order using Add method.

Solution

1. Step 1: Understand in-place reversal logic

   Reversing a singly linked list in place requires changing each node's next pointer to point to the previous node, not creating new nodes or swapping data.

2. Step 2: Evaluate options for correctness

   Iterating through the list, for each node setting its next pointer to the previous node while updating previous and current pointers until the end correctly describes the standard in-place reversal. The other options involve extra memory or inefficient operations.

3. Final Answer:

   Iterate through the list, for each node set its next pointer to the previous node, updating previous and current pointers until the end. -> Option C

4. Quick Check:

   Reverse by redirecting next pointers in place [OK]

Hint: Reverse by changing next pointers, not data or new nodes [OK]

Common Mistakes:

• Creating new lists instead of reversing in place
• Swapping data instead of pointers
• Resetting head to null losing the list