In: Computer Science
2.2.1
cLL
The class is described according to the simple UML diagram
below:
2cLL<T>
-head:item<T> *
-size:int
------------------------
+cLL()
+~cLL()
+isEmpty():bool
+getSize():int
+push(newItem: item<T>*):void
+pop():item<T>*
+removeAt(x:T):item<T> *
+printList():void
The class variables are as follows:
• head: The head pointer for the linked list.
• size: The current size of the circular linked list. It starts at
0 and grows as the list
does.
The class methods are as follows:
• cLL: The constructor. It will set the size to 0 and initialise
head as null.
• ∼cLL: The class destructor. It will iterate through the circular
linked list and
deallocate all of the memory assigned for the items.
• isEmpty: This function returns a bool. If the circular linked
list is empty, then it
will return true. Otherwise, if it has items then it will return
false.
• getSize: This returns the current size of the circular linked
list. If the list is empty
the size should be 0.
• push: This receives a new item and adds it to the circular linked
list. It is added to
the front of the list. The front in this case refers to the
head.
• pop: This receives, and returns, the first element in the list.
The first element is
removed from the list in the process. If the list is empty, return
null. The first
element referring to the head pointer in this case.
• removeAt: This will remove an item from the linked list based on
its value. If
the value is not found, nothing should be removed. Also note that
in the event of
multiple values being found, the first one in the list, from head,
should be removed.
Note that nothing is deleted. Instead the node must be removed
through relinking
and then returned.
• printList: This will print out the entire list from head onwards.
The output consists
of a single comma delimited line, with a newline at the end. For
example:
1,2,3,4,5
32.2.2
item
The class is described according to the simple UML diagram
below:
item <T>
-data:T
-------------------
+item(t:T)
+~item()
+next: 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.
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.
// C++ program to create a circular linked list
#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;
T getData();
};
// constructor
template <class T>
item<T>::item(T t)
{
data = t;
next = 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
template <class T>
class cLL
{
private:
item<T> *head;
int size;
public:
cLL();
~cLL();
bool isEmpty();
void push(item<T>* newItem);
item<T>* pop();
item<T>* removeAt(T x);
int getSize();
void printList();
};
// default constructor
template <class T>
cLL<T>::cLL()
{
head = NULL;
size = 0;
}
// destructor
template <class T>
cLL<T>::~cLL()
{
if(head != NULL)
{
item<T> *curr =
head->next;
// loop over the linked list
while(curr != head)
{
item<T>
*temp = curr; // get the current head
curr =
curr->next; // set head to pointer next to head
delete(temp); //
delete the old head
}
delete(head);
head = NULL;
size = 0;
}
}
// function to return true if the list is empty else false
template <class T>
bool cLL<T>::isEmpty()
{
return(head == NULL);
}
// function to insert the element as the first element of the
list
template <class T>
void cLL<T>::push(item<T>* newItem)
{
if(head == NULL) // empty list
{
head = newItem;
head->next = head;
}else
{
item<T> *curr =
head->next;
// loop to get the last element of
the list
while(curr->next != head)
curr =
curr->next;
curr->next = newItem; // update
the next pointer of the last node
// insert the new node as the head
node
newItem->next = head;
head = newItem;
}
size++; // increment the size
}
// function to remove and return the first node of the
list
template <class T>
item<T>* cLL<T>:: pop()
{
// list is empty
if(isEmpty())
return NULL;
else
{
item<T> *node =
head;
// if one element
if(head->next == head)
head =
NULL;
else
{
item<T>
*curr = head->next;
// loop to get
the last element of the list
while(curr->next != head)
curr = curr->next;
// update the
next pointer of last node
curr->next =
head->next;
// update the
head
head =
head->next;
}
size--; // decrement the size
return node;
}
}
// function to remove the node with data x
template <class T>
item<T>* cLL<T>::removeAt(T x)
{
if(isEmpty()) // empty list
{
return NULL;
}else if(head->getData() == x) // if x is present
in head, call pop
{
return pop();
}else
{
item<T> *curr =
head->next;
item<T> *prev = head;
// loop to get the node with data
x
while(curr != head)
{
// if curr's
data is x
if(curr->getData() == x)
{
prev->next = curr->next; // update the
enxt pointer of prev node
size--; // decrement the size
return curr; // return the curr node
}
prev = curr;
// set prev to curr
curr =
curr->next; // set curr to next of curr
}
return NULL;
}
}
// function to return the size of the list
template <class T>
int cLL<T>::getSize()
{
return size;
}
// function to print the list
template <class T>
void cLL<T>::printList()
{
if(isEmpty()) // empty list
{
cout<<"Empty
list"<<endl;
}else if(head->next == head) // single node
list
{
cout<<head->getData()<<endl;
}else
{
item<T> *curr = head;
// loop to print the list
while(curr->next != head)
{
cout<<curr->getData()<<",";
curr =
curr->next;
}
cout<<curr->getData()<<endl;
}
}
//end of cLL