Assignment Operator not working properly in circular doubly linked list

Question

I'm doing a doubly linked list with a sentinel node that makes the doubly linked list a circular list (there is no head and no tail pointers to the front and back, instead head is referred to by m_sentinel->m_next and tail is referred to by m_sentinel->m_prev). Here is the following code:

In MyList.h:

template <typename T>
class Node
{
    public:
        T m_element;

        Node<T> *m_prev;
        Node<T> *m_next;

        // Helps make a dummy/sentinel/junk node
        Node(Node<T> *in_prev, Node<T> *in_next): 
            m_prev(in_prev), m_next(in_next){}

        Node(const T &x, Node<T> *in_prev, Node<T> *in_next): 
            m_element(x), m_prev(in_prev), m_next(in_next){}
};

template <typename T>
class MyList
{
    private:
        Node<T> *m_sentinel = nullptr;

        int m_size;

    public:
        MyList();

        ~MyList();

        MyList<T> & operator=(const MyList<T> &source);

        void clear();

        void push_back(const T &x);

In MyList.hpp:

template <typename T>
MyList<T>::MyList()
{
  m_size = 0;
  m_sentinel = new Node<T>(NULL, NULL);
}

template <typename T>
MyList<T>::~MyList()
{
  clear();

  m_size = 0;
}

template <typename T>
MyList<T> & MyList<T>::operator=(const MyList<T> &source)
{
  if(this == &source)
  {
    return *this;
  }
  while(source.m_sentinel->m_next != source.m_sentinel)
  {
    Node<T> *temp = source.m_sentinel->m_next;
    push_back(temp->m_element);
    source.m_sentinel->m_next = temp->m_next;
  }

  return *this;
}

template <typename T>
void MyList<T>::clear()
{
  if(m_sentinel->m_prev == NULL && m_sentinel->m_next == NULL)
  {
    delete m_sentinel;
  }
  else
  {
    int k = size();
    for(int i = 0; i < k; i++)
    {
      pop_back();
    }
    delete m_sentinel;
  }
}

template <typename T>
void MyList<T>::push_back(const T &x)
{
  Node<T> *newNode;
  newNode = new Node<T>(x, NULL, NULL);
  if(m_sentinel->m_prev == NULL && m_sentinel->m_next == NULL)
  {
    newNode->m_prev = m_sentinel;
    newNode->m_next = m_sentinel;
    m_sentinel->m_prev = newNode;
    m_sentinel->m_next = newNode;
  }
  else
  {
    newNode->m_next = m_sentinel;
    newNode->m_prev = m_sentinel->m_prev;
    Node<T> *temp = newNode->m_prev;
    m_sentinel->m_prev = newNode;
    temp->m_next = m_sentinel->m_prev;
  }
  m_size++;
}

In main.cpp:

#include "MyList.h"

int main()
{
    MyList<int> x;
    x.push_front(1);
    x.push_front(2);
    x.push_front(3);
    x.push_front(4);
    x.push_front(5);
    x.push_front(6);
    x.push_front(7);
    MyList<int> p;
    p = x; 

    // Below just outputs each linked list
    int j = 0;
    int m = x.size();
    cout << endl << endl;
    for(auto i = 0; i < m; i++)
    {
        cout << x.front() << endl;
        x.pop_front();
        j++;
    }
    cout << endl << endl;
    j = 0;
    m = p.size();
    for(auto i = 0; i < m; i++)
    {
        cout << p.front() << endl;
        p.pop_front();
        j++;
    }
    cout << endl << endl;

When running this code, x does get copied to p successfully. When outputting p, the following output is given: 7 6 5 4 3 2 1, but when outputting x, the following output is given: -19823746 ... which is just junk memory values (which tells me x is being changed obviously, but p is successfully getting x's contents). I have no clue why it's changing; I'm looking for a fix/solution to the assignment operator because it's not working properly.

Where is your user-defined copy constructor? Even if you got the assignment operator to work, your class is still broken, and broken very easily by doing `MyList p = x;` in the `main` function. Read up on [the rule of three](https://stackoverflow.com/questions/4172722/what-is-the-rule-of-three) — PaulMcKenzie, Mar 14 '20 at 21:24
I was going to work on the copy constructor after the assignment operator - bad idea? I'll check that link out though, thanks! — bmcisme, Mar 14 '20 at 21:27
The best way is to work on the copy constructor and destructor first. Leave the assignment operator alone. Then when you can get copy constructor and destructor working properly, then the assignment operator takes about two minutes to code up correctly using the [copy / swap](https://stackoverflow.com/questions/3279543/what-is-the-copy-and-swap-idiom) idiom. — PaulMcKenzie, Mar 14 '20 at 21:31
`{MyList t = source; std::swap(t.m_size, m_size); std::swap(t.m_sentinel, m_sentinel); return *this;}` -- Believe it or not, that would be the assignment operator **if** you had written the copy constructor and destructor first. — PaulMcKenzie, Mar 14 '20 at 21:36
Well unfortunately I can't use the swap/copy functions for the stl library since this is a coding assignment. I have the destructor done but not the copy constructor, that'll be what I work on now then. — bmcisme, Mar 14 '20 at 21:39
Then just swap the items yourself. That is all that `std::swap` is doing. Please read the link about copy and swap. All you're doing would be to swap out the temporary variables contents with the current contents, and let the temporary die off. — PaulMcKenzie, Mar 14 '20 at 21:42

David G · Answer 1 · 2020-03-14T22:10:56.317

1

Inside of your MyList::operator= you should be iterating with a new variable, not the source.m_sentinel member itself. This changes the actual list and is actually removing nodes.

Use this instead:

Node<T>* current = source.m_sentinel;
while (current->m_next != source.m_sentinel) {
  Node<T>* temp = current->m_next;
  push_back(temp->m_element);
  current = temp;
}

edited Mar 14 '20 at 22:10

answered Mar 14 '20 at 21:15

David G

94,763
41
167
253

I tried doing this and I get the error: 'terminate called after throwing an isntance of 'St9bad_alloc' what(): std::bad_alloc Aborted (core dumped) – bmcisme Mar 14 '20 at 21:37
Here's the current function just for clarity: ``template MyList & MyList::operator=(const MyList &source) { if(this == &source) { return *this; } Node* current = source.m_sentinel; while(current->m_next != source.m_sentinel) { Node* temp = current->m_next; push_back(temp->m_element); current = temp->m_next; } return *this; }` ``` – bmcisme Mar 14 '20 at 21:38
@bmcisme Use your debugger and trace where the error is coming from. The code I wrote looks correct so it may not be coming from my example... – David G Mar 14 '20 at 21:56
@bmcisme Try changing `current = temp->m_next` to `current = temp` (from my example) and see what happens. – David G Mar 14 '20 at 22:11

Assignment Operator not working properly in circular doubly linked list

1 Answers1