Search code examples
c++classlinked-listiteratornodes

Insert node at specified custom class iterator position


I'm trying to insert a node at a specified position, the issue is that the insertion happens one position after where I want it. For example:

insert 100 at list.insert(list.begin()++, 100) in 1,2,3,4,5,6,7 results in:

1,2,100,3,4,5,6,7

I thought of decrementing the iterator, then inserting but that would be a workaround some flawed logic in my code but I cannot see where it is.

insert function

iterator insert(iterator position, const T& value) {

        Node* newNode = new Node(value);

        if (position == List<T>::iterator(head_)) {
            newNode->next_ = head_;
            head_ = newNode;
        }
        else if (!position.iNode->next_) {
            position.iNode->next_ = newNode;
        }
        else {

            Node* tmp = new Node(value);
            tmp->next_= position.iNode->next_;
            position.iNode->next_ = tmp;
        }

        return position;
    }

iterator class

class iterator
    {
    public:

        Node* iNode;
        iterator(Node* head): iNode(head){ }
        ~iterator() {}


        T& operator*() {
            return  iNode -> value_;
        }
    
        iterator& operator++() {
            iNode = iNode->next_;
            return *this;
        }

        iterator operator++(int ignored) {
            iNode = iNode->next_;
            return *this;
        }

        //! Is this iterator pointing at the same place as another one?
        bool operator== (const iterator& it) const {
            return this->iNode == it.iNode;
        }

        //! Is this iterator pointing at a different place from another?
        bool operator!= (const iterator& it) const {
            return this->iNode != it.iNode;
        }
    };

node class

class Node {
    public:
        Node(T value) : value_(value) {}

        T value_;
        Node* next_;
        Node* prev_;

        Node* head_;
        Node* tail_;
    };


Solution

  • The problem here in insert:

    iterator insert(iterator position, const T& value) {
    
            Node* newNode = new Node(value);
    
            if (position == List<T>::iterator(head_)) {
                newNode->next_ = head_;
                head_ = newNode;
            }
            else if (!position.iNode->next_) {
                position.iNode->next_ = newNode;
            }
            else {
                Node* curr = head_; 
                while (curr->next_ != position.iNode) 
                    {
                        curr = curr->next_;
                    }
    
                newNode->next_ = curr->next_;
                curr->next_ = newNode;
            }
    
            return position;
        }
    

    You insert a new node just after iterator position. But you need to insert it just before the new node.

    By the way, I tested it in my own List class. If something go wrong just add a comment to my post.

    Update: Actually, I fixed only part of the problem that time. Now the logic is:

    1. Iterate from head to node before the iterator.
    2. Connect new Node to the next of the node we iterated to in first step.
    3. Connect node we iterated to in first step to new Node.