Operations on Linked List giving error after completion

Question

I have written a linked list class and some methods for it. It is completing all methods fine but the program is outputting an error after. Is there any reason to why this would be happening?

The Node hpp:

class Node{
    public:
        int data;
        Node * next;
        Node(int val);
};

The Node cpp:

#include <stdio.h>
#include "node.hpp"

Node::Node(int val)
    : next(NULL)
{
    data = val;
}

The linked list Class hpp:

#include "node.cpp"

class LL {
    private:
        Node *head;
        Node *tail;
    public:

        LL();
        ~LL();


        int LL_append(int value);

        void LL_print();

        int LL_search(int target);

        int LL_catenate(LL * list);

        int LL_insert(int x);


};

The linked list Class cpp:

#include "LL.hpp"
#include <stdio.h>
#include <iostream>

using std::cout;

LL::LL()
    :
      head(NULL),
      tail(NULL)
{

}
LL::~LL(){
    Node * curr = head;
    while(head != NULL){
        if(head == tail){
            delete head;
            return;
        }
        while(curr->next != tail){
            curr = curr->next;
        }
        delete tail;
        tail = curr;
        curr = head;
    }
}

//returns 1 for success and 0 for fail
int LL::LL_append(int value){
    int ret = 0;
    Node * newNode = new Node(value);
    if(value != NULL){
        if(head == NULL){
            head = newNode;
            tail = newNode;

        }   
        else{
            tail->next = newNode;
            tail = newNode;
        }
        ret = 1;
    }
    return ret;
}

//prints out list
void LL::LL_print(){
    Node * curr = head;
    cout << "[ ";
    while(curr != NULL){
        cout << curr->data << " ";
        curr = curr->next;
    }
    cout << "]\n";
}

//returns the number of times it appears in the list. return -1 if failed
int LL::LL_search(int target){
    int count = 0;
    Node * curr = head;
    while(curr != NULL){
        if(curr->data == target){
            count++;
        }
        curr = curr->next;
    }
    return count;
}

//returns 1 on success
int LL::LL_catenate(LL * list){
    if(list->head == NULL){

    }
    else if(head == NULL){
        head = list->head;
        tail = list->tail;
    }
    else{
        tail->next = list->head;
        tail = list->tail;
    }
    return 1;
}

int LL::LL_insert(int x){
    int ret = 0;
    Node * curr = head;
    Node * newNode = new Node(x);
    if(head == NULL){
        head = newNode;
        tail = newNode;
        ret = 1;
    }
    else if(head->data >= x){
        printf("here\n");
        newNode->next = head;
        head = newNode;
    }
    else{
        Node * curr = head;
        while( curr->next != NULL && curr->next->data < x){
            curr = curr->next;
        }
        newNode->next = curr->next;
        curr->next = newNode;
        if(curr->next == NULL){
            tail = newNode;
        }
        ret = 1;


    }

    return ret;
}

This is what I am using to test the methods out:

int main(){
    LL L1 = LL();
    L1.LL_append(1);
    L1.LL_append(3);
    L1.LL_print();
    printf("%d\n", L1.LL_search(12));
    printf("%d\n", L1.LL_search(1));

    LL L2 = LL();
    L2.LL_append(5);
    L2.LL_append(9);
    L1.LL_catenate(&L2);
    L1.LL_print();

    L1.LL_insert(7);
    L1.LL_print();
    L1.~LL();
    L2.~LL();
    printf("done\n");
}

And this is the output of the program:

[ 1 3 ]
0
1
[ 1 3 5 9 ]
[ 1 3 5 7 9 ]
done
double free or corruption (fasttop)
Aborted (core dumped)

I have never seen an error happen after the test program is done running. Is there any reason to why this is happening? I believe it has something to do with the insert method.

Why are you calling the `LL` destructor explicitly? You should normally never do that. — Some programmer dude, Apr 17 '20 at 04:40

score 0 · Answer 1 · answered Apr 17 '20 at 04:42

Don't call your destructor manually. The destructor will get called automatically when the linked list goes out of scope. If you just remove the explicit calls to the destructor, it works correctly.

Note that you get warnings about using NULL. Fix that by using nullptr instead.

Michael · Accepted Answer · 2020-04-17T04:48:35.783

You should not call the destructor unless you constructed the object explicitly (that is, using placement new).
If you define a destructor, you should also define a copy-constructor and copy assignment operator. This is called the Rule of 3

Bonus -

your program is extremely inefficient. You iterate over the LinkedList from the beginning to the end for deleting a single object. Consider this improvement:

LL::~LL(){
    Node* curr = head;
    while(head != NULL){
        head = curr->next;
        delete curr;
        curr = head;
    }
}

You check that value != NULL in the insertion. This simply checks that value != 0, but it is misleading and I can't see any reason for this check. If you meant it, write value != 0. Otherwise - remove.

Alan Birtles · Answer 3 · 2020-04-17T04:53:00.970

Explicitly calling your destructors mean they run twice, once when you call them and once when your lists are destroyed. Simply remove the calls to the destructors they aren't necessary.

Your destructor itself seems unnecessarily complicated and could just be:

LL::~LL(){
    while(head){
        Node* next = head->next;
        delete head;
        head = next;
    }
    tail = nullptr;
}

This isn't causing you a problem yet but likely will soon, as you have a destructor you need to follow the rule of three and delete/define the copy constructor and assignment operator.

Operations on Linked List giving error after completion

3 Answers3