0

This is my code:

#include <iostream>

using namespace std;

typedef struct Node
{   
    int data;
    Node* next;
}Node;

class LinkedList
{
private:
    Node* first;
    Node* last;
public:
    LinkedList() {first = last = NULL;};
    LinkedList(int A[], int num);
    ~LinkedList();

    void Display();
    void Concatenate(LinkedList b);
};

// Create Linked List using Array
LinkedList::LinkedList(int A[], int n)
{   
    Node* t = new Node;
    t->data = A[0];
    t->next = NULL;
    first = last = t;

    for (int i = 1; i < n; i++)
    {
        t = new Node;
        t->data = A[i];
        t->next = NULL;
        
        last->next = t;
        last = t;
    }
}

// Deleting all Node in Linked List
LinkedList::~LinkedList()
{
    Node* p = first;
    Node* tmp;

    while (p != NULL)
    {
        tmp = p;
        p = p->next;
        delete tmp;
    }
}

// Displaying Linked List
void LinkedList::Display()
{
    Node* tmp;

    for (tmp = first; tmp != NULL; tmp = tmp->next)
        cout << tmp->data << " ";
    cout << endl;    
}

// Concatenate two linked list
void LinkedList::Concatenate(LinkedList b)
{
    // We can use last pointer which point to last Node of first linked list
    // Make it to point to the first Node of second linked list
    last->next = b.first;
    b.first = NULL;
}

int main()
{
    int arr1[] = {4, 8, 12, 14, 18};
    int arr2[] = {2, 6, 10, 16};

    LinkedList l1(arr1, 5);
    LinkedList l2(arr2, 4);

    l1.Display();
    l2.Display();
    
    // Concatenate first linked list with second linked list
    l1.Concatenate(l2);
    l1.Display();

    return 0;
}

I try to learn how to Concatenate two Linked List. And the result is correct. Which connect arr1 and arr2 in main() function.

But, what I don't understand is there's a warning on my Compiler said:

free(): double free detected in tcache 2

When I try to check using Valgrind, there's so much Error inside Heap which makes me not understand more. But it seems like it's not Free all the Nodes properly.

Is there something wrong in my code? What should I change to make the warning disappear? Perhaps there's another way to Concatenate Linked List? And maybe someone can explain me what double free means. Thank You.

Kevinkun
  • 21
  • 5
  • While you should still follow [the rule of three/five/zero](https://en.cppreference.com/w/cpp/language/rule_of_three) there is a very quick workaround: Don't pass the lists by value to the `Concatenate` function. It will also solve another problem: That the poriginal `l2` object in the `main` function not being modified, and you suddenly have "two" (well not really) lists. – Some programmer dude Jul 14 '21 at 17:29
  • By the way, in the `Concatenate` function there's another bug: You don't update the `last` pointer. It will point to somewhere in the middle of the list. – Some programmer dude Jul 14 '21 at 17:31
  • The problem is not only in `Concatenate` because `b` loses ownership of the onderlying list. It's also in the constuctor: `last->next = t; last = t;`. `last` and `last->next` are the same object. – ichramm Jul 14 '21 at 17:31
  • A general tip when it comes to things like lists: Do all operations using pencil and paper *first* before you attempt to write any code. Draw small squares for the nodes and other variables, and label all variables. Then draw arrows for the links and the pointers, and every time you make a modification to a link or pointer, erase the arrow and redraw a new one reflecting the update you just made. Once you get everything to "work" then you start writing the code. – Some programmer dude Jul 14 '21 at 17:36
  • @JuanR That part actually looks fine. `last->next = t;` is called while `last` still points to the now-penultimate element of the list. Then `last = t;` updates what `last` points to. They _should_ be pointing to the same node. – Nathan Pierson Jul 14 '21 at 17:41
  • @NathanPierson you are absolutely right, my bad! – ichramm Jul 14 '21 at 17:43
  • I don't know where to start with the rule you gave. So, you mean I should pass the list by address and work with pointer inside the function? @Someprogrammerdude – Kevinkun Jul 14 '21 at 17:47
  • Pass by *reference*. As in `void Concatenate(LinkedList& b);` But like I said, it's just a quick and dirty workaround, the real problem still needs to be adressed. – Some programmer dude Jul 14 '21 at 17:51
  • @Kevinkun `LinkedList::Concatenate(LinkedList b)` accepts `b` by value. That means when you call `l1.Concatenate(l2);`, you make a copy of `l2`. However, you haven't written a copy constructor for your class, and in your class's case the default compiler-generated copy constructor is incorrect. It copies the values of the pointers `first` and `last`, but it doesn't copy the contents pointed to them. This eventually means that both `l1` and `l2` will be trying to delete the same node when their destructors run. – Nathan Pierson Jul 14 '21 at 17:51
  • 1
    @Someprogrammerdude In this case perhaps consider even passing by rvalue `LinkedList&& b`. Since we're not just changing `b`, we're leaving it in a completely invalid state. And then you could write `l1.concatenate(std::move(l2));` if you really wanted to blow up `l2`. – Nathan Pierson Jul 14 '21 at 17:53
  • @NathanPierson I just change the code and the warning is gone. Pass by _reference_ and also update my `last` pointer to store the last Node of second linked list. Then, I assign Null to `first` and `last` of second linked list so it will completely lost when I try to display it again. – Kevinkun Jul 14 '21 at 18:06
  • @NathanPierson and when I run **Valgrind** it says _All heap blocks were freed_ – Kevinkun Jul 14 '21 at 18:09
  • Right. So now when you pass by reference, it modifies `l2`, instead of modifying a copy (a copy that was produced inaccurately). So all the nodes get transferred from `l2` to `l1`, meaning that when `l1`'s destructor is called all the nodes are destroyed and when `l2`'s destructor is called no nodes are destroyed and everything is dandy. You still have the problem that if you ever _do_ try to copy a `LinkedList` things will go badly wrong, but this change means that you no longer make a copy. – Nathan Pierson Jul 14 '21 at 18:15

0 Answers0