Hi guys!
I am wondering how can one perform a sorted merge between the calling object list and the the passed in list?
Here is what I have got so far :
#include<iostream>
using namespace std;
#define NULL 0
template <typename T>
class DoublyLinkedList;
template <typename T>
class Node
{
friend class DoublyLinkedList<T>;
public:
Node()
{next = this; prev = this;}
Node(const T& data, Node<T> *next = NULL, Node<T> *prev = NULL)
{this ->data = data; this ->next = next;
this ->prev = prev;}
private:
T data;
Node<T> *next;
Node<T> *prev;
};
template <typename T>
class DoublyLinkedList
{
public:
DoublyLinkedList();
DoublyLinkedList(T arr[], T arrSize);
~DoublyLinkedList();
Node<T> *insert(Node<T> *insertionPoint, const T& data);
void addSortedList(const DoublyLinkedList<T>& list2);
void display();
private:
Node<T> *header;
int size; // number of data nodes in list
};
template<typename T>
DoublyLinkedList<T>::DoublyLinkedList()
{
header = new Node<T>();
size = 0;
}
template<typename T>
DoublyLinkedList<T>::DoublyLinkedList(T arr[], T arrSize)
{
header = new Node<T>();
size = arrSize;
for (int i = 0; i < size; i++)
{
insert(header->prev, arr[i]);
}
}
template<typename T>
DoublyLinkedList<T>::~DoublyLinkedList()
{
while (header->next != header)
{
Node<T>* next = header ->next;
header = next;
}
delete header;
}
template<typename T>
Node<T> *DoublyLinkedList<T>::insert(Node<T> *insertionPoint, const T& data)
{
Node<T> *prevNodePtr;
Node<T> *newNodePtr;
prevNodePtr = insertionPoint ->prev;
newNodePtr = new Node<T>(data, insertionPoint, prevNodePtr);
size++;
insertionPoint ->prev = prevNodePtr->next = newNodePtr;
return newNodePtr;
}
template<typename T>
void DoublyLinkedList<T>::addSortedList(const DoublyLinkedList<T> &list2)
{
DoublyLinkedList<T> current = list2;
DoublyLinkedList<T> *next;
while(header->next != header)
{
if (current.header->next < list2.header-> next)
{
header->next = current.header;
current.header = current.header ->next;
}
else
{
header->next = list2.header;
//list2.header = list2.header ->next;
}
}
}
template<typename T>
void DoublyLinkedList<T>::display()
{
if(header->next == header)
{
cout<<"the list is empty"<<endl;
}
else
{
Node<T> *next = header ->next;
header = next;
cout<<header;
}
}
My .cpp file
#include "DoublyLinkedList.h"
int main()
{
int arrA[] = {30,90,95};
int arrB[] = {10,20,40,95, 100};
int arrASize = sizeof(arrA)/sizeof(int);
int arrBSize = sizeof(arrB)/sizeof(int);
DoublyLinkedList<int> listA(arrA, arrASize);
DoublyLinkedList<int> listB(arrB, arrBSize);
DoublyLinkedList<int> listC;
listC.display();
listA.display();
listA.addSortedList(listB);
listA.display();
listB.display();
return 0;
}
This should print
Empty linked list
30 90 95
10 20 30 40 90 95 100
30 90 95
I need help in addSortedList function, I think.
Thank you,