In this lab, you will implement a circular linked list.

The circular linked list is almost same as normal singly linked list but its last node should point to the first node instead of NULL

You have to modify the lab4.cpp

Do NOT change anything in main function

Do NOT change any of the function prototypes. I have changed the regular prototypes (discussed in lecture) for your brain storming. For example, instead of void all the functions in this lab (except traverse) should return the last node of the list.

You should NOT use any head pointer or any other external pointer

Submit to the grader before the grace date. You will not loose any point for missing due date. However, you will lose points severely if you change the function prototype, any hardcoded output or match the output with any other data structure than circular linked list, etc.

Expected output for the main function:

The list from the first node: 2 4 6 8 12

Last element: 12

After 2 hops of circular movement: 4

The list from the first node:12 2 4 6 8 12 12 12

CODE

#include

using namespace std;

//struct is defined globally.

struct Node

{

int data;

Node *next;

};

class CircularLinkedList

{

//All the functions should return the last node of the list

//other than the traverse function.

//addToEmpty (insert a node in an empty list) is a basic function.

//In this function, I wrote each steps in DOs.

//So, follow the Do's of this function line by line.

//In the other functions, you do not have as many DOs.

//It is up to you to figure out the algorithm and its steps

public:

//Function to add a node in an empty list

Node *addToEmpty(Node *last, int data)

{

//Do1: If the last is not NULL

// return the last node

if (last != NULL)

return

//Do2: Create a node dynamically.

//Do3: Assign the data.

//Do4: Set n as last node

//Do5: Set the next properly.

// Figure out where should you point it

// when there is only one node

return last;

}

Node *addBegin(struct Node *last, int data)

{

//if last is null then return addToEmpty

if (last == NULL)

return addToEmpty(last, data);

//Do1: Insert a node in the beginning

return last;

}

Node *addEnd(struct Node *last, int data)

{

//if last is null then return addToEmpy

if (last == NULL)

return addToEmpty(last, data);

//Do1: Steps for adding a node in the end

return last;

}

void traverse(struct Node *last)

{

Node *p;

// If list is empty, return.

if (last == NULL)

{

cout << "List is empty." << endl;

return;

}

//Do1: Traverse the list from the first node

}

};

//Do NOT change the main function

int main()

{

CircularLinkedList *cll = new CircularLinkedList();

Node *last = NULL;

//last should always store the pointers to the last node

last = cll->addToEmpty(last, 6);

last = cll->addBegin(last, 4);

last = cll->addBegin(last, 2);

last = cll->addEnd(last, 8);

last = cll->addEnd(last, 12);

cout << "The list from the first node: ";

cll->traverse(last);

cout << endl;

cout << "Last element: " << last->data << endl;

cout << "After 2 hops of circular movement: " << last->next->next->data << endl;

cout << "The list from the first node:";

last = cll->addBegin(last, 12);

last = cll->addEnd(last, 12);

last = cll->addEnd(last, 12);

cll->traverse(last);

return 0;

}