The end iterator for a linked list

Question

I started to implement a list and got stuck at the end() iterator function. My understanding is that end() should point one element after the last member of the list. But since in a list elements are not contiguous in memory how can we point to one position after the last one?

And one extra question, how can we have operator--? If previous element points to current one, so current one do not have the knowledge about the previous.

#include <iostream>

template<typename T>
class Node
{
public:
    Node(const T _value) : value(_value) {}

    T value;
    std::shared_ptr<Node<T>> next = nullptr;
};

template<typename T>
class List
{
public:

    class Iterator
    {
    public:
        Iterator(std::shared_ptr<Node<T>> node) : m_node(node) {}

        T& operator*()
        {
            return m_node->value;
        }

    private:
        std::shared_ptr<Node<T>> m_node;
    };

    void insert_back(const T value)
    {
        auto node = std::make_shared<Node<T>>(value);

        if (!m_node)
            m_node = node;
        else
        {
            node->next = m_node;
            m_node = node;
        }
    }

    Iterator begin()
    {
        if (!m_node)
            return Iterator(nullptr);

        auto node = m_node;
        while(node->next)
            node = node->next;

        Iterator it(node);
        return it;
    }

    // Iterator end(){} // ?

private:
    std::shared_ptr<Node<T>> m_node = nullptr;
};

void test()
{
    List<int> list;

    list.insert_back(4);
    list.insert_back(2);

    auto beg = list.begin();
    std::cout << "beg is: " << *beg << std::endl;

    // auto end = list.end();
    // std::cout << "end is: " << *end << std::endl;
}

int main()
{
    std::cout << "starting..." << std::endl;

    test();

}

Answer 1

The end iterator should logically refer to "one past the end", but it doesn't have to physically refer to anything. The only requirement is that it compares equal to the iterator value you obtain by incrementing an iterator that refers to the last element of the list.

In the case of your List class, the last node in the list has a null next pointer, so when you increment an iterator to that node you'll end up with an iterator holding a null pointer. That means your end iterator can simply be

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

Answer 2

Presumably if you reach a nullptr you have reached the end of the list, so:

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

You probably also want Node to be inside of List as no user of List should need to directly create or modify a Node.

As a nitpick, m_node in List is probably better named head, head_node, or something to that effect.