Singly Linked List Tutorial

Written by Hamza Sanaulla

Singly Linked List Tutorial. When we write programs, managing collections of elements is a daily chore. Most of us start our journey by writing arrays. They are simple, fast, and easy to understand. But eventually, you run into a wall. What happens when you try to insert a new element right in the middle of a $ 10,000$-element array? Your program is forced to shift every subsequent item to make space physically. It is slow, clumsy, and painfully resource-intensive.

What if your program could instead store data in a way that grows organically, claiming memory on the fly only when needed, and updating connections with the flick of a digital switch?

That is the power of the Singly Linked List.

Whether you are looking for the best singly linked list tutorial online to pass an upcoming university exam, reading up on singly linked list notes, or looking for a comprehensive DSA course with singly linked list breakdowns to prep for interviews, this complete guide is for you. We will break down this foundational linear data structure step by step, utilizing direct, clear concepts that bypass cold, dry academic textbooks.

What is a Singly Linked List?

To understand a linked list in data structure systems, we first have to understand the core limitation of standard arrays. Arrays require contiguous memory allocation. If you want an array of $5$ integers, your system must find a spot in RAM where $5$ integer-sized slots sit perfectly side-by-side. If your memory is fragmented, or if you need to double the array size later, you are out of luck. You must allocate a brand-new, larger block elsewhere, copy everything over, and delete the old array.

A Singly Linked List solves this by using a fully dynamic data structure design.

Instead of demanding a single contiguous block of memory, a linked list is scattered across your computer’s RAM. The elements are allocated dynamically at runtime, wherever your operating system can find room. Because they are not physically sitting next to each other, they maintain their ordered sequence by holding onto memory references. Each element holds its own data, along with a pointer pointing to where the next element lives.

This approach is highly prized in computer science and dynamic memory management. By utilizing runtime allocation, your program only takes up exactly as much space as it currently needs, no more, no less. It is a highly efficient way to manage memory when you do not know the incoming dataset size in advance.

Structure of a Singly Linked List

To understand the mechanics, let’s dissect the physical anatomy of this structure. Every singly linked list is composed of two primary entities: nodes and pointers.

The Node: The Building Block

A node in a singly linked list system is the basic atomic unit. It acts as a small storage container holding two distinct fields:

• Data: The actual value you want to store (an integer, a string, a custom user object, etc.).
• Next Pointer: A reference variable storing the memory address of the subsequent node in the sequence (data and next address).

The Boundary Keepers: Head and NULL

To keep track of this chain of nodes, we use two special indicators:

• Head Node / Head Pointer: This is your entry point. The head pointer is a reference variable that stores the memory address of the first node in the list. It is not a node itself, but rather a guidepost pointing to where the list begins. If the list is empty, the head pointer simply points to nothing (NULL).
• NULL Pointer: How does a program know when it has reached the end of the list? The next pointer of the very last node in the chain points to NULL (or nullptr in modern C++). This serves as a universal terminal boundary marker.

How a Singly Linked List Works

Let’s visualize a singly linked list with example data. Imagine you want to store a list of three ID numbers: $10$, $20$, and $30$.

In an array, they would sit side-by-side in addresses like 1000, 1004, and 1008.

In a singly linked list, your system might assign them random, fragmented addresses across your RAM:

• Node 10 lives at address 0x00A1. Its data field is $10$, and its next pointer contains 0x00C4.
• Node 20 lives at address 0x00C4. Its data field is $20$, and its next pointer contains 0x00B2.
• Node 30 lives at address 0x00B2. Its data field is $30$, and its next pointer contains NULL.

When your code wants to read this list, it starts at the head pointer (which holds 0x00A1). It reads the data $10$, looks at the address 0x00C4 stored in the next pointer, and jumps there. It reads $20$, looks at the next address 0x00B2, and jumps there. It reads $30$, notices the next address is NULL, and terminates.

This is why we call it sequential access. You cannot jump directly to the third element because you do not know its address until you have read the second element. You must follow the physical memory breadcrumbs.

Advantages of Singly Linked List

Why do software engineers use linked lists when arrays are so straightforward? Let’s look at the major advantages:

• Dynamic Resizing: Unlike standard arrays, you do not need to declare a fixed size at compile-time. The list grows as your data grows.
• Highly Efficient Insertions and Deletions: If you have a reference to a node, you can insert a new node right next to it in $\mathcal{O}(1)$ constant time. All you do is update two pointers. No shifting of elements, no rebuilding the list.
• Memory Efficiency (No Over-allocation): You never have to pre-allocate an array of size $1000$ “just in case” you receive $1000$ items. You allocate memory on-demand, saving RAM for other active system processes.

Disadvantages of Singly Linked List

While powerful, this structure is not a magic bullet. It has notable trade-offs:

• No Random Access: Want to access the $50\text{th}$ element? You cannot write list[50]. You must traverse through elements $0$ to $49$ first.
• Memory Pointer Overhead: Every single node must store a memory pointer alongside its data. On $64$-bit systems, a pointer takes up $8$ bytes of memory. If you are only storing $4$-byte integers, your memory overhead is substantial.
• Cache Unfriendliness: Because nodes are scattered randomly across memory, modern CPU caching mechanisms cannot predict the next node’s address. This leads to cache misses, making traversals slower than contiguous array sweeps.
• Single-Direction Navigation: You can only travel forward. If you are at Node C, there is no direct way to go back to Node B without starting over from the head. (For bi-directional travel, you would need to study a doubly linked list instead).

Basic Operations in a Singly Linked List

Writing code for linked list operations is a classic rite of passage in computer science. Let’s break down the logic of how we insert, delete, traverse, and search within a singly linked list.

Insertion

Adding an item to your list is all about updating pointer links. There are three main scenarios when you want to insert a node:

A. Insert at the Beginning (Prepend)

To insert a new node at the start of the list, we point the new node’s next pointer to the current head, and then update the head pointer to point to our new node.

$$\text{New Node’s Next} \leftarrow \text{Head}$$

$$\text{Head} \leftarrow \text{New Node}$$

This executes in $\mathcal{O}(1)$ time.

B. Insert at the End (Append)

To append, you must first traverse a linked list all the way to the end until you find the node whose next pointer is NULL. Once found, you update that last node’s next pointer to point to your newly created node. (Time Complexity: $\mathcal{O}(N)$).

C. Insert in the Middle

To insert after a specific target node, you point the new node’s next pointer to the target node’s current next node. Then, update the target node’s next to point directly to your new node.

Deletion

To delete a node, your goal is to disconnect the target node and route the chain safely around it to avoid a broken link.

A. Deleting the Head Node

This is simple: you create a temporary pointer to hold the current head, update the head pointer to point tohead -> next, and then safely delete/free the temporary pointer’s memory to avoid memory leaks.

B. Deleting a Middle Node

To delete Node B (which is between Node A and Node C), you must locate Node A (the predecessor). You update Node A’s next pointer to point directly to Node C (Node A->next = Node B->next). Finally, you delete Node B from memory.

Traversal

To traverse a linked list means to step through each node one by one. Here is the standard algorithm:

1. Initialize a temporary pointer temp to point to the head.
2. Run a loop that continues as long as temp is not equal to NULL.
3. Inside the loop, process the node’s data (e.g., print it).
4. Advance the pointer by reassigning it: temp = temp->next.

Searching

To search in a linked list for a specific target value:

1. Start traversal from the head node.
2. Compare the current node’s data with your target value.
3. If a match is found, return true or the node’s position.
4. If the current node is not a match, advance to the next.
5. If you hit NULL without finding a match, return false.

C++ Singly Linked List Implementation

Let’s look at complete C++ code for a singly linked list that demonstrates these basic operations in action. Writing singly linked list programs like this from scratch is the absolute best way to cement these concepts.

C++
#include <iostream>
 
// The foundational Node structure
struct Node {
    int data;
    Node* next;
 
    // Constructor to quickly initialize a node
    Node(int val) {
        data = val;
        next = nullptr;
    }
};
 
class SinglyLinkedList {
private:
    Node* head;
 
public:
    SinglyLinkedList() {
        head = nullptr;
    }
 
    // 1. Insertion: Prepend (Insert at beginning)
    void insertAtHead(int val) {
        Node* newNode = new Node(val);
        newNode->next = head;
        head = newNode;
    }
 
    // 2. Insertion: Append (Insert at the end)
    void insertAtTail(int val) {
        Node* newNode = new Node(val);
        if (head == nullptr) {
            head = newNode;
            return;
        }
        Node* temp = head;
        while (temp->next != nullptr) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
 
    // 3. Deletion: Delete node by value
    void deleteNode(int target) {
        if (head == nullptr) return; // Empty list
 
        // Case A: Deleting the head node
        if (head->data == target) {
            Node* temp = head;
            head = head->next;
            delete temp;
            return;
        }
 
        // Case B: Deleting a middle or end node
        Node* curr = head;
        Node* prev = nullptr;
        while (curr != nullptr && curr->data != target) {
            prev = curr;
            curr = curr->next;
        }
 
        if (curr == nullptr) return; // Target not found
 
        prev->next = curr->next;
        delete curr;
    }
 
    // 4. Searching: Find if a value exists
    bool search(int target) {
        Node* temp = head;
        while (temp != nullptr) {
            if (temp->data == target) return true;
            temp = temp->next;
        }
        return false;
    }
 
    // 5. Traversal: Print the list
    void display() {
        Node* temp = head;
        while (temp != nullptr) {
            std::cout << temp->data << " -> ";
            temp = temp->next;
        }
        std::cout << "NULL" << std::endl;
    }
};
 
int main() {
    SinglyLinkedList list;
 
    // Build the list
    list.insertAtTail(10);
    list.insertAtTail(20);
    list.insertAtTail(30);
    list.insertAtHead(5); // List: 5 -> 10 -> 20 -> 30 -> NULL
 
    std::cout << "Initial list: ";
    list.display();
 
    std::cout << "Searching for 20: " << (list.search(20) ? "Found" : "Not Found") << std::endl;
 
    list.deleteNode(10);
    std::cout << "List after deleting 10: ";
    list.display();
 
    return 0;
}

Note: If you are looking for classic C implementations, you can easily adapt this logic into a pure singly linked list code in C by using standard structures (struct Node) and swapping new/delete for standard malloc() and free() dynamic memory library functions.

Time Complexity of Singly Linked List

When analyzing Data Structures and Algorithms (DSA), evaluating complexity is critical. Here is how a singly linked list compares to standard arrays:

Applications of Singly Linked List

Singly linked lists are not just theoretical constructs; they are the underlying structural backbone for many critical computer components:

• Abstract Data Type Foundations: You can easily implement a stack or a queue where insertions and deletions strictly happen at the boundaries ($\mathcal{O}(1)$ operations).
• Undo/Redo States: Graphic editors or text processors often store operational histories in a sequential, pointer-based format.
• Playlist Management: Music players use basic list traversals to jump from one track to the next sequentially.
• Hash Table Collision Handling: Chaining, a common method to resolve collisions in hash tables, utilizes a linked list at each bucket index to store conflicting values.

Prep for Tech Interviews: Singly Linked List Practice Problems

If you are currently on the job hunt, you can practically guarantee that singly linked list interview questions will pop up during your technical screen. Coding interviews love pointer manipulation because it tests your mental visualization of memory.

Here are three high-yield singly linked list practice problems to solve:

1. Reverse a Singly Linked List: Reverse the direction of all pointers in-place, so that 1 -> 2 -> 3 -> NULL becomes 3 -> 2 -> 1 -> NULL. (Requires keeping track of three pointers: prev, curr, and next).
2. Detect a Cycle in a Linked List: Determine if a list contains a loop (i.e., a node pointing backward to an earlier node). This is classically solved using Floyd’s Cycle-Finding Algorithm (also known as the “Tortoise and Hare” algorithm).
3. Find the Middle Node: Find the exact middle node of a linked list in a single traversal pass. (Use a fast pointer moving two steps at a time, and a slow pointer moving one step at a time. When the fast pointer hits the end, the slow pointer will rest exactly in the middle).

Interactive Learning & Documentation Resources

To deepen your hands-on understanding of Singly Linked Lists, interactive visualizations and complete standard library documentation are excellent companions:

• Visualizing Pointer Transitions: Explore the step-by-step graphical node movements during insertion and deletion on the interactive VisuAlgo Linked List Simulator.
• Interactive Sandbox: Practice pointer logic and try solving linked list algorithms interactively in Python, Java, or C++ with online compilers on LeetCode’s Linked List Explore Card.
• Standard Implementations Reference: Learn how professional software development handles sequential containers by looking at the official cppreference documentation for std::forward_list, which is C++’s standard library implementation of a singly linked list.

Quick Summary / Key Takeaways

Before wrapping up, let’s highlight the most critical details you need to remember:

• A singly linked list is a dynamic, linear data structure where nodes point forward to their neighbor using a single next pointer.
• It excels at dynamic memory management, allowing lists to grow or shrink instantly without shifting elements or reallocating large contiguous blocks of memory.
• The primary drawback is its linear lookup time ($\mathcal{O}(N)$); you cannot jump straight to an index.
• It serves as the foundation for constructing other fundamental structures like stacks, queues, and hash table chains.

Conclusion

Mastering the singly linked list is your first major step in transitioning from a basic programmer to a true computer scientist. By learning to work directly with pointers and dynamic allocation, you build the core mental model required to learn more advanced structures like trees, graphs, and spatial indexes.

Now that you have got the basics down, you can keep learning data structures step by step. If you want to explore further, try reading up on a singly linked list vs. a doubly linked list comparison to see how adding a second “previous” pointer changes performance, or check out how a circular linked list loops back to the beginning to keep loops running indefinitely. Keep coding, experiment with pointer reassignments, and build things from scratch!

Related Blogs

What is DSA? Why Every Programmer Must Learn Data Structures and Algorithms

Time Complexity and Big O Notation Explained Like You’re 10 Years Old

Arrays in Data Structures: Complete Guide with Real-Life Examples

2D Arrays (Matrices) Explained: How to Store and Access Data

Doubly Linked List vs Circular Linked List: What’s the Difference?