Question
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
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;
}
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started