Implementing begin() and end() for doubly linked list

Question

I have written my own container class whose original internal data structure was the std::list. I then needed to create my own doubly linked list. I have now implemented my own doubly linked list as well as my own iterator for the linked list, but I'm having problems getting it to behave like std::list, particularly with begin() and end().

From what I understand, begin() should point the first node, and end() should point one element past the last element. I need to make sure that when I call end() that I can decrement back to the valid last element. I also need to make sure that I can do your normal traversals like...

while (beg != end ) { do something; beg++; }

Essentially my linked list just uses nodes that contain a data element, a pointer to the previous node and a pointer to the next node.

When I first tried to implement my end(), I just had the last node's next pointer be a nullptr. It works on its own but does not act the same way as the stl.

Any advice on how to implement the begin() and end() the same way the standard library does?

Answer 1

You could introduce a sentinel node and have a circular linked list.

A sketch:

class List
{
    private:
    struct Node {
        Node* previous;
        Node* next;

        Node() : previous(this), next(this) {}
    };

    struct DataNode : Node {
        int data;
    };

    public:
    class iterator
    {
        friend class List;

        private:
        iterator(Node* node) : m_node(node) {}

        public:
        iterator() : m_node(0) {}

        iterator& operator ++() {
            m_node = m_node->next;
            return *this;
        }

        int& operator * () {
            // Note: Dereferncing the end (sentinal node) is undefined behavior.
            return reinterpret_cast<DataNode*>(m_node)->data;
        }

        // More iterator functions.

        private:
        Node* m_node;
    };

    public:
    List() : m_sentinal(new Node) {}

    iterator begin() { return iterator(m_sentinal->next); }
    iterator end() { return iterator(m_sentinal); }

    iterator insert(iterator position, int data) {
        DataNode* data_node = new DataNode; // pass data
        Node* current = position.m_node;
        data_node->next = current;
        data_node->previous = current->previous;
        current->previous->next = data_node;
        current->previous = data_node;
        return iterator(current);
    }

    void append(int data) {
        insert(end(), data);
    }

    private:
    Node* m_sentinal;
};

Answer 2

Your end node cannot be null because you can't implement -- (going backwards) if all you have is null. You'll need to make a sentinel for the end node that at least knows how to get back to the last node in the list.

Answer 3

Your container should create a end node that is always available. This is what you will return from begin() when the container is empty. Your last real node should always set it's next node to this end node.