(In C++) For this assignment create a simple double linked structures consisting
ID: 3835196 • Letter: #
Question
(In C++) For this assignment create a simple double linked structures consisting of Node objects. Each node will have a pointer to the next node and a pointer to the previous node. You will use a head pointer to keep track of the first node in the linked list, and a tail pointer to keep track of the last node in the linked list. Set both head and tail to NULL when the list is empty. You will store an integer in each node. You can assume all the integers are positive numbers. You will create the list dynamically by user input.
Implement following functions in the linked list:
Add a new node to the head;
Add a new node to the tail;
Delete from head (the first node in the list);
Delete from tail (the last node in the list);
Traverse the list reversely, that is to print the node from back to the forth.
When user tries to add a new node (functions 1&2), your program will prompt the user to enter a number and validate the input, create a new node in the list, store the value properly, change the head/tail pointers and print the current whole list from head to the tail.
When user tries to delete a node (functions 3&4), your program should check whether the list is empty, if so, give a warning message, and if not, delete the node properly and free the memory, then point the head/tail pointers to the new position, and print out the whole list.
When user tries to print the list from tail to the head (functions 5), your program will print the value from the last node to the first node. If the list is empty, print a message to indicate that.
You need to add one more option in your menu to exit the program.
For this lab, you will not implement the linked list operations using functions/methods that from an outside source. That means you need to write all the functions by yourself.
Example running:
Welcome to my linked list!
Choose from following options:
Add a new node to the head;
Add a new node to the tail;
Delete from head;
Delete from tail;
Traverse the list reversely;
Exit.
1
Please enter a positive integer:
15
Your linked list is: 10
Choose from following options:
Add a new node to the head;
Add a new node to the tail;
Delete from head;
Delete from tail;
Traverse the list reversely;
Exit.
1
Please enter a positive integer:
10
Your linked list is: 5 10
Choose from following options:
Add a new node to the head;
Add a new node to the tail;
Delete from head;
Delete from tail;
Traverse the list reversely;
Exit.
2
Please enter a positive integer:
5
Your linked list is: 10 15 5
Choose from following options:
Add a new node to the head;
Add a new node to the tail;
Delete from head;
Delete from tail;
Traverse the list reversely;
Exit.
5
Your linked list is: 5 15 10
Choose from following options:
Add a new node to the head;
Add a new node to the tail;
Delete from head;
Delete from tail;
Traverse the list reversely;
Exit.
4
Your linked list is: 10 15
Explanation / Answer
/*
* C++ Program to Implement Singly Linked List
*/
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
/*
* Node Declaration
*/
struct node
{
int info;
struct node *next;
}*start;
/*
* Class Declaration
*/
class single_llist
{
public:
node* create_node(int);
void insert_begin();
void insert_last();
void delete_pos();
void delete_pos_end();
void reverse();
void display();
single_llist()
{
start = NULL;
}
};
/*
* Main :contains menu
*/
main()
{
int choice, nodes, element, position, i;
single_llist sl;
start = NULL;
cout<<endl<<"Welcome to my linked list!"<<endl;
while (1)
{
cout<<endl<<"Choose from following options:"<<endl;
cout<<"Add a new node to the head;"<<endl;
cout<<"Add a new node to the tail;"<<endl;
cout<<"Delete from head;"<<endl;
cout<<"Delete from tail;"<<endl;
cout<<"Traverse the list reversely;"<<endl;
cout<<"Exit."<<endl;
cout<<"Enter your choice : ";
cin>>choice;
switch(choice)
{
case 1:
sl.insert_begin();
cout<<endl;
sl.display();
cout<<endl;
break;
case 2:
sl.insert_last();
cout<<endl;
sl.display();
cout<<endl;
break;
case 3:
sl.delete_pos();
cout<<endl;
sl.display();
cout<<endl;
break;
case 4:
sl.delete_pos_end();
cout<<endl;
sl.display();
cout<<endl;
break;
case 5:
sl.reverse();
cout<<endl;
sl.display();
cout<<endl;
break;
case 6:
exit(1);
break;
default:
cout<<"Wrong choice"<<endl;
}
}
}
/*
* Creating Node
*/
node *single_llist::create_node(int value)
{
struct node *temp, *s;
temp = new(struct node);
if (temp == NULL)
{
cout<<"Memory not allocated "<<endl;
return 0;
}
else
{
temp->info = value;
temp->next = NULL;
return temp;
}
}
/*
* Inserting element in beginning
*/
void single_llist::insert_begin()
{
int value;
cout<<"Please enter a positive integer:"<<endl;
cin>>value;
struct node *temp, *p;
temp = create_node(value);
if (start == NULL)
{
start = temp;
start->next = NULL;
}
else
{
p = start;
start = temp;
start->next = p;
}
//cout<<"Element Inserted at beginning"<<endl;
}
/*
* Inserting Node at last
*/
void single_llist::insert_last()
{
int value;
cout<<"Please enter a positive integer:"<<endl;
cin>>value;
struct node *temp, *s;
temp = create_node(value);
s = start;
while (s->next != NULL)
{
s = s->next;
}
temp->next = NULL;
s->next = temp;
//cout<<"Element Inserted at last"<<endl;
}
/*
* Delete element at a End
*/
void single_llist::delete_pos_end()
{
if (start == NULL)
{
cout<<"List is empty"<<endl;
return;
}
struct node *s;
s = start;
if(s->next!=NULL)
{
while (s->next->next != NULL)
{
s = s->next;
}
if(s->next->next==NULL)
s->next=NULL;
}
}
/*
* Delete element at head
*/
void single_llist::delete_pos()
{
if (start == NULL)
{
cout<<"List is empty"<<endl;
return;
}
struct node *s;
s = start;
start = s->next;
}
/*
* Reverse Link List
*/
void single_llist::reverse()
{
struct node *ptr1, *ptr2, *ptr3;
if (start == NULL)
{
cout<<"List is empty"<<endl;
return;
}
if (start->next == NULL)
{
return;
}
ptr1 = start;
ptr2 = ptr1->next;
ptr3 = ptr2->next;
ptr1->next = NULL;
ptr2->next = ptr1;
while (ptr3 != NULL)
{
ptr1 = ptr2;
ptr2 = ptr3;
ptr3 = ptr3->next;
ptr2->next = ptr1;
}
start = ptr2;
}
/*
* Display Elements of a link list
*/
void single_llist::display()
{
struct node *temp;
if (start == NULL)
{
cout<<"The List is Empty"<<endl;
return;
}
temp = start;
cout<<"Your linked list is:"<<endl;
while (temp != NULL)
{
cout<<temp->info<<" ";
temp = temp->next;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.