complexcodes 0 Junior Poster in Training

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,

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.