This is my C++ 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 Merge(LinkedList& b);
};
// Create Linked List using Array
LinkedList::LinkedList(int A[], int n)
{
Node* t = new Node;
if (t == NULL)
{
cout << "Failed allocating memory!" << endl;
exit(1);
}
t->data = A[0];
t->next = NULL;
first = last = t;
for (int i = 1; i < n; i++)
{
t = new Node;
if (t == NULL)
{
cout << "Failed allocating memory!" << endl;
exit(1);
}
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;
}
// Merge two linked list
void LinkedList::Merge(LinkedList& b)
{
// Store first pointer of Second Linked List
Node* second = b.first;
Node* third = NULL, *tmp = NULL;
// We find first Node outside loop, smaller number, so Third pointer will store the first Node
// Then, we can only use tmp pointer for repeating process inside While loop
if (first->data < second->data)
{
third = tmp = first;
first = first->next;
tmp->next = NULL;
}
else
{
third = tmp = second;
second = second->next;
tmp->next = NULL;
}
// Use while loop for repeating process until First or Second hit NULL
while (first != NULL && second != NULL)
{
// If first Node data is smaller than second Node data
if (first->data < second->data)
{
tmp->next = first;
tmp = first;
first = first->next;
tmp->next = NULL;
}
// If first Node data is greater than second Node data
else
{
tmp->next = second;
tmp = second;
second = second->next;
tmp->next = NULL;
}
}
// Handle remaining Node that hasn't pointed by Last after while loop
if (first != NULL)
tmp->next = first;
else
tmp->next = second;
// Change first to what Third pointing at, which is First Node
first = third;
// Change last pointer from old first linked list to new last Node, after Merge
Node* p = first;
while (p->next != NULL)
{
p = p->next;
}
last = p;
// Destroy second linked list because every Node it's now connect with first linked list
// This also prevent from Double free()
b.last = NULL;
b.first = NULL;
}
int main()
{
int arr1[] = {4, 8, 12, 14, 15, 20, 26, 28, 30};
int arr2[] = {2, 6, 10, 16, 18, 22, 24};
int size1 = sizeof(arr1) / sizeof(arr1[0]);
int size2 = sizeof(arr2) / sizeof(arr2[0]);
LinkedList l1(arr1, size1);
LinkedList l2(arr2, size2);
l1.Display();
l2.Display();
// Merge two linked list, pass l2 as reference
l1.Merge(l2);
l1.Display();
return 0;
}
I'm beginner on C++ and in this code, I practice how to Merge two linked list. This actually works perfectly. I've successfully Merge the two Linked List in sorted order.
But, there's people said that I should've follow the Rule of Three on C++. Which implement: Destructor, Copy Constructor, and Copy Assignment Operator.
I've watched many videos about that. I do understand that is basically handle Shallow Copy especially when we don't want two different object point to the same address of memory. But, for my problem is, I still don't know how to Implement it on a Class that working on a Linked List just like my code above.
Someone said, in my main(), this code: l1.Merge(l2); is somehow incorrect because I don't have explicit Copy Constructor.
And if you look at my Merge() function, in Last line, if I didn't to this: b.last = NULL; and b.first = NULL; , which simply destroy pointer of Second Linked list, the Compiler give me warning: Double free() detected.
So, I think my question is:
l1.Merge(l2); is have something to do with Copy Constructor?Double free() happened because I don't implement the Rule of Three? If yes, how to address them?Thank You. I hope someone can explain to me like I'm 10 years old. and hope someone can write me some Code.
But, for my problem is, I still don't know how to Implement [Rule of Three] on a Class that working on a Linked List just like my code above.
You simply implement the copy constructor and copy assignment operator to iterate the input list, making a copy of each node and inserting them into your target list. You already have a working destructor. In the case of the copy assignment operator, you can usually use the copy-swap idiom to implement it using the copy constructor to avoid repeating yourself.
Someone said, in my
main(), this code:l1.Merge(l2);is somehow incorrect because I don't have explicit Copy Constructor.
Then you were told wrong. Your Merge() code has nothing to do with a copy constructor.
And if you look at my
Merge()function, in Last line, if I didn't to this:b.last = NULL;andb.first = NULL;, which simply destroy pointer of Second Linked list, the Compiler give me warning:Double free() detected.
Correct. Since you are moving the nodes from the input list to the target list, you need to reset the input list so it doesn't point at the moved nodes anymore. Otherwise, the destructor of the input list will try to free them, as will the destructor of the target list.
How can this code:
l1.Merge(l2);is have something to do with Copy Constructor?
It doesn't have anything to do with it.
Is
Double free()happened because I don't implement the Rule of Three?
Not in your particular example, as you are not performing any copy operations. But, in general, not implementing the Rule of Three can lead to double frees, yes.
How to write the Rule of Three based on my code?
See the code below.
Do I still need the Rule of Three if my Program only want to Merge Linked List?
No. Only when you want to make copies of lists.
With that said, here is an implementation that includes the Rule of Three:
#include <iostream>
#include <utility>
struct Node
{
int data;
Node *next;
};
class LinkedList
{
private:
Node *first;
Node *last;
public:
LinkedList();
LinkedList(const LinkedList &src);
LinkedList(int A[], int num);
~LinkedList();
LinkedList& operator=(const LinkedList &rhs);
void Display() const;
void Merge(LinkedList &b);
};
// Create Linked List using default values
LinkedList::LinkedList()
: first(NULL), last(NULL)
{
}
// Create Linked List using Array
LinkedList::LinkedList(int A[], int n)
: first(NULL), last(NULL)
{
Node **p = &first;
for (int i = 0; i < n; ++i)
{
Node *t = new Node;
t->data = A[i];
t->next = NULL;
*p = t;
p = &(t->next);
last = t;
}
}
// Create Linked List by copying another Linked List
LinkedList::LinkedList(const LinkedList &src)
: first(NULL), last(NULL)
{
Node **p = &first;
for (Node *tmp = src.first; tmp; tmp = tmp->next)
{
Node* t = new Node;
t->data = tmp->data;
t->next = NULL;
*p = t;
p = &(t->next);
last = t;
}
}
// Deleting all Node in Linked List
LinkedList::~LinkedList()
{
Node *p = first;
while (p)
{
Node *tmp = p;
p = p->next;
delete tmp;
}
}
// Update Linked List by copying another Linked List
LinkedList& LinkedList::operator=(const LinkedList &rhs)
{
if (&rhs != this)
{
LinkedList tmp(rhs);
std::swap(tmp.first, first);
std::swap(tmp.last, last);
}
return *this;
}
// Displaying Linked List
void LinkedList::Display() const
{
for (Node *tmp = first; tmp; tmp = tmp->next)
std::cout << tmp->data << " ";
std::cout << std::endl;
}
// Merge two linked list
void LinkedList::Merge(LinkedList& b)
{
if ((&b == this) || (!b.first))
return;
if (!first)
{
first = b.first; b.first = NULL;
last = b.last; b.last = NULL;
return;
}
// Store first pointer of Second Linked List
Node *second = b.first;
Node *third, **tmp = &third;
// We find first Node outside loop, smaller number, so Third pointer will store the first Node
// Then, we can only use tmp pointer for repeating process inside While loop
// Use while loop for repeating process until First or Second hit NULL
do
{
// If first Node data is smaller than second Node data
if (first->data < second->data)
{
*tmp = first;
tmp = &(first->next);
first = first->next;
}
// If first Node data is greater than second Node data
else
{
*tmp = second;
tmp = &(second->next);
second = second->next;
}
*tmp = NULL;
}
while (first && second);
// Handle remaining Node that hasn't pointed by Last after while loop
*tmp = (first) ? first : second;
// Change first to what Third pointing at, which is First Node
first = third;
// Change last pointer from old first linked list to new last Node, after Merge
Node *p = first;
while (p->next)
{
p = p->next;
}
last = p;
// Destroy second linked list because every Node it's now connect with first linked list
// This also prevent from Double free()
b.first = b.last = NULL;
}
int main()
{
int arr1[] = {4, 8, 12, 14, 15, 20, 26, 28, 30};
int arr2[] = {2, 6, 10, 16, 18, 22, 24};
int size1 = sizeof(arr1) / sizeof(arr1[0]);
int size2 = sizeof(arr2) / sizeof(arr2[0]);
LinkedList l1(arr1, size1);
LinkedList l2(arr2, size2);
LinkedList l3(l1);
LinkedList l4;
l1.Display();
l2.Display();
l3.Display();
l4.Display();
// Merge two linked list, pass l2 as reference
l3.Merge(l2);
l4 = l3;
l1.Display();
l2.Display();
l3.Display();
l4.Display();
return 0;
}