Linked List Destructor executes with Valgrind but not on its own

Question

I have the following struct:

class List{
public: //Functions go here
    typedef struct node{
    string data;
    node* prev;
    node* next;
}* nodePtr;

nodePtr head;
nodePtr curr;
nodePtr temp;
nodePtr tail;

List();
//~List();
    void addToEnd(string addData);
    void addToBeg(string addData);
    void DeleteList();
    //More functions not included//
};

with constructor:

List::List(){
    head = NULL;
    curr = NULL;
    temp = NULL;
    tail = NULL;
}

and to delete nodes:

void List::DeleteList(){
    temp = head;
    curr = head;
    while(curr != NULL){
        temp = curr->next;
        delete curr;
        curr = temp;
    }
}

The rest of the code takes in numbers and performs addition and multiplication on them by partitioning the numbers into nodes. I call DeleteList() at the end of each function for each List. When I run the code with Valgrind, my output completes with the correct answers even though it says "Conditional jump or move depends on uninitialised value(s)" on a few of the function calls.

When I execute the program along using gcc, I get a "pointer being freed was not allocated". What is the difference between the two execution methods? And why is gcc saying that the pointer wasn't allocated?

Adding a node looks like:

void List::addToEnd(string addData){ //adds to end of linked list
    //nodePtr n = (nodePtr)malloc(sizeof(node));
    nodePtr n = new node;
    n->next = NULL;
    n->data = addData;

    if(head != NULL){
        curr = head;
        while(curr->next != NULL){
            curr = curr->next;
        }
        curr->next = n;
        n->prev = curr;
        tail = n;
    }
    else{
        n->prev = NULL;
        head = n;
        tail = n;
    }
}

edit: Complete code for reference:

//structure for assembling doubly linked list.
#include <cstdlib>
#include <iostream>
#include <stdlib.h>
#include <cstring>
#include <string.h>
#include <math.h>
#include <fstream>
#include <sstream>
#include <stdio.h>
#include <ctype.h>
#include <unistd.h>
using namespace std;

class List{
public: //Functions go here
    typedef struct node{
        string data;
        node* prev;
        node* next;
    }* nodePtr;

    nodePtr head;
    nodePtr curr;
    nodePtr temp;
    nodePtr tail;

    List();
    ~List();
    void addToEnd(string addData);
    void addToBeg(string addData);
    List::nodePtr returnHead();
    List::nodePtr returnNext(List::nodePtr n);
    List::nodePtr returnPrev(List::nodePtr n);
    List::nodePtr returnTail();
    void DeleteList();
    void PrintList();
    void ConvertHead();
    void DeleteNode(string delData);
    string ListValue();
    string returnValue(List::nodePtr n);
};
//Functions
List addLists(List a, List b, long long nodeLength);
List multLists(List a, List b, long long nodeLength);
string doArithmetic(string num1, string num2, string op, long long nodSiz);
string removeSpaces(string input);


int main(int argc, char** argv){

  string sentence, sent2, operation, arg1, arg2;
  long long digitCount;
  int op;

  //Takes in the first argument and finds the first double quote
  //Uses what is in the quotes as the filename
  string str (argv[1]);

  size_t firstEqual = 6;

  size_t semicolon = str.find_first_of(";");

  size_t secondEqual = semicolon + 17;

  std::string file = str.substr(firstEqual, semicolon - firstEqual);
  digitCount = stoll(str.substr(secondEqual, str.length()));

  //Opens the file designated in the argument  
  ifstream inputFile (file.c_str());

  while(getline(inputFile, sentence)){
    sent2 = removeSpaces(sentence);
    op = sent2.find_first_of("+*");
    arg1 = sent2.substr(0,op);
    arg2 = sent2.substr(op+1,string::npos);
    //cout << "arg1: " << arg1 << " arg2: " << arg2 << " Operation: " << sent2.substr(op,1) << endl;
    cout << sent2 << "=";
    cout << doArithmetic(arg1, arg2, sent2.substr(op,1), digitCount) << endl;
    }
    return 0;
}


string doArithmetic(string num1, string num2, string op, long long nodSiz){

    long long nodeSize = nodSiz;
    string numberOne = num1; //14
    string numberTwo = num2;
    string answer;

    List value1, value2, result;

    //cout << numberOne << endl;
    //assigns values as strings to value1
    if(strlen(numberOne.c_str())%nodeSize != 0){
        value1.addToEnd(numberOne.substr(0,strlen(numberOne.c_str())%nodeSize));

        for(int i=0; i < strlen(numberOne.c_str())/nodeSize; i++){
            value1.addToEnd(numberOne.substr(strlen(numberOne.c_str())%nodeSize + i*nodeSize,nodeSize));
        }
    }
    else{
        for(int i=0; i < strlen(numberOne.c_str())/nodeSize; i++){
            value1.addToEnd(numberOne.substr(strlen(numberOne.c_str())%nodeSize + i*nodeSize,nodeSize));
        }
    }
    //value1.PrintList();

    //cout <<numberTwo<<endl;
    //assigns values as strings to value2
    if(strlen(numberTwo.c_str())%nodeSize != 0){
        value2.addToEnd(numberTwo.substr(0,strlen(numberTwo.c_str())%nodeSize));

        for(int i=0; i < strlen(numberTwo.c_str())/nodeSize; i++){
            value2.addToEnd(numberTwo.substr(strlen(numberTwo.c_str())%nodeSize + i*nodeSize,nodeSize));
        }
    }
    else{
        for(int i=0; i < strlen(numberTwo.c_str())/nodeSize; i++){
            value2.addToEnd(numberTwo.substr(strlen(numberTwo.c_str())%nodeSize + i*nodeSize,nodeSize));
        }
    }
    //value2.PrintList();

    if(op == "+"){ 
        result = addLists(value1, value2, nodeSize);
    }
    else{
        result = multLists(value1, value2, nodeSize);
    }

    result.ConvertHead();
    answer = result.ListValue();

    value1.DeleteList();
    value2.DeleteList();
    result.DeleteList();
    return answer;
}

List multLists(List a, List b, long long nodeLength){
    List n;
    List::nodePtr aPoint, bPoint;
    long long valueA, valueB, product;
    long long leftover = 0;
    string filler;
    long long lengthDiff;
    int counterA = 0;
    int counterB = 0;

    for(int i=0; i < nodeLength;i++) filler = "0" + filler;

    bPoint = b.returnTail();
    while(bPoint != NULL){
        //cout << "B Point" << endl;
        valueB = stoll(b.returnValue(bPoint));
        leftover = 0;
        aPoint = a.returnTail();
        counterA = 0;
        while(aPoint != NULL){
            //cout << "A Point" << endl;
            List temp;
            valueA = stoll(a.returnValue(aPoint));
            product = valueA * valueB + leftover;

            lengthDiff = to_string(product).length() - nodeLength;

            if(to_string(product).length() > nodeLength){
                temp.addToBeg(to_string(product).substr(to_string(product).length()-nodeLength,nodeLength));
                leftover = stoll(to_string(product).substr(0,lengthDiff));
            }
            else{
                temp.addToBeg(to_string(product));
                leftover = 0;
            }

            for(int i = 0; i < counterA + counterB; i++){
                temp.addToEnd(filler);
            }
            n = addLists(n,temp,nodeLength);
            temp.DeleteList();  
            aPoint = a.returnPrev(aPoint);
            counterA = counterA + 1;
        }
        bPoint = b.returnPrev(bPoint);
        counterB = counterB + 1;
    }
    if(leftover != 0) n.addToBeg(to_string(leftover));

    return n;
}



List addLists(List a, List b, long long nodeLength){
    List n;
    List::nodePtr aPoint, bPoint;
    long long valueA, valueB, sum;
    long long leftover = 0;
    long long lengthDiff;
    string input;

    aPoint = a.returnTail();
    bPoint = b.returnTail();

    while(aPoint != NULL || bPoint != NULL){
        if(aPoint != NULL) valueA = stoll(a.returnValue(aPoint));
        else valueA = 0;

        if(bPoint != NULL) valueB = stoll(b.returnValue(bPoint));
        else valueB = 0;

        sum = valueA + valueB + leftover;
        if(to_string(sum).length() > nodeLength){ 
            input = to_string(sum).substr(to_string(sum).length()-nodeLength,nodeLength);
        }
        else {
            input = to_string(sum);
        }

        lengthDiff = nodeLength-to_string(sum).length();

        if(nodeLength > to_string(sum).length()){
            for(int i=0; i < nodeLength-to_string(sum).length();i++){
                // cout << "sumLength: " << to_string(sum).length() << endl;
                input = "0" + input;
            }
        }
        n.addToBeg(input);

        if(to_string(sum).length() > nodeLength){
            leftover = stoll(to_string(sum).substr(0,to_string(sum).length() - nodeLength));
        }
        else leftover = 0;

        if(aPoint != NULL) aPoint = a.returnPrev(aPoint);
        if(bPoint != NULL) bPoint = b.returnPrev(bPoint);
        // cout << "sum: " << sum << " sum.length(): " << to_string(sum).length() << " leftover: " << leftover << endl;
        // cout << "lengthDiff: " << to_string(sum).substr(0,to_string(sum).length() - nodeLength) << endl;
    }

    if(leftover != 0) n.addToBeg(to_string(leftover));

    return n;
}

List::List(){
    head = NULL;
    curr = NULL;
    temp = NULL;
    tail = NULL;
}

List::~List(){
    temp = head;
    curr = head;
    while(curr != NULL){
        temp = curr->next;
        delete curr;
        //free(curr);
        curr = temp;
    }
    head = curr = temp = tail = NULL;
}

void List::addToEnd(string addData){ //adds to end of linked list
    //nodePtr n = (nodePtr)malloc(sizeof(node));
    nodePtr n = new node;
    n->next = NULL;
    n->data = addData;

    if(head != NULL){
        curr = head;
        while(curr->next != NULL){
            curr = curr->next;
        }
        curr->next = n;
        n->prev = curr;
        tail = n;
    }
    else{
        n->prev = NULL;
        head = n;
        tail = n;
    }
}

void List::addToBeg(string addData){ //adds to beginning of linked list
    //nodePtr n = (nodePtr)malloc(sizeof(node));
    nodePtr n = new node;
    n->prev = NULL;
    n->data = addData;

    if(head != NULL){
        curr = head;
        while(curr->prev!= NULL){
            curr = curr->prev;
        }
        curr->prev = n;
        n->next = curr;
        head = n;
    }
    else{
        n->prev = NULL;
        head = n;
        tail = n;
    }
}

List::nodePtr List::returnHead(){
    return head;
}

List::nodePtr List::returnNext(List::nodePtr n){
    return n->next;
}

List::nodePtr List::returnPrev(List::nodePtr n){
    return n->prev;
}

List::nodePtr List::returnTail(){
    return tail;
}

string List::returnValue(List::nodePtr n){
    return n->data;
}

void List::DeleteList(){
    temp = head;
    curr = head;
    while(curr != NULL){
        temp = curr->next;
        delete curr;
        //free(curr);
        curr = temp;
    }
    head = curr = tail = temp = NULL;
}

void List::ConvertHead(){
    long long convert;
    curr = head;
    convert = stoll(curr->data);
    curr->data = to_string(convert); 
}


void List::PrintList(){
    curr = head;
    while(curr != NULL){
        cout << curr->data << endl;
        curr = curr->next;
    }
}

string List::ListValue(){
    string value;
    curr = head;
    while(curr != NULL){
        value = value + curr->data;
        curr = curr->next;
    }
    return value;
}

string removeSpaces(string input){ //found on cplusplus.com
  int length = input.length();
  for (int i = 0; i < length; i++) {
     if(input[i] == ' ') input.erase(i, 1);
  }
  return input;
}

Example command line prompt:

./a.out "input=test0.txt; digitsPerNode =3"

with example input file named test0.txt:

0*0
0+1
2*3
2*2000000000000000
2*3
1+10
10000000000000000+1
12345667890123456789 + 8765432109876543210
999999999999999999999 + 1

What destructor are you referring to? I don't see any destructors in this code. — robert
Do you reuse the same List object after calling DeleteList()? It leaves the object in inconsistent state. No other function can be called after for that object. To reuse the obeject DeleteList() must reset all pointers head = curr = tail = temp = NULL. — Orest Hera
When you "execute the program along using gcc"? You build the executable using gcc, you then run the executable by itself. Is gcc really telling you that an unallocated pointer is being freed? That sounds like a run-time error, so either 1) something else is telling you that, 2) gcc is telling you something else, or 3) gcc is smarter than I thought it was. Please give us a minimal complete example so we can stop guessing. — Beta

Orest Hera Orest Hera · Accepted Answer · 2015-09-28T10:30:44

Copy constructor and assignment operator are required for such class, since it holds pointers. The default copy constructor only makes a copy of class members.

So, if a local class instance is returned from a function the result contains pointers to invalid nodes that are deleted during destruction of the local object:

List multLists(List a, List b, long long nodeLength)
{
    List n;
    //... construct nodes of n      
    return n;
}

// result holds only body of returned n; nodes are already deleted
result = multLists(value1, value2, nodeSize);

Copy constructor and assignment operator with deep object copy resolve that issue:

// copy constructor
List::List(const List& l) :
    head(nullptr), curr(nullptr), temp(nullptr), tail(nullptr)
{
    for (nodePtr i = l.head; i; i = i->next)
        addToEnd(i->data);
}

// C++11 move constructor
List::List(List&& l) :
    head(l.head), curr(l.curr), temp(l.temp), tail(l.tail)
{
    // keep original object in consistent state
    l.head = nullptr;
    l.curr = nullptr;
    l.temp = nullptr;
    l.tail = nullptr;
}

// assignment operator
List& List::operator=(const List& l)
{
    if (this == &l)
        return *this;

    // for exception safety at first copy to temporary
    List tmp(l);

    // move temporary to this
    *this = move(tmp);

    return *this;
}

// C++11 move assignment operator
List& List::operator=(List&& l)
{
    if (this == &l)
        return *this;

    // free current list
    DeleteList();
    // move to this
    head = l.head;
    curr = l.curr;
    temp = l.temp;
    tail = l.tail;
    // keep original object in consistent state
    l.head = nullptr;
    l.curr = nullptr;
    l.temp = nullptr;
    l.tail = nullptr;

    return *this;
}

The adding to begin also should be fixed:

void List::addToBeg(string addData){ //adds to beginning of linked list
    nodePtr n = new node;
    n->prev = NULL;
    n->data = addData;

    if(head != NULL){
        n->next = head;
        head->prev = n;
        head = n;
    }
    else{
        n->next = NULL;
        head = n;
        tail = n;
    }
}

Other remarks

Since the project compilation requires C++11 there is nullptr instead of NULL.

It looks that addToEnd() may be optimized. The while loop is not needed to find the last list item, since there is tail pointer.

It makes sense to avoid deep object copies during function calls. It is better to pass constant references:

List multLists(const List& a, const List& b, long long nodeLength)

Of course here the code should be adjusted to proper usage of const qualifiers.

Linked List Destructor executes with Valgrind but not on its own

1 Answers