I am trying merge two list in C++. My implementation are below:
listnode.h
#ifndef __LISTNODE_H
#define __LISTNODE_H
template< class NODETYPE > class List;
template <class NODETYPE>
class ListNode
{
friend class List< NODETYPE >;
private:
NODETYPE data;
ListNode* next;
public:
ListNode(const NODETYPE &);
~ListNode() {};
NODETYPE getData() const;
ListNode<NODETYPE>* getNext() const;
};
template< class NODETYPE >
ListNode<NODETYPE>::ListNode(const NODETYPE& data)
:data(data),
next(0)
{ } // empty ctor body
template< class NODETYPE >
NODETYPE ListNode<NODETYPE>::getData() const { return data; }
template< class NODETYPE >
ListNode<NODETYPE>* ListNode<NODETYPE>::getNext() const { return next; }
#endif
list.h
#ifndef __LIST_H
#define __LIST_H
#include "listnode.h"
#include <iostream>
#include <new>
#include <cstdlib>
template <class NODETYPE>
class List
{
private:
ListNode<NODETYPE>* firstPtr;
ListNode<NODETYPE>* lastPtr;
ListNode<NODETYPE>* getNewNode(const NODETYPE&);
public:
List();
~List();
void insertFromFront(const NODETYPE&);
void insertAtBack(const NODETYPE&);
bool removeFromFront(const NODETYPE&);
bool removeFromBack(const NODETYPE&);
bool isEmpty() const;
void print() const;
ListNode<NODETYPE>* getFirstNode() const;
ListNode<NODETYPE>* getLastNode() const;
void sort();
void concatenate(List<NODETYPE>);
};
template< class NODETYPE >
List<NODETYPE>::List()
: firstPtr(0),
lastPtr(0)
{// empty ctor body}
template< class NODETYPE >
List<NODETYPE>::~List() {
ListNode<NODETYPE> *iter = firstPtr, *temp;
if(!isEmpty()) {
while (iter) {
temp = iter;
iter = iter->next;
delete temp;
}
}
}
template< class NODETYPE >
void List<NODETYPE>::insertFromFront(const NODETYPE& value) {
ListNode<NODETYPE> *newNode = getNewNode(value);
if (newNode) {
if (isEmpty())
firstPtr = lastPtr = newNode;
else {
newNode -> next = firstPtr; // newNode->next points whereever firstPtr points to.
firstPtr = newNode; // firstPtr now demonstrates the first nodeç
}
} else {
std::cerr << "Allocation failed!" << std::endl;
exit(EXIT_FAILURE);
}
}
template< class NODETYPE >
void List<NODETYPE>::insertAtBack(const NODETYPE& value) {
ListNode<NODETYPE> *newNode = getNewNode(value);
if (newNode) {
if(isEmpty())
firstPtr = lastPtr = newNode;
else {
lastPtr -> next = newNode;
lastPtr = newNode;
}
} else {
std::cerr << "Allocation fails!" << std::endl;
exit(EXIT_FAILURE); // terminate the program
}
}
template< class NODETYPE >
bool List<NODETYPE>::removeFromFront(const NODETYPE& value) {
ListNode<NODETYPE>* temp;
if(isEmpty()) {
return false;
}
if(firstPtr == lastPtr) { // if only one node present
value = firstPtr -> data;
firstPtr = lastPtr = 0;
return true;
}
temp = firstPtr;
value = temp -> data;
firstPtr = firstPtr -> next;
delete temp;
return true;
}
template< class NODETYPE >
bool List<NODETYPE>::removeFromBack(const NODETYPE& value) {
if (isEmpty())
return false;
if(firstPtr == lastPtr) { // if only one node present
value = lastPtr->data;
firstPtr = lastPtr = 0;
return true;
}
ListNode<NODETYPE> *iter = firstPtr;
while (iter != lastPtr)
iter = iter->next;
lastPtr = iter; // alter the point lastPtr points to.
value = iter->next->data; // grab the value of last node
delete iter->next; // delete the last node
return true;
}
template< class NODETYPE >
bool List<NODETYPE>::isEmpty() const {
return firstPtr == 0;
}
template< class NODETYPE >
void List<NODETYPE>::print() const {
ListNode<NODETYPE> *iter = firstPtr;
while(iter) {
std::cout << iter->data << ' ';
iter = iter->next;
}
std::cout << std::endl << std::endl;
}
template< class NODETYPE >
void List<NODETYPE>::sort() {
NODETYPE min = firstPtr -> data;
for (ListNode<NODETYPE>* i = firstPtr; i != 0; i = i -> next) {
for (ListNode<NODETYPE>* j = i -> next; j != 0; j = j -> next) {
if(j->data < i->data){
NODETYPE temp = i->data;
i->data = j->data;
j->data = temp;
}
}
}
}
template< class NODETYPE >
ListNode<NODETYPE>* List<NODETYPE>::getNewNode(const NODETYPE &value) {
return new ListNode<NODETYPE>(value);
}
template< class NODETYPE >
ListNode<NODETYPE>* List<NODETYPE>::getFirstNode() const { return firstPtr; }
template< class NODETYPE >
ListNode<NODETYPE>* List<NODETYPE>::getLastNode() const { return lastPtr; }
template< class NODETYPE >
void List<NODETYPE>::concatenate(List<NODETYPE> l) {
ListNode<NODETYPE>* iter = l.getFirstNode(); // first node of the second linked list
while (iter != 0){
insertAtBack(iter->getData());
iter = iter->next;
}
sort(); // to sort in ascending order
//std::cout << "lastPtr->data:" << lastPtr->data << std::endl;
}
#endif
main.cpp
#include <iostream>
#include "list.h"
#include <cstdlib>
#include <ctime>
template < class NODETYPE>
List<NODETYPE> mergeHandler(List<NODETYPE> list1, List<NODETYPE> list2) {
List<NODETYPE> resultList;
NODETYPE min = list1.getFirstNode()->getData();
for (ListNode<NODETYPE>* i = list1.getFirstNode(); i != 0; i = i -> getNext()) {
}
resultList.print();
return resultList;
}
int main(int argc, char *argv[]) {
List< int > intList1, intList2/*, mergedList*/;
srand(time(NULL));
for (size_t i = 0; i < 10; i++)
intList1.insertFromFront(1 + rand() % 100);
for (size_t i = 0; i < 10; i++)
intList2.insertFromFront(1 + rand() % 100);
//intList1.print();
//intList1.sort();
intList1.print();
//intList2.print();
//intList2.sort();
intList2.print();
intList1.concatenate(intList2);
intList1.sort();
intList1.print();
return 0;
}
The problem is, as mentioned, that at the end of the program, it yields
free(): double free detected in tcache 2
Aborted (core dumped)
I couldn't understand the problem. Because I created new nodes to the first list and add the values of the second list. So even if I delete the same values, I delete the values stored exactly different addresses. In of the question, reccomends of implementing copy ctor and = operator. However, I couldn't get and implement it because I use the normal constructor, but when I implement this ctor
public:
.
.
.
List(List<NODETYPE> &rhs){std::cout << "Do nothing in copy ctor" << std::endl;}
It strangly outputs Do nothing in copy ctor even though I use the normal consturctor. How can I handle this issue? I have already a concatenate method and wanna use it, because when I use copy ctor, it throws a segmentation fault error.
