Geek asks and answers

Implementation of begin () and end () for a doubly linked list

I wrote my own container class whose original internal data structure was std::list. Then I needed to create my own double list. I have now implemented my own double-linked list, as well as my own iterator for the linked list, but I am having problems making it behave like std::list, especially with begin()and end().

From what I understand, the begin()first node end()should indicate , and should indicate one element after the last element. I need to make sure that when I call end(), I can return to the actual last element. I also need to make sure that I can do your usual workarounds, for example ...

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

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

When I first tried to implement mine end(), I had only the last node, the next pointer be a nullptr. It works on its own, but does not act like stl.

Any tips on how to implement begin()and end()just like the standard library does?

+3
source share
3 answers

You can enter a sentinel node and have a circular linked list.

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;
};
+5
source

node, . , begin(), . node node node.

+1

Your end node cannot be null, because you cannot implement --(backward) if everything you have is null. You need to make a node end lookout code that at least knows how to return to the last node in the list.

+1
source

More articles:


All Articles