How do I Implement the Big Three Correctly: Singly Linked List (C++)

Question

I am writing a program that contains a singly linked list to hold a shopping list. Each node has the item name, quantity, and quantity description (i.e. dozen for eggs). Everything works find in the program except the destructor. I can't seem to find what is wrong with it though.

The driver will execute to the end where the code is return 0;, then the destructor is called and stops on the line delete current; with the message:

"Unhandled exception at 0x0FC7A9E8 (msvcr120d.dll) in Project 14.exe: 0xC0000005: Access violation reading location 0xFEEEFEE2.".

I've posted the implementation for the big three functions below. The default constructor initializes both pointers (first, last) as null and the nodeCount as 0.

I can't seem to find the problem. Any help?

List::List(const List& b)
{
    Node* newNodePtr = new Node;
    Node* nodeCopy = b.first;
    newNodePtr = nodeCopy;
    first = newNodePtr;
    last = newNodePtr;
    nodeCount++;
    nodeCopy = nodeCopy->getNext();
    while (last != b.last)
    {
        Node* newNode = new Node;
        newNode = nodeCopy;
        Node* currentNode = last;
        currentNode->setNext(newNode);
        last = newNode;
        nodeCount++;
        nodeCopy = nodeCopy->getNext();
    }
}

List::~List()
{
    Node* current = first;
    while (current != nullptr)
    {
        Node* _next = current->getNext();
        delete current;
        current = _next;
    }
    first = nullptr;
    last = nullptr;
}

List& List::operator=(const List& rho)
{
    Node* current = first;
    while (current != nullptr)
    {
        Node* _next = current->getNext();
        delete current;
        current = _next;
    }
    first = nullptr;
    last = nullptr;

    Node* newNodePtr = new Node;
    Node* nodeCopy = rho.first;
    newNodePtr = nodeCopy;
    first = newNodePtr;
    last = newNodePtr;
    nodeCount++;
    nodeCopy = nodeCopy->getNext();
    while (last != rho.last)
    {
        Node* newNode = new Node;
        newNode = nodeCopy;
        Node* currentNode = last;
        currentNode->setNext(newNode);
        last = newNode;
        nodeCount++;
        nodeCopy = nodeCopy->getNext();
    }
    return *this;
}

EDIT: I've also added my push_back function as it is written:

void List::push_back(Node* newNode)
{
if (first == nullptr)
{
    first = newNode;
    last = newNode;
}
else
{
    Node* currentNode = last;
    currentNode->setNext(newNode);
    last = newNode;
}
nodeCount++;
}

Alright I think I've figured in out. This code seems to work and it fits the driver provided by my professor. Below I've included the big three functions and all of the other functions they call:

List::List(const List& b)
{
    this->copyList(b);
}

List::~List()
{
    this->clearList();
}

List& List::operator=(const List& rho)
{
    this->clearList();
    this->copyList(rho);
    return *this;
}

void List::clearList()
{
    Node* current = first;
    while (current != nullptr)
    {
        current = pop_front();
        delete current;
        current = first;
    }
    first = nullptr;
    last = nullptr;
}

void List::copyList(const List& b)
{
    first = nullptr;
    last = nullptr;
    nodeCount = 0;
    Node *headNode = b.getFirst();
    while (headNode != nullptr)
    {
        string des = headNode->getDescription();
        string qNa = headNode->getQuantityName();
        int qNu = headNode->getQuantityNumber();
        Node* newNode = new Node(qNu, qNa, des);
        push_back(newNode);
        headNode = headNode->getNext();
    }
}

Node* List::pop_front()
{
    Node* saveFirst = first;
    first = first->getNext();
    nodeCount--;
    return saveFirst;
}

void List::push_back(Node* newNode)
{
    if (nodeCount == 0)
    {
        first = newNode;
        last = newNode;
    }
    else
    {
        Node* currentNode = last;
        currentNode->setNext(newNode);
        last = newNode;
    }
    nodeCount++;
}

Answer 1

It will depend at least in part on what first is pointing to when you call the destructor.

Your code is not copying the contents of the nodes. Instead it is only manipulating pointers so, as dyp pointed out, you have a leak with: Node* newNodePtr = new Node; Node* nodeCopy = b.first; newNodePtr = nodeCopy;

You might want to read up on the copy-swap idiom. What is the copy-and-swap idiom?

Answer 2

This may not solve your exact issue, but if you have the functions you mentioned, then pseudo-code to a copy constructor would look like this.

List::List(const List& b)
{
   Node *headNode = b.getHeadNode();
   while (headNode != NULL)
   {
      push_back(headNode->getDataFromNode());
      headNode = headNode->getNextNode();
  }
}

So basically, that in a nutshell is the entire copy constructor. You're basically starting from the first node in the list, getting the data from that node, and calling your push_back() to add the new data. I'm assuming that push_back() does all of the tricky work of creating a node, adding the data to it, and placing it correctly at the back of the list.

Note how small, compact, and intuitive this implementation is. We know that all we need to do to create a copy of a linked list is to first make sure the list is empty (which it is for a new object), and keep adding the items from the old list to the new list. Since push_back() adds an item to a list (and has all the complexity of creating a node and linking it to the end node), we use it in a smart way to create our copy.

Note that you also need an assignment operator to go along with the copy constructor. The assignment operator in the example is simply calling clear() (if you have such a function) to remove all the nodes before proceeding.

Remember that all of this requires that your push_back() function works flawlessly. It should know how to properly handle inserting at the end of an empty and non-empty list.

Edit:

If your driver code does create the new node before the push_back (therefore push_back doesn't allocate the new node), then the alternative code can be used:

List::List(const List& b)
{
   Node *headNode = b.getHeadNode();
   while (headNode != NULL)
   {
      Node *newNode = new Node(headNode->getDataFromNode());
      push_back(newNode);
      headNode = headNode->getNextNode();
  }
}

In the alternate version, I'm assuming that the constructor for the new node can be created with the data as an argument. I personally don't like the design of having push_back() not do all of the work of creating the node, but that's another issue.