Linked List Iterator Implementation C++

Question

I've created a Linked List in C++ and want to implement an iterator for it so that I can do range loops: for (const int& i : list) where Linked_List<int> list;.

My idea is to create the Iterator as part of the Linked_List class like this:

This is what I got so far:

template <typename T>
class Linked_List
{
public:
    struct Iterator;
    struct Node;
public:
    Linked_List();
    ~Linked_List() noexcept(false);
    Linked_List(const Linked_List&) = delete;
    Linked_List(Linked_List&&) = delete;
    Linked_List& operator=(const Linked_List&) = delete;
    Linked_List& operator=(Linked_List&&) = delete;

    void push_back(T);
    void push_front(T);
    void pop_back();
    void pop_front();
    bool empty() const;
    T back() const;
    T front() const;
    //void swap(T, T);
    //void insert(Iterator, T);
    //void erase(Iterator);
    //Iterator begin() const;
    //Iterator end() const;
private:
    Node* head;
    Node* tail;
};

template<typename T>
struct Linked_List<T>::Node
{
    Node() : prev(nullptr), next(nullptr) {}
    Node(T t) : value(t), prev(nullptr), next(nullptr) {}
    Node* prev;
    Node* next;
    T value;
};

1. Is this a good approach?
2. Should I do error checking when incrementing the list to check if current->next == tail? If so, how do I do that? Because my Iterator doesn't have a list object with a tail.

Edit: I'm not sure how to implement the struct Iterator;, I get stuck when figuring out how to connect it with the list so that I can check if the current node returned from the iterator equals the tail in the list, in the Linked_List Iterator end() const method.

Let's say I've implemented all the necessary operators for an iterator like this:

struct Iterator
{
    T& operator*() const { return current->value; }
    bool operator!=(const Iterator& rhs) { return (*_current != rhs._current); }
    Iterator& operator++()
    {
        current = current->next;
        return *this;
    }
};

How would I go about implementing Iterator Linked_List<T>::begin() const; and end() now?

I imagine an imaginary user making an iterator object like this: Linked_List<int>::Iterator it;

An idea is to have a public constructor with no parameters and a private constructor that takes a node as a parameter which _current will be set to, and have the Linked_List class as a friend.

Answer 1

A few notes.

There are two options where to declare Node and Iterator. Inside the list class as List<T>::Node or outside as Node<T>. It is, in part, a matter of taste. From engineering perspective though, the symbol names are longer for nested classes, so your debuginfo is bigger. Also, when nested classes are also templates it is harder to specialize them if/when necessary (because that requires fully specializing the enclosing template first), but this is not the case here.

It leads to more elegant code when one list node is used as list head and tail. Empty list is a node whose next and prev point to itself. push_front appends to list.next which points to the first node or itself. push_back appends a node to list.prev which points to the last node or itself. When inserting/removing nodes there is no need to have special handling of the first and last nodes. E.g. :

struct Node {
    Node *next_, *prev_;

    Node() 
        : next_(this), prev_(this)
    {}

    ~Node() { 
        unlink();
    }

    void push_back(Node* n) {
        n->next_ = this;
        n->prev_ = prev_;
        prev_->next_ = n;
        prev_ = n;
    }

    void unlink() {
        Node *next = next_, *prev = prev_;
        next->prev_ = prev;
        prev->next_ = next;
        next_ = this;
        prev_ = this;
    }
};

In the above, Node only needs two operations to be able to maintain a list. More than that, Node is itself a minimalist list that can be used for intrusive lists (with auto-unlink in the destructor). Note how using this makes checks for nullptr unnecessary - Node is always a valid list.

Error checking should be in debug mode only (use assert, for example). Otherwise, those checks penalise correct applications with unnecessary run-time checks.

---

Here is a minimal working example based on the ideas for you:

template<class T>
class List;

class Iterator;

class Node {
    friend class Iterator;
    template<class T> friend class List;

protected:
    Node *next_, *prev_;

    void push_back(Node* n) {
        n->next_ = this;
        n->prev_ = prev_;
        prev_->next_ = n;
        prev_ = n;
    }

    void unlink() {
        Node *next = next_, *prev = prev_;
        next->prev_ = prev;
        prev->next_ = next;
        next_ = this;
        prev_ = this;
    }

public:
    Node()
        : next_(this), prev_(this)
    {}

    ~Node() { unlink(); }
};

class Iterator {
protected:
    Node* node_;

    Iterator(Node* node)
        : node_(node)
    {}

public:
    Iterator& operator++() {
        node_ = node_->next_;
        return *this;
    }

    bool operator==(Iterator b) const { return node_ == b.node_; }
    bool operator!=(Iterator b) const { return node_ != b.node_; }

    // Implement the rest of iterator interface.
};

template<class T>
class List {
    class NodeT : public Node {
        friend class List<T>;
        T value_;
        NodeT(T t) : value_(t) {}
    };

    template<class U>
    class IteratorT : public Iterator {
        friend class List<T>;
        NodeT* node() const { return static_cast<NodeT*>(node_); }
    public:
        U& operator*() const { return node()->value_; }
        U* operator->() const { return &node()->value_; }
        operator IteratorT<U const>() const { return node_; } // iterator to const_iterator conversion
        IteratorT(Node* node) : Iterator{node} {}
    };

    Node list_;

public:
    using iterator = IteratorT<T>;
    using const_iterator = IteratorT<T const>;

    ~List() { clear(); }

    bool empty() const { return list_.next_ == &list_; }

    iterator begin() { return list_.next_; }
    iterator end() { return &list_; }

    void push_back(T t) { list_.push_back(new NodeT(t)); }
    void erase(const_iterator i) { delete i.node(); }

    void clear() {
        while(!empty())
            erase(begin());
    }

    // Implement the rest of the functionality.
};

int main() {
    List<int> l;
    l.push_back(1);
    l.push_back(2);
    l.push_back(3);
    for(auto elem : l)
        std::cout << elem << ' ';
    std::cout << '\n';
}