Simple Linked List in Cpp: Complete Solution & Deep Dive Guide

---

Mastering the C++ Simple Linked List: A Deep Dive for Developers

A C++ Simple Linked List is a fundamental linear data structure composed of nodes linked sequentially. Each node holds data and a pointer to the next node in the chain. This comprehensive guide explores its C++ implementation from scratch, covering node creation, push, pop, and reversal operations for practical applications.

You’ve just been tasked with a core feature for a new music streaming application: the playlist. Users need to add songs, remove them, and, most importantly, reorder them on the fly. You could start with a simple array or a std::vector, but you quickly realize the performance hit. Every time a user moves a song from the middle to the front, you'd have to shift every other element. This is inefficient and won't scale.

This is a classic computer science problem where a more dynamic data structure shines. Enter the singly linked list. It's a powerful tool that allows for constant-time insertions and deletions at the head, making it perfect for dynamic collections like playlists, task queues, or undo/redo stacks. This guide will walk you through building a simple linked list in C++ from the ground up, using the music player playlist as our practical example.

---

What Exactly Is a Simple Linked List?

A simple (or singly) linked list is a linear data structure, but unlike an array, its elements are not stored at contiguous memory locations. Instead, elements are linked using pointers. It's a chain of nodes, where each node is a small, independent object containing two key pieces of information:

• Data: The actual value stored in the node (in our case, a song ID represented as an integer).
• Next Pointer: A pointer that stores the memory address of the very next node in the sequence. The last node's "next" pointer points to nullptr, signifying the end of the list.

The entire list is accessed through a single pointer, typically called the head, which points to the very first node in the chain. If the head is nullptr, the list is empty.

This structure is incredibly flexible. To add a new song to the beginning of our playlist, we just create a new node, make it point to the current head, and then update the head to be our new node. No data shifting required.

Visualizing the Structure

Here is a conceptual diagram of a linked list containing three song IDs: 101, 205, and 317. The head pointer gives us the entry point to the entire playlist.

  ● head
  │
  ▼
┌───────────┐      ┌───────────┐      ┌───────────┐
│ Data: 101 │──────│ Data: 205 │──────│ Data: 317 │
│ next:  ───┼─────→│ next:  ───┼─────→│ next:  ───┼──→ ● nullptr
└───────────┘      └───────────┘      └───────────┘

---

Why Use a Linked List Over a Vector or Array?

Choosing the right data structure is critical for writing efficient and scalable code. While C++'s std::vector is a fantastic general-purpose container, linked lists offer distinct advantages in specific scenarios. The decision hinges on your primary use case: do you need fast random access, or do you need fast insertions and deletions?

An array or std::vector stores its elements in a contiguous block of memory. This is great for cache performance and allows for O(1) random access—you can jump to any element instantly using its index. However, inserting or deleting an element in the middle or at the beginning is an O(n) operation because all subsequent elements must be shifted.

A linked list, with its nodes scattered across memory, excels where vectors struggle. Inserting a new element at the beginning (a push operation) is O(1). You just adjust a couple of pointers. Deleting the first element (a pop operation) is also O(1). This makes it ideal for implementing stacks and queues.

Here’s a breakdown of the trade-offs:

Pros & Cons: Linked List vs. Array/Vector

Feature	Singly Linked List	Array / std::vector
Insertion/Deletion (at Head)	Excellent (O(1))	Poor (O(n) - requires shifting)
Element Access (Random)	Poor (O(n) - requires traversal from head)	Excellent (O(1) - direct index access)
Memory Allocation	Non-contiguous. Nodes can be anywhere in memory.	Contiguous block of memory.
Memory Overhead	Higher. Each node stores an extra pointer.	Lower. Minimal overhead per element.
Dynamic Sizing	Highly efficient. Grows and shrinks node by node.	Efficient, but may require reallocating the entire block and copying elements.
Cache Locality	Poor. Nodes can be far apart, leading to cache misses.	Excellent. Sequential access is very fast.

---

How to Implement a Simple Linked List in C++

Let's build our music player's playlist feature. The core requirements from the kodikra learning path are to create a list from a range of song IDs, add songs (push), remove them (pop), and reverse the playlist. We will implement this using raw pointers to solidify our understanding of memory management.

Our implementation will consist of two main parts: the Element struct, which represents a single song (a node), and the List class, which manages the entire collection of nodes.

The Core C++ Code Structure

Here is the complete header file (simple_linked_list.h) that defines the interface for our List and its internal Element.

#pragma once

#include <vector>
#include <cstddef>

namespace simple_linked_list {

struct Element {
    int data{};
    Element* next{};
};

class List {
public:
    List() = default;
    ~List();

    // Disable copy and assignment for simplicity
    List(const List& other) = delete;
    List& operator=(const List& other) = delete;

    std::size_t size() const;
    void push(int entry);
    int pop();
    Element* head() const;
    void reverse();

    // Helper constructor to create a list from a vector
    List(const std::vector<int>& values);

private:
    Element* head_ = nullptr;
    std::size_t current_size = 0;
};

} // namespace simple_linked_list

Now, let's dive into the implementation file (simple_linked_list.cpp) and break down each method line by line.

1. The `Element` Struct

This is our node. It's a simple C-style struct containing the song ID (data) and a pointer to the next Element. We initialize next to nullptr by default to ensure that a newly created node doesn't point to random memory.

2. The `List` Class and its Destructor `~List()`

The List class encapsulates the entire logic. It holds the head_ pointer, which is our only entry point into the list, and a current_size member for O(1) size checks.

#include <stdexcept>
#include "simple_linked_list.h"

namespace simple_linked_list {

List::~List() {
    while (head_ != nullptr) {
        Element* next_node = head_->next;
        delete head_;
        head_ = next_node;
    }
}

Code Walkthrough:

• List::~List(): This is the destructor. It's one of the most critical pieces of code when dealing with manual memory management.
• while (head_ != nullptr): The loop continues as long as the list is not empty.
• Element* next_node = head_->next;: Before we delete the current head, we must save the address of the *next* node. If we don't, we lose our link to the rest of the list.
• delete head_;: This deallocates the memory occupied by the current head node, preventing a memory leak.
• head_ = next_node;: We then update the head_ to point to the next node we saved. The loop repeats, effectively walking down the list and deleting one node at a time until it's empty.

3. The `size()` Method

A straightforward getter method that returns the current size of the list. By maintaining a current_size counter, we make this an O(1) operation.

std::size_t List::size() const {
    return current_size;
}

4. The `push()` Method: Adding a Song

This method adds a new song to the *front* of the playlist. This is the classic linked list insertion operation.

void List::push(int entry) {
    auto new_element = new Element{entry, head_};
    head_ = new_element;
    current_size++;
}

Code Walkthrough:

• auto new_element = new Element{entry, head_};: This is the core of the operation.
  • new Element: We allocate memory for a new node on the heap.
  • {entry, head_}: We use aggregate initialization. The first value, entry, initializes the data member. The second value, head_, initializes the next pointer of our new node. This means the new node's next pointer now points to what *used to be* the first node in the list.
• head_ = new_element;: We update the list's head_ pointer to point to our newly created node, officially making it the new front of the list.
• current_size++;: We increment our size counter.

5. The `pop()` Method: Removing a Song

This method removes the song from the front of the playlist and returns its ID. It's the inverse of push.

int List::pop() {
    if (head_ == nullptr) {
        throw std::out_of_range("Cannot pop from an empty list.");
    }

    int popped_data = head_->data;
    Element* old_head = head_;
    head_ = head_->next;
    
    delete old_head;
    current_size--;
    
    return popped_data;
}

Code Walkthrough:

• if (head_ == nullptr): First, a sanity check. We can't remove an element from an empty list, so we throw an exception.
• int popped_data = head_->data;: We save the data from the head node so we can return it later.
• Element* old_head = head_;: We create a temporary pointer to the current head. We need this to deallocate its memory after we've updated the list's structure.
• head_ = head_->next;: We update the list's head_ to point to the second element, effectively "decapitating" the list.
• delete old_head;: Now we can safely deallocate the memory of the original head node using our temporary pointer.
• current_size--;: We decrement the size.
• return popped_data;: We return the song ID we saved.

6. The `reverse()` Method: Reversing the Playlist

This is a classic linked list algorithm. To reverse the list in-place, we iterate through it and reverse the direction of the next pointers one by one. This requires three pointers: one for the current node, one for the previous node, and one to temporarily store the next node.

void List::reverse() {
    Element* current = head_;
    Element* prev = nullptr;
    Element* next = nullptr;

    while (current != nullptr) {
        // Store the next node before we overwrite the pointer
        next = current->next;
        
        // The actual reversal: current node now points backward
        current->next = prev;
        
        // Move pointers one position forward for the next iteration
        prev = current;
        current = next;
    }
    
    // The old tail (prev) is now the new head
    head_ = prev;
}

Code Walkthrough & Visualization:

Imagine our list is `1 -> 2 -> 3 -> nullptr`. Let's trace the pointers.

Initial State:
  prev = nullptr
  current = Node(1)
  next = nullptr

Iteration 1:
  1. next = current->next      // next points to Node(2)
  2. current->next = prev      // Node(1) now points to nullptr
  3. prev = current            // prev points to Node(1)
  4. current = next            // current points to Node(2)
  State: nullptr <- 1   2 -> 3

Iteration 2:
  1. next = current->next      // next points to Node(3)
  2. current->next = prev      // Node(2) now points to Node(1)
  3. prev = current            // prev points to Node(2)
  4. current = next            // current points to Node(3)
  State: nullptr <- 1 <- 2   3

Iteration 3:
  1. next = current->next      // next points to nullptr
  2. current->next = prev      // Node(3) now points to Node(2)
  3. prev = current            // prev points to Node(3)
  4. current = next            // current becomes nullptr, loop terminates
  State: nullptr <- 1 <- 2 <- 3

Final Step:
  head_ = prev;                // head_ is updated to point to Node(3)

This logic is elegantly captured in the following flow diagram:

    ● Start (current = head, prev = nullptr)
    │
    ▼
  ┌─────────────────┐
  │ Is current null?│
  └────────┬────────┘
           │ No
           ▼
┌──────────────────────────┐
│ 1. Save next node        │
│    (next = current->next)│
└────────────┬─────────────┘
             │
             ▼
┌──────────────────────────┐
│ 2. Reverse pointer       │
│    (current->next = prev)│
└────────────┬─────────────┘
             │
             ▼
┌──────────────────────────┐
│ 3. Advance prev pointer  │
│    (prev = current)      │
└────────────┬─────────────┘
             │
             ▼
┌──────────────────────────┐
│ 4. Advance current pointer│
│    (current = next)      │
└────────────┬─────────────┘
             │
             └───────────┐
                         ▼
┌─────────────────┐ ─────┘
│ Is current null?│
└────────┬────────┘
         │ Yes
         ▼
┌──────────────────────────┐
│ Update head (head = prev)│
└──────────────────────────┘
             │
             ▼
           ● End

---

Future-Proofing: A Modern C++ Approach with Smart Pointers

While the manual memory management with new and delete is an excellent learning exercise from the kodikra.com curriculum, modern C++ offers safer, more robust tools: smart pointers. Using std::unique_ptr automates memory deallocation, preventing common errors like memory leaks and making the code easier to reason about.

A std::unique_ptr is a smart pointer that owns and manages another object through a pointer and disposes of that object when the unique_ptr goes out of scope. It ensures exclusive ownership.

Here’s how our Element struct and List class would look using std::unique_ptr:

#include <memory> // Required for std::unique_ptr

// Modern Element struct
struct Element {
    int data{};
    std::unique_ptr<Element> next{};
};

// Modern List class
class List {
public:
    // The destructor ~List() is now automatically handled by unique_ptr!
    // We can just use the default.

    void push(int entry) {
        auto new_element = std::make_unique<Element>();
        new_element->data = entry;
        new_element->next = std::move(head_); // Transfer ownership of old head
        head_ = std::move(new_element);       // Transfer ownership of new node
        current_size++;
    }

    int pop() {
        if (!head_) {
            throw std::out_of_range("List is empty.");
        }
        int popped_data = head_->data;
        // Ownership of the rest of the list is transferred to a temporary
        auto old_head_next = std::move(head_->next);
        // The old head is destroyed when this function returns.
        // We move the rest of the list back into head_.
        head_ = std::move(old_head_next);
        current_size--;
        return popped_data;
    }

    // ... other methods ...

private:
    std::unique_ptr<Element> head_ = nullptr;
    std::size_t current_size = 0;
};

Key changes:

• No Manual delete: The destructor ~List() is no longer needed. When the List object is destroyed, its head_ member (a unique_ptr) is also destroyed. This triggers a chain reaction, where each unique_ptr in the list destroys the next, safely deallocating all memory.
• std::move: Since unique_ptr enforces exclusive ownership, we cannot simply copy it. We must explicitly transfer ownership using std::move.
• RAII Principle: This design follows the Resource Acquisition Is Initialization (RAII) principle, a cornerstone of modern C++ that ties the lifetime of a resource to the lifetime of an object.

---

Where Are Linked Lists Used in the Real World?

Beyond our music player example, linked lists are foundational in many areas of software engineering:

• Implementing Other Data Structures: They are the building blocks for stacks, queues, and hash maps (for handling hash collisions through chaining).
• Operating Systems: OS schedulers often use linked lists to manage queues of processes waiting for the CPU. Memory management systems can use them to keep track of free blocks of memory.
• Browser History: The "back" and "forward" buttons in a web browser can be implemented using a doubly linked list, where each node represents a visited page.
• Graphs: Adjacency lists, a common way to represent graphs, use an array of linked lists where each list stores the neighbors of a vertex.
• Undo/Redo Functionality: Applications like text editors use a list-like structure to store a sequence of commands, allowing the user to easily undo or redo actions.

---

Frequently Asked Questions (FAQ)

What is the difference between a singly and a doubly linked list?

A singly linked list has nodes with only one pointer, pointing to the next node. A doubly linked list has nodes with two pointers: one to the next node and another to the previous node. This allows for traversal in both directions but comes at the cost of extra memory per node and more complex insertion/deletion logic.

Why is random access O(n) in a linked list?

Because nodes are not in contiguous memory, you cannot calculate the memory address of the Nth element from the start. To find the Nth element, you must start at the head and traverse the list one node at a time, following the next pointers N times. This makes the operation's time complexity directly proportional to the size of the list (n).

What is a memory leak in the context of this C++ linked list?

A memory leak occurs if we allocate memory using new but fail to deallocate it with delete. In our manual implementation, if we forgot to write the destructor ~List(), every node created would remain in memory even after the List object was destroyed, consuming resources indefinitely.

How does std::list in the C++ STL differ from this simple implementation?

std::list is a highly optimized, production-ready implementation of a doubly linked list. It provides a rich API with iterators, allocators, and numerous helper functions (like sort, merge, splice). Our simple list is a singly linked list built for educational purposes to understand the core mechanics.

Is a linked list better than a std::vector?

Neither is universally "better." The choice depends entirely on the access patterns of your application. Use std::vector as the default choice due to its excellent performance for iteration and random access. Choose a linked list (or std::list) only when you have a clear need for frequent, fast insertions and deletions at arbitrary points in the sequence and do not require random access.

Can a linked list be circular?

Yes. A circular linked list is a variation where the next pointer of the last node points back to the head node instead of nullptr. This creates a continuous loop, which is useful for applications like round-robin scheduling or managing a buffer that wraps around.

---

Conclusion: The Power of Pointers and Structure

The simple linked list is more than just an academic exercise; it's a testament to the power of pointers and custom data structures. By building one from scratch, we gain a deep appreciation for memory management, algorithmic complexity, and the trade-offs inherent in software design. We've seen how its dynamic nature provides a perfect solution for our music playlist problem, offering performance benefits that arrays cannot match.

While modern C++ provides safer abstractions like std::unique_ptr and robust containers like std::list, understanding the manual, low-level implementation is a rite of passage for any serious C++ developer. It equips you with the knowledge to debug complex memory issues and make informed decisions about which data structure is right for the job.

Disclaimer: All code examples are based on the C++17 standard. The modern C++ approach using smart pointers is generally recommended for production code to ensure memory safety and maintainability.

Ready to master more fundamental concepts? Explore our complete C++ learning path on kodikra.com or advance to the next challenge in the Data Structures and Algorithms roadmap.

---

Published by Kodikra — Your trusted Cpp learning resource.