Iterator while loop running extra loop

Question

I have a Doubly linked List class wherein i have a function which uses my classes iterators to loop over the collection. However in 1 specific place it runs for an extra loop and I cannot figure out why.

current merge template

template <typename T>
void DlList<T>::merge(SortedList& other) {  
    iterator it = back_->prev_;
    iterator oit = other.begin();   
    while (oit.current_->next_ != NULL) {
        std::cout << *it << "    " << *oit << std::endl;
        it.current_->next_ = oit.current_;
        back_->prev_ = oit.current_;
        //back_->prev_->next_ = back_;
        //other.back_->prev_ = other.back_->prev_->prev_;
        it++;
        oit++;
    }
}

It always iterates and extra time and added a null node to the list and I don't understand why.

Any insight is greatly appricicated!

Edit Added full project examples to explain intention of function I am working on a templated data structure class which is a doubly linked list which uses sentinel nodes. The list is sorted based on insert() and I am working on a merge function wherein the nodes of each list must be combined into this->list. The nodes must be moved and not have new ones created. and if the same value exists in both lists the other node value must come after the current node value.

I coded what I thought was a logical implementation however the output I get is not as expected and the results do not make sense to me, so if anyone could explain how i am getting the results I have it would be greatly appreciated.

Class Definition

class SortedList {
    struct Node {
        T data_;
        Node* next_;
        Node* prev_;
        Node(const T& data = T{}, Node* nx = nullptr, Node* pr = nullptr) {
            data_ = data;
            next_ = nx;
            prev_ = pr;
        }
    };
    Node* front_;
    Node* back_;

public:
    class const_iterator {
        friend class SortedList;
        Node* current_;
        const_iterator(Node* n)
        {
            current_ = n;
        }
    public:
        const_iterator() {
            //Set to safe state         
            current_ = nullptr;
        }
        const_iterator& operator++() {
            current_ = current_->next_;
            return *this;
        }
        const_iterator operator++(int) {
            const_iterator old = *this;
            current_ = current_->next_;
            return old;
        }
        const_iterator& operator--() {
            current_ = current_->prev_;
            return *this;
        }
        const_iterator operator--(int) {
            const_iterator old = *this;
            current_ = current_->prev_;
            return old;
        }
        bool operator==(const_iterator rhs) {
            return (current_ == rhs.current_) ? true : false;
        }
        bool operator!=(const_iterator rhs) {
            return !(*this == rhs);
        }
        bool operator>(const_iterator rhs) {
            return current_->data_ > rhs->current_->data_;
        }
        const T& operator*()const {
            return current_->data_;
        }
    };
    class iterator :public const_iterator {
        friend SortedList;
        iterator(Node* n) :const_iterator(n) {};
    public:
        iterator() : const_iterator() {};
        //prefix
        iterator& operator++() {
            this->current_ = this->current_->next_;
            return *this;
        }
        //post-fix
        iterator operator++(int) {
            iterator old = *this;
            this->current_ = this->current_->next_;
            return old;
        }
        iterator& operator--() {
            this->current_ = this->current_->prev_;
            return *this;
        }
        iterator operator--(int) {
            iterator old = *this;
            this->current_ = this->current_->prev_;
            return old;
        }
        T& operator*() {
            return this->current_->data_;
        }
        const T& operator*()const {
            return this->current_->data;
        }
    };
    SortedList();                                   //done
    ~SortedList();
    SortedList(const SortedList& rhs);
    SortedList& operator=(const SortedList& rhs);
    SortedList(SortedList&& rhs);
    SortedList& operator=(SortedList&& rhs);
    iterator begin() {
        return iterator(front_->next_);
    }
    iterator end() {
        return iterator(back_);
    }
    const_iterator cbegin() const {
        return const_iterator(front_->next_);
    }
    const_iterator cend() const {
        return const_iterator(back_);
    }
    iterator insert(const T& data);
    iterator search(const T& data);
    const_iterator search(const T& data) const;
    iterator erase(iterator it);
    void merge(SortedList& other);
    bool empty() const;
    int size() const;
};

first merge function attempt

template <typename T>
void SortedList<T>::merge(SortedList& other) {
    
    iterator it = this->begin();
    iterator oit = other.begin();
    while (oit !=  other.end()) {               
        std::cout << *oit << " " << *it << std::endl;
        if (*oit < *it) {
            oit.current_->prev_->next_ = oit.current_->next_;
            oit.current_->next_->prev_ = oit.current_->prev_;
            oit.current_->next_ = it.current_;
            oit.current_->prev_ = it.current_->prev_;
            it.current_->next_ = oit.current_;
        }
        else {
            oit.current_->prev_->next_ = oit.current_->next_;
            oit.current_->next_->prev_ = oit.current_->prev_;
            oit.current_->next_ = it.current_->next_;
            oit.current_->prev_ = it.current_;
            it.current_->prev_ = oit.current_;
        }
        oit++;
        it++;
    }
}

main tester

int main() {
    int num[] = { 3,5,1,2,6,8,9,11 };
    int num2[] = { 1,5,4,6,12,7,8,9 };

    SortedList<int> l;
    SortedList<int> l2;
    for (int i = 0; i < 8; i++)
    {
        l.insert(num[i]);
        l2.insert(num2[i]);
    }
     SortedList<int>::iterator result;
     SortedList<int>::iterator result2 = l2.begin();
     result = l.begin();
     while (result != l.end()) {
         std::cout << *result << "    " << *result2 << std::endl;
         ++result;
         ++result2;
     }
     l.merge(l2);

output

1    1
2    4
3    5
5    6
6    7
8    8
9    9
11    12

1 1
2 2
3 3
5 5
6 6
8 8
9 9
11 11
0 0

I dont understand why my second output is showing same the same values for *it and *oit I am pretty certain the error is in how I assign the the oit.current_->next & prev but i am unsure.

any insight is appriciated.

Answer 1

You seem to want to merge two sorted doubly linked lists together. There are several problems with your approach, and so I'll show you my code:

#include <iostream>
using namespace std;

struct node {
    node* next;
    node* prev;
    int val;
    
    node(int i_val)
      : next(nullptr),
        prev(nullptr),
        val(i_val)
    {}
};

void connect(node* a, node* b) {
    if (a != nullptr) {
        if (a->next != nullptr) {
            a->next->prev = nullptr;
        }
        a->next = b;
    }
    if (b != nullptr) {
        if (b->prev != nullptr) {
            b->prev->next = nullptr;
        }
        b->prev = a;
    }
}

struct DlList {
    node* first_node;
    node* last_node;
    
    DlList()
      : first_node(nullptr),
        last_node(nullptr)
    {}
    
    ~DlList() {
        for (node* n = first_node; n != nullptr; n = n->next) {
            delete n->prev;
        }
        delete last_node;
    }
    
    void push(int new_val) {
        node* new_node = new node(new_val);
        connect(last_node, new_node);
        last_node = new_node;
        if (first_node == nullptr) {
            first_node = new_node;
        }
    }
    
    void merge_sorted(DlList& other) {
        node* this_node = first_node;
        node* other_node = other.first_node;
        node* n = nullptr; // goes through each node of the new list in order
        while (this_node != nullptr || other_node != nullptr) {
            node* next_n;
            if (other_node == nullptr || 
                    (this_node != nullptr && this_node->val <= other_node->val)) {
                // entered if other_node is nullptr or this_node comes before other_node
                next_n = this_node;
                this_node = this_node->next;
            }
            else {
                // entered if this_node is nullptr or other_node comes before this_node
                next_n = other_node;
                other_node = other_node->next;
            }
            connect(n, next_n);
            if (n == nullptr) { // first time through loop
                first_node = next_n;
            }
            n = next_n;
        }
        last_node = n;
        
        // *this takes ownership of all of other's nodes
        other.first_node = nullptr;
        other.last_node = nullptr;
    }
};

int main() {
    std::cout << "running test" << std::endl;
    
    int num[] = { 1,2,3,5,6,8,9,11 };
    int num2[] = { 1,4,5,6,7,8,9,12 };

    DlList l;
    DlList l2;
    for (int i = 0; i < 8; i++)
    {
        l.push(num[i]);
        l2.push(num2[i]);
    }
    l.merge_sorted(l2);
    
    for (node* n = l.first_node; n != nullptr; n = n->next) {
        std::cout << n->val << " ";
    }
    std::cout << std::endl;
}

You may add iterators and other higher-level abstractions later, but for now I think they complicate and obscure the logic. I also did not see a need for a "past-the-end-of-the-list" node in your case, as nullptr would suffice. Though of course these could rather easily be added in if you wanted them to, just for demonstration purposes they are omitted.

Notice how I made a dedicated connect function that does all the pointer assignments as they should be done for two nodes. It handles a bunch of combinations of nullptr cases, too, so you don't need to worry as much about checking for null pointers outside of the function. (Note how the first time through the merge loop, a null n pointer is connected to next_n). Now you hardly need to worry about pointer assignments, and it's clearer when you just say, "connect these two nodes."

My merger function goes through each node in the newly created list. It picks the next node from the two available nodes, from *this and other. It then connects the current node to the next node, and advances the current node to the next node. It has special handling when one or the other of the lists runs out (this_node or other_node becomes nullptr), which indeed happens in the given test case. It takes care to assign first_node and last_node in the correct places, and to clear other after the merge, so as to prevent double ownership issues.