Question

C++ (With main to test)

2.2
Task 1
You are going to implement a variant of the standard linked list, the doubly linked list.
Doubly linked lists are because they enable a backwards and forwards traversal of the
list through the addition of more pointers. By increasing the memory cost of the list, it
enables a better access since the list does not need to be traversed in only one direction.
This will consist of implementing two classes: dLL and item.

2.2.1
dLL
The class is described according to the simple UML diagram below:
2dLL<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>*
+peek():item<T>*
+getItem(i:):item<T> *
+maxNode():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 respec-
tively.
• ∼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. The push should add to the front, which refers to the head pointer.
• pop: This returns the top item of the linked list. The item is returned and removed
from the list.
• peek: This returns the top item of the linked list but without removing it 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. Use 0-indexing for the get item. That is, indices start at 0.
• maxNode: This returns the value of the item that has the highest value in the linked
list.
3• 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. Afterwards, print
out a newline.
2.2.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.

You will be allowed to use the following libraries: cstdlib,string,iostream.

Answer 1

Code:

#include<iostream>
#include<string>
using namespace std;

// Template for class item
template <class T>
class item{
private:
   T data; // data holds the variable in the item
public:
   item* next; // pointer to the next item
   item* prev; // pointer to the previous item

   // Constructor
   item(T t){
       data = t;   // assigning data = t
       next = NULL;   // assigning next to null
       prev = NULL;   // assigning prev to null
   }

   // Destructor
   ~item(){
       cout<<"Item Deleted"<<endl;
   }
  
   // Function to return the data in the item
   T getData(){
       return this->data;
   }
};

template <class T>
class dLL{
private:
   item<T>* head;   // Pointer to the head item
   item<T>* tail; // Pointer to the tail item
   int size; // total number of items in the doubly linked list
public:
   dLL(){
       head = NULL; // initialize head to null
       tail = NULL; // initialize tail to null
       size = 0; // initialize size = 0
   }

   ~dLL(){
       // Should destroy all the items in linked list
       while(head != NULL) // the item to be deleted should not be null
       {
           item<T>* temp = head;
           head = head->next;
           delete temp;   // Deletes the item temp.
                   // Calls the destructor of item
           temp = NULL;   // After deleting, should be put to null
       }
   }

   // Function returns the pointer the head item
   item<T>* getHead(){
       return head;
   }

   // Function returns the pointer the tail item
   item<T>* getTail(){
       return tail;
   }

   // Function to add a new item to the front of the list.
   void push(item<T>* newItem){
       if(head == NULL) // if head == NULL, this is the first item to be inserted
       {
           head = newItem; // assigning head to newItem
           tail = head;   // point tail to head
           size++;       // increase size by one
           return;      
       }
      
       newItem->next = head;   // newItem
       head->prev = newItem;
       head = newItem;
       size++;
   }
  
   item<T>* pop(){
       item<T>* temp = head;
       head = head->next;
       head->prev = NULL;
       if(head == NULL)
           tail = NULL;
       size--;
       return temp;
   }

   item<T>* peek(){
       return head;
   }

   item<T>* getItem(int i){
       item<T>* temp = head;
       while(i > 0)
       {
           temp = temp->next;
           i--;
       }
      
       return temp;
   }

   // Returns the maximum data
   T maxNode(){
       item<T>* temp = head;
       T max;
       if(typeid(string)!=typeid(T))
           max = 0;
       else
       {
           cout<<"The data is of type string no max";
       }

       // Traversing the list and checking for the max item
       while(temp != NULL)
       {
           if(typeid(string)!=typeid(T) && temp->getData() > max)
               max = temp->getData();
           temp = temp->next;
       }
       return max;
   }

   // return the number of elements in the list
   int getSize(){
       return size;
   }

   // Print the Doubly linked list
   void printList(){
       item<T>* temp = head;

       cout << temp->getData();
       temp = temp->next;

       // traversing the linked list and printing the datas
       while(temp != NULL)
       {
           cout <<"," << temp->getData();
           temp = temp->next;
       }
       cout<<endl;
   }

};

int main()
{
   item<int>* i = new item<int>(1);
   dLL<int> DLL;

   DLL.push(i);
   DLL.push(new item<int>(2));

   cout<<"The List after inserting two elements:"<<endl;
   DLL.printList();

   DLL.push(new item<int>(5));
   DLL.push(new item<int>(4));
   DLL.push(new item<int>(3));

   cout<<"The List after inserting the rest of the elements:"<<endl;  
   DLL.printList();

   item<int>* temp = DLL.pop();

   cout<<"The deleted node data: "<<temp->getData()<<endl;  

   cout<<"The List after popping the top node:"<<endl;
   DLL.printList();
  
   if(temp != NULL)
   {
       delete temp;
       temp = NULL;
   }

   temp = DLL.getItem(2);

   cout<<"The data at position 2: "<<temp->getData()<<endl;

   cout<<"Peek at the top item: "<<DLL.peek()->getData()<<endl;

   cout<<"Max Node: "<<DLL.maxNode()<<endl;

   cout<<"Size of DLL: "<<DLL.getSize()<<endl;

   return 1;
}

Output:

The List after inserting two elements:
2,1
The List after inserting the rest of the elements:
3,4,5,2,1
The deleted node data: 3
The List after popping the top node:
4,5,2,1
Item Deleted
The data at position 2: 2
Peek at the top item: 4
Max Node: 5
Size of DLL: 4
Item Deleted
Item Deleted
Item Deleted
Item Deleted