Question

Complete the following task in C++. You may use the following libraries cstdlib, string, iostream.

1 dLL
The class is described according to the simple UML diagram below:

dLL<T>
-head: item<T>*
-tail: item<T>*
-size: int
----------------------------
+dLL()
+~dLL()
+getHead(): item<T>*
+getTail(): item<T>*
+push(newItem:item<T>*):void
+pop():item<T>*
+getItem(i:int):item<T>*
+minNode():T
+getSize():int
+printList():void

The class variables are as follows:

head: The head pointer of the doubly linked list.
tail: The tail pointer of the doubly linked list.
size: The current size of the doubly linked list. This starts at 0 and increases as the list grows in size.

The class methods are as follows:
dLL: The class constructor. It starts by setting the variables to null and 0 respectively.
~dLL: The class destructor. It will deallocate all of the memory in the class.
getHead: This returns the head pointer of the doubly linked list.
getTail: This returns the tail pointer of the doubly linked list.
push: This adds a new item to the doubly linked list, by adding it to the front of the list.
pop: This returns the top item of the linked list. The item is returned and removed from the list.
getItem: This returns the item of the linked list at the index specified by the argument but without removing it from the list. If the index is out of bounds, return null.
minNode: This returns the value of the item that has the lowest value in the linked list.
getSize: This returns the current size of the linked list.
printList: This prints out the entire list in order, from head to tail. Each item's data value is separate by a comma. For example: 3.1,5,26.6,17.3. Remember to add a newline to the end of the output.

2. item

The class is described according to the simple UML diagram below:

item <T>
-data:T
-------------------
+item(t:T)
+~item()
+next: item*
+prev: item*
+getData():T

The class has the following variables:

data: A template variable that stores some piece of information.
next: A pointer of item type to the next item in the linked list.
prev: A pointer of item type to the previous item in the linked list.

The class has the following methods:

item: This constructor receives an argument and instantiates the data variable with it.
~item: This is the destructor for the item class. It prints out "Item Deleted" with no quotation marks and a new line at the end.
getData: This returns the data element stored in the item.

Answer 1

// C++ code to create item and dLL class
#include <iostream>
using namespace std;

// item class to represent a node in the dLL class
template <class T>
class item
{
private:
   T data;
public:
   item(T t);
   ~item();
   item<T> *next;
   item<T> *prev;
   T getData();
};

// constructor
template <class T>
item<T>::item(T t)
{
   data = t;
   next = NULL;
   prev = NULL;
}

// destructor
template <class T>
item<T>::~item()
{
   cout<<"Item Deleted"<<endl;
}

// return the data
template <class T>
T item<T>::getData()
{
   return data;
}

//end of item

// dLL class to represent the doubly linked list
template <class T>
class dLL
{
private:
   item<T> *head;
   item<T> *tail;
   int size;

public:
   dLL();
   ~dLL();
   item<T>* getHead();
   item<T>* getTail();
   void push(item<T>* newItem);
   item<T>* pop();
   item<T>* getItem(int i);
   T minNode();
   int getSize();
   void printList();
};

// constructor
template <class T>
dLL<T>::dLL()
{
   head = NULL;
   tail = NULL;
   size = 0;
}

// destructor
template <class T>
dLL<T>::~dLL()
{
   // loop over the linked list
   while(head != NULL)
   {
       item<T> *temp = head; // get the current head
       head = head->next; // set head to pointer next to head
       delete(temp); // delete the old head
   }

   tail = NULL;
   size = 0;
}

// function to return the head
template <class T>
item<T>* dLL<T>::getHead()
{
   return head;
}

// function to return the tail
template <class T>
item<T>* dLL<T>::getTail()
{
   return tail;
}

// function to insert newItem at the start of the list
template <class T>
void dLL<T>::push(item<T>* newItem)
{
   // make prev of newItem to NULL and next of newItem to head
   newItem->prev = NULL;
   newItem->next = head;
   // if non-empty list
   if(head != NULL)
   {
       head->prev = newItem; // set prev of head to newItem
   }else // if empty list
   {
       tail = newItem; // set tail to newItem
   }

   head = newItem; // set head as newItem
   size++; // increment the size
}

// delete and return the top element of the list
template <class T>
item<T>* dLL<T>::pop()
{
   item<T> *node = head; // set node to current head
   // if non-empty list
   if(head != NULL)
   {
       head = head->next; // set head to next of head
       // if head is NULL, set tail to NULL
       if(head == NULL)
           tail = NULL;
       else // else set prev of head to NULL
           head->prev = NULL;
       size--; // decrement the size
   }

   return node; // return the node
}

// function to return the item at index i
template <class T>
item<T>* dLL<T>::getItem(int i)
{
   // if index is valid
   if(i >=0 && i < size)
   {
       int idx = 0;
       item<T> *curr = head;
       // loop to get the ith element of list
       while(idx < i)
       {
           curr = curr->next;
           idx++;
       }

       return curr; // return the element
   }

   return NULL; // return NULL, if invalid index
}

// function to return the minimum value in the list
template <class T>
T dLL<T>::minNode()
{
   T minVal ;

   // if non-empty list
   if(head != NULL)
   {
       minVal = head->data;
       item<T> *node = head;
       // loop to get the minimum value of list
       while(node != NULL)
       {
           if(node->getData() < minVal)
               minVal = node->getData();
           node = node->next;
       }

       return minVal; // return minimum value
   }

   return T(0); // return dummy value
}

// function to return the size of list
template <class T>
int dLL<T>::getSize()
{
   return size;
}

// function to print the list
template <class T>
void dLL<T>::printList()
{
   if(head == NULL) //empty list
   {
       cout<<"Empty list"<<endl;
   }else
   {
       // loop to print the list
       item<T> *curr = head;
       cout<<"List : "<<endl;
       while(curr != NULL)
       {
           cout<<curr->getData()<<endl;
           curr = curr->next;
       }
       cout<<endl;
   }
}
//end of dLL class