CODEWITHSUNDEEP
c++pointersmemory
alekscooper
alekscooper

Reputation: 831

Memory error in the destructor when reverse a linked list

I'm writing my own linked list class (for educational purposes) and here it is:

The node

#define PRINT(x) #x << " = " << x << " "

struct ListNode {
    int val;
    ListNode *next = nullptr;
    ListNode(int x) : val(x), next(nullptr) {}
};

The class

class LinkedList{
    private:
        ListNode* _head;
        unsigned long long int _size;
    public:

        LinkedList():_head(nullptr), _size(0) {}

        LinkedList(ListNode* _h):_head(_h), _size(0) {
            ListNode *node = _head;
            while (node != nullptr) {
                _size++;
                node = node -> next;
            }
        }

       ~LinkedList() {
            while (_head != nullptr) {
                remove();
            }
        }

        void add(const int& value) {
             ListNode *node = new ListNode(value);
             node -> next = _head;
             _head = node;
             _size++;
        }

        int remove() {
             int v = _head -> val;
             ListNode *node = _head;
             _head = _head -> next;
             delete node;
             _size--;
             return v;
        }

        void print() {
             if (size() == 0) {
                 cout << "List is empty" << endl;
                 return;
             }
             ListNode *node = _head;
             while (node -> next != nullptr) {
                 cout << node -> val << " -> ";
                 node = node -> next;
             }
             cout << node -> val << endl;
        }

         unsigned long long int size() { return _size; }
         ListNode* head() { return _head; }
};

I've decided to solve a LeetCode problem Reverse Linked List and here's the solution that works:

// Returns the head of the reversed list
ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* current = head;
    while(current != nullptr) {
        ListNode* next_elem = current -> next;
        current -> next = prev;
        prev = current;
        current = next_elem;
    }
    return prev;
}

The problem is the following: LeetCode doesn't want my main() function, so for testing purposes I obviously used my own. Here it is:

int main() {

    LinkedList L;
    L.add(4);
    L.add(3);
    L.add(2);
    L.add(1);

    L.print();

    LinkedList L2 (reverseList(L.head()));
    cout << PRINT(L2.size()) << endl;
    L2.print();

    return 0;
}

The problem with that function is that I get this error: IO_FILE(3853,0x7fff75d44000) malloc: *** error for object 0x7f92284031b0: pointer being freed was not allocated

I can't figure out at what moment I'm trying to free a pointer that was not allocated. Where am I doing it?

Upvotes: 1

Views: 68

Answers (1)

Lukas-T
Lukas-T

Reputation: 11350

It's not quite as I said in my comment, but the the rule of three is still a good read.

The problem is sligthly different: The constructor 

LinkedList(ListNode* _h)

Just takes ownership of _h. When you initialize a LinkedList with this constructor like in

LinkedList L2 (reverseList(L.head()));

head is the same in L1 and L2. When those two lists go out of scope both will try to delete the same nodes (which works only once of cause).

Upvotes: 3

Related Questions