Question

In this assignment you will use pointers and structures to create Single and double link list. Write a menu driven program with the menu options:
1. Insert in Linked List
      1. Insert in Single linked list
             1. Insert at front(head)
             2. Insert at Index
             3. Insert at end(tail)
      2. Insert in double linked list
             1. Insert at front(head)
             2. Insert at Index
             3. Insert at end(tail)
2. Print
      1. Print linked list
      2. Print double linked list in reverse order after           calculating the cube of each element.
3. Delete in both linked list
       1. deletion at front(head)
       2. deletion at Index
       3. deletion at end(tail)
4. Return maximum data from single/double linked list
5. Count the number of nodes in linked list
6. Find the sum of all node
7. Check if elements stored in Linked list make a Palindrome. (like 1221, 3333, 2442)
8. Return Minimum data from single/ double linked list
9. Exit

Note ::: Program should be implemented in C++ with, pointers and functions   Each menu option should be implemented in separate function. Try to terminate insertion in linked list according to user’s choice.

Answer 1

#include <iostream>

using namespace std;
/*----Function Prototypes-----*/
struct node
{
int info;
struct node *next;
};

struct Dnode
{
struct Dnode *prev;
int n;
struct Dnode *next;
}*h,*temp,*temp1,*temp2,*temp4;

void insert_first();
void insert_last();
void insert_position();
void traversebeg();

void display();
void insert_begin();
void insert_end();
void insert_index();
void delete_begin();
void delete_end();
void delete_index();
int getCount(struct node*);
int smallestElement(struct node*);
int largestElement(struct node*);
int sumOfNodes(struct node* ) ;
void traverseend(int);
int palin_check(struct node*,int);
/*-----------------------------*/
int count=0;
struct node *start=NULL;
int main() //main() starts
{
int choice;
int count;
int max,min;
int Ichoice;
int pchoice;
int Dchoice;
int insertion_type;
int dchoice;
int result;
h = NULL;
temp = temp1 = NULL;
  
while(1){

cout<<"\n MENU \n";
cout<<"---------------------------------------";
cout<<"\n 1.Insert ";
cout<<"\n 2.Display ";
cout<<"\n 3.Delete ";
cout<<"\n 4.Maximum number int he list ";
cout<<"\n 5. Count the number of nodes in linked list ";
cout<<"\n 6.sum of the nodes in the list";
cout<<"\n 7.Check if elements stored in Linked list make a Palindrome";
cout<<"\n 8.minimum number in the list ";
cout<<"\n 9.Exit ";
cout<<"\n--------------------------------------";
cout<<"\nEnter your choice:\t";
cin>>choice;
switch(choice)
{
case 1:
cout<<"\n 1.Insertion in Single Linked list";
cout<<"\n 2.Insertion in Double linked list";
cout<<"\nEnter your choice:\t";
cin>>insertion_type;
switch(insertion_type)
{
case 1:
cout<<"\n 1.Insert at the beginning \n";
cout<<"\n 2.Insert at the end \n";
cout<<"\n 3.Insert at specified position \n";
cout<<"Enter your choice:\t";
cin>>Ichoice;
switch(Ichoice){

case 1:
insert_begin();
break;
case 2:
insert_end();
break;
case 3:
insert_index();
break;
}break;
case 2:
cout<<"\n 1.Insert at the beginning \n";
cout<<"\n 2.Insert at the end \n";
cout<<"\n 3.Insert at specified position \n";
cout<<"Enter your choice:\t";
cin>>Ichoice;
switch(Ichoice){

case 1:
insert_first();
break;
case 2:
insert_last();
break;
case 3:
insert_position();
break;
}
}
  

break;
case 2:
  
cout<<"\n 1. disply elements in the single list";
cout<<"\n 2. Print double linked list in reverse order after calculating the cube of each element.";
cout<<"\nEnter your choice:\t";
cin>>pchoice;
switch(pchoice){
case 1:
display();
break;
case 2:
temp2 = h;
if (temp2 == NULL)
cout<<"\n Error : List empty to display ";
else
{
cout<<"\n Reverse order of linked list is : ";
traverseend(temp2->n);
}
  
}break;

  
case 3:
cout<<"\n 1.Delete from beginning \n";
cout<<"\n 2.Delete from the end \n";
cout<<"\n 3.Delete from specified position \n";
cout<<"Enter your choice:\t";
cin>>Dchoice;
switch(Dchoice){
case 1:
delete_begin();
break;
case 2:
delete_end();
break;
case 3:
delete_index();
break;
}break;
  
  
case 4:
max=largestElement(start);
cout<<"Maximum number in the list is="<<max;
break;

case 5:
count=getCount(start);
cout<<"count ="<<count;
break;
  
case 6:
sumOfNodes(start);
break;
  
case 7:
count=getCount(start);
result = palin_check(start, count);
if (result == 1)
{
printf("The linked list is a palindrome.\n");
}
else
{
printf("The linked list is not a palindrome.\n");
}
  
case 8:
  
min=smallestElement(start);
cout<<"Minimun number in the list id="<<min;
break;
case 9:
exit(0);
break;

default:
cout<<"\n Wrong Choice:\n";
break;
}//end of switch()
}
return 0;
}//end of main()
void create()
{
struct node *temp,*ptr;
temp=(struct node *)malloc(sizeof(struct node));
if(temp==NULL)
{
printf("\nOut of Memory Space:\n");
exit(0);
}
printf("\nEnter the data value for the node:\t");
scanf("%d",&temp->info);
temp->next=NULL;
if(start==NULL)
{
start=temp;
}
else
{
ptr=start;
while(ptr->next!=NULL)
{
ptr=ptr->next;
}
ptr->next=temp;
}
}//end of create()
void display()
{
struct node *ptr;
if(start==NULL)
{
printf("\nList is empty:\n");
return;
}
else
{
ptr=start;
printf("\nThe List elements are:\n");
while(ptr!=NULL)
{
printf("%d\t",ptr->info );
ptr=ptr->next ;
}//end of while
}//end of else
}//end of display()
void insert_begin()
{
struct node *temp;
temp=(struct node *)malloc(sizeof(struct node));
if(temp==NULL)
{
printf("\nOut of Memory Space:\n");
return;
}
printf("\nEnter the data value for the node:\t" );
scanf("%d",&temp->info);
temp->next =NULL;
if(start==NULL)
{
start=temp;
}
else
{
temp->next=start;
start=temp;
}
}//end of insert_begin()
void insert_end()
{
struct node *temp,*ptr;
temp=(struct node *)malloc(sizeof(struct node));
if(temp==NULL)
{
printf("\nOut of Memory Space:\n");
return;
}
printf("\nEnter the data value for the node:\t" );
scanf("%d",&temp->info );
temp->next =NULL;
if(start==NULL)
{
start=temp;
}
else
{
ptr=start;
while(ptr->next !=NULL)
{
ptr=ptr->next ;
}
ptr->next =temp;
}
}//end of insert_end
void insert_index()
{
struct node *ptr,*temp;
int i,pos;
temp=(struct node *)malloc(sizeof(struct node));
if(temp==NULL)
{
printf("\nOut of Memory Space:\n");
return;
}
printf("\nEnter the position for the new node to be inserted:\t");
scanf("%d",&pos);
printf("\nEnter the data value of the node:\t");
scanf("%d",&temp->info) ;

temp->next=NULL;
if(pos==0)
{
temp->next=start;
start=temp;
}
else
{
for(i=0,ptr=start;i<pos-1;i++)
{
ptr=ptr->next;
if(ptr==NULL)
{
printf("\nPosition not found:[Handle with care]\n");
return;
}
}
temp->next =ptr->next ;
ptr->next=temp;
}//end of else
}//end of insert_pos
void delete_begin()
{
struct node *ptr;
if(ptr==NULL)
{
printf("\nList is Empty:\n");
return;
}
else
{
ptr=start;
start=start->next ;
printf("\nThe deleted element is :%d\t",ptr->info);
free(ptr);
}
}//end of delete_begin()
void delete_end()
{
struct node *temp,*ptr;
if(start==NULL)
{
printf("\nList is Empty:");
exit(0);
}
else if(start->next ==NULL)
{
ptr=start;
start=NULL;
printf("\nThe deleted element is:%d\t",ptr->info);
free(ptr);
}
else
{
ptr=start;
while(ptr->next!=NULL)
{
temp=ptr;
ptr=ptr->next;
}
temp->next=NULL;
printf("\nThe deleted element is:%d\t",ptr->info);
free(ptr);
}
}//end of delete_begin()
void delete_index()
{
int i,pos;
struct node *temp,*ptr;
if(start==NULL)
{
printf("\nThe List is Empty:\n");
exit(0);
}
else
{
printf("\nEnter the position of the node to be deleted:\t");
scanf("%d",&pos);
if(pos==0)
{
ptr=start;
start=start->next ;
printf("\nThe deleted element is:%d\t",ptr->info );
free(ptr);
}
else
{
ptr=start;
for(i=0;i<pos;i++)
{
temp=ptr;
ptr=ptr->next ;
if(ptr==NULL)
{
printf("\nPosition not Found:\n");
return;
}
}
temp->next =ptr->next ;
printf("\nThe deleted element is:%d\t",ptr->info );
free(ptr);
}
}//end of else
}//end of delete_pos()

/* TO create an empty node */
void createDouble()
{
int data;

temp =(struct Dnode *)malloc(1*sizeof(struct Dnode));
temp->prev = NULL;
temp->next = NULL;
printf("\n Enter value to node : ");
scanf("%d", &data);
temp->n = data;
count++;
}

/* TO insert at beginning */
void insert_first()
{
if (h == NULL)
{
createDouble();
h = temp;
temp1 = h;
}
else
{
createDouble();
temp->next = h;
h->prev = temp;
h = temp;
}
}

/* To insert at end */
void insert_last()
{
if (h == NULL)
{
createDouble();
h = temp;
temp1 = h;
}
else
{
createDouble();
temp1->next = temp;
temp->prev = temp1;
temp1 = temp;
}
}

/* To insert at any position */
void insert_position()
{
int pos, i = 2;

printf("\n Enter position to be inserted : ");
scanf("%d", &pos);
temp2 = h;

if ((pos < 1) || (pos >= count + 1))
{
printf("\n Position out of range to insert");
return;
}
if ((h == NULL) && (pos != 1))
{
printf("\n Empty list cannot insert other than 1st position");
return;
}
if ((h == NULL) && (pos == 1))
{
createDouble();
h = temp;
temp1 = h;
return;
}
else
{
while (i < pos)
{
temp2 = temp2->next;
i++;
}
createDouble();
temp->prev = temp2;
temp->next = temp2->next;
temp2->next->prev = temp;
temp2->next = temp;
}
}
//display form end
void traverseend(int i)
{
if (temp2 != NULL)
{
i = temp2->n;
temp2 = temp2->next;
traverseend(i);
cout<< i*i*i;
}
}
/* Counts no. of nodes in linked list */
int getCount(struct node* start)
{
int count = 0; // Initialize count
struct node* current = start; // Initialize current
while (current != NULL)
{
count++;
current = current->next;
}
return count;
}
int largestElement(struct node* head)
{

int max = -99999999;
  
// Check loop while head not equal to NULL
while (head != NULL) {
  
if (max < head->info)
max = head->info;
head = head->next;
}
return max;
}
  
// Function that returns smallest element

int smallestElement(struct node* head)
{

int min = 999999;
  
// Check loop while head not equal to NULL
while (head != NULL) {
  

if (min > head->info)
min = head->info;
  
head = head->next;
}
return min;
} //minimum numbe in the list

int sumOfNodes(struct node* head)
{
// if head = NULL
if (!head)
return -1;
  
  
int sum = 0;
  
  
struct node* current = head; // Initialize current
while (current != NULL) {

sum += current->info;
current = current->next;
}
  
// calculate average

  
return sum;
}//sum of all nodes in list
//palindrom or not checking
int palin_check (struct node *p, int count)
{
int i = 0, j;
struct node *front, *rear;

while (i != count / 2)
{
front = rear = p;
for (j = 0; j < i; j++)
{
front = front->next;
}
for (j = 0; j < count - (i + 1); j++)
{
rear = rear->next;
}
if (front->info != rear->info)
{
return 0;
}
else
{
i++;
}
}

return 1;
}