Building an STL-Compatible Linked List with Custom Iterators in C++

Introduction: Why Build Your Own Container?

In modern C++ development, the Standard Template Library (STL) provides powerful containers like std::list, std::vector, and std::map. But have you ever wondered how they work under the hood? In this tutorial, we'll build a simple_linked_list container from scratch, complete with custom iterators that integrate seamlessly with STL algorithms. By the end, you'll understand why iterator-based generic algorithms "just work" on any container that follows the STL conventions.

Think of it like building your own gaming leaderboard system. Just as a leaderboard needs to efficiently add players, remove them, and traverse rankings, our linked list needs to support insertion, deletion, and iteration. And just as a well-designed leaderboard API lets you sort players using any criteria, our iterator design will let us use std::sort, std::find, and other algorithms on our list.

The Anatomy of a Linked List Container

Before diving into code, let's understand the three key classes we'll implement:

• linked_node: The building block that stores a value and a pointer to the next node.
• simple_linked_list: The container that manages head and tail pointers, and exposes iterator-based methods.
• simple_linked_iterator: The iterator that knows how to traverse nodes and access data.

This structure mirrors what you'd find in a professional codebase. For example, in a mobile game's leaderboard system, each player entry is a node, the leaderboard itself is the container, and a cursor that moves through rankings is an iterator.

Implementing the Iterator

Let's start with the iterator because it's the heart of STL compatibility. Our iterator needs to support:

• Increment (both pre and post) to move to the next node.
• Dereference to access the node's data.
• Equality comparison to check if two iterators point to the same node.

Here's the implementation:

// simple_linked_iterator methods
simple_linked_iterator& operator++() { // preincrement
    pos = pos->next;
    return *this;
}

simple_linked_iterator operator++(int) { // postincrement
    simple_linked_iterator temp = *this;
    pos = pos->next;
    return temp;
}

T& operator*() {
    return pos->data;
}

bool operator==(const simple_linked_iterator& other) const {
    return pos == other.pos;
}

bool operator!=(const simple_linked_iterator& other) const {
    return !(*this == other);
}

Notice how preincrement returns a reference to itself (efficient), while postincrement returns a copy (preserving the old state). This is a common pattern in C++ iterators. The operator!= is optional but makes loop conditions cleaner.

Container Core Methods

Now let's implement the container itself. We'll start with the basics: empty check, size, front, back, and push_back.

bool empty() const {
    return head == nullptr;
}

std::size_t size() const {
    std::size_t count = 0;
    for (auto it = begin(); it != end(); ++it) {
        ++count;
    }
    return count;
}

T& front() {
    return head->data;
}

T& back() {
    return tail->data;
}

void push_back(const T& value) {
    auto* new_node = new linked_node(value);
    if (empty()) {
        head = tail = new_node;
    } else {
        tail->next = new_node;
        tail = new_node;
    }
}

The size() method uses our iterator to count elements. This is O(n) but demonstrates iterator usage. For a production list, you'd cache the size.

Range Constructor and Iterator Methods

The range constructor allows constructing a list from any iterator range, including arrays, vectors, or other lists.

template <typename ITERATOR>
simple_linked_list(ITERATOR first, ITERATOR last) : head(nullptr), tail(nullptr) {
    for (auto it = first; it != last; ++it) {
        push_back(*it);
    }
}

simple_linked_iterator begin() {
    return simple_linked_iterator(head);
}

simple_linked_iterator end() {
    return simple_linked_iterator(nullptr);
}

By convention, end() returns an iterator pointing one past the last element (nullptr in our case). This works seamlessly with algorithms like std::for_each.

Removing Elements: pop_back and clear

Implementing pop_back() requires finding the second-to-last node. With a singly linked list, we must traverse from the head.

void pop_back() {
    if (empty()) return;
    if (head == tail) { // only one node
        delete head;
        head = tail = nullptr;
        return;
    }
    // Find the node before tail
    auto* current = head;
    while (current->next != tail) {
        current = current->next;
    }
    delete tail;
    tail = current;
    tail->next = nullptr;
}

void clear() {
    while (!empty()) {
        pop_back();
    }
}

~simple_linked_list() {
    clear();
}

Notice the destructor calls clear() to avoid memory leaks. This is crucial for any container that manages dynamic memory.

Putting It All Together: STL Algorithms in Action

Once your container and iterator are complete, STL algorithms work out of the box. Here's an example using a gaming leaderboard scenario:

simple_linked_list<int> scores;
scores.push_back(1500);
scores.push_back(2300);
scores.push_back(1800);

// Use std::find to locate a score
auto it = std::find(scores.begin(), scores.end(), 1800);
if (it != scores.end()) {
    std::cout << "Found: " << *it << std::endl;
}

// Use std::sort to rank players (requires random-access, but for demonstration)
// std::sort(scores.begin(), scores.end()); // Not valid for forward iterators

// Use std::for_each to print all scores
std::for_each(scores.begin(), scores.end(), [](int s) {
    std::cout << s << " ";
});

Because our iterator is a forward iterator, algorithms that only require forward traversal (like std::find, std::count, std::for_each) work perfectly. Algorithms that require random access (like std::sort) won't compile, which is correct behavior.

Testing Your Implementation

Create a separate test file (not submitted) to verify each method. For example:

#include "simple_linked_list.h"
#include <algorithm>
#include <cassert>

int main() {
    simple_linked_list<int> list;
    assert(list.empty());
    
    list.push_back(10);
    list.push_back(20);
    assert(list.front() == 10);
    assert(list.back() == 20);
    assert(list.size() == 2);
    
    list.pop_back();
    assert(list.back() == 10);
    assert(list.size() == 1);
    
    list.clear();
    assert(list.empty());
    
    // Test range constructor
    int arr[] = {1,2,3};
    simple_linked_list<int> list2(arr, arr+3);
    assert(list2.size() == 3);
    
    // Test STL algorithm
    auto it = std::find(list2.begin(), list2.end(), 2);
    assert(it != list2.end());
    
    std::cout << "All tests passed!" << std::endl;
    return 0;
}

Remember to compile with g++ -std=c++17 -Wall -Wextra -o test test.cpp.

Common Pitfalls and Best Practices

1. Memory leaks: Always pair new with delete. Use the destructor to clean up.
2. Iterator invalidation: After modifying the container (e.g., pop_back), iterators pointing to removed nodes become invalid. Don't use them.
3. Const-correctness: Provide const versions of begin()/end() for const containers.
4. Rule of Five: Consider implementing copy constructor, copy assignment, move constructor, and move assignment to avoid shallow copies.

Conclusion

You've now implemented a fully functional STL-style linked list with custom iterators. The key takeaway is that by following the iterator conventions (increment, dereference, comparison), your container automatically gains compatibility with a vast library of algorithms. This is the power of generic programming in C++.

Whether you're building a game leaderboard, a music playlist, or an undo history, understanding how iterators work under the hood will make you a more confident C++ developer. Now go ahead and run those STL algorithms on your own container—they just work!