In C++, i\'m trying to get my linked list program to run and complete four cases
ID: 3743161 • Letter: I
Question
In C++, i'm trying to get my linked list program to run and complete four cases. Please use the format and functions of my code so that I can better understand.
Case 0: The linked list current state is NULL (empty), A node with a new number should be the only one and be first in the list.
Case 1: A new number is inserted into the linked list and is smaller than the smallest item in the list. The new number should go at
the front of the list.
Case 2: The new number is larger than all of the numbers in the list. The new number
should go at the end of the list.
Case 3: The new number should be inserted inserted in the middle of the link list.
CODE:
#include <iostream>
using namespace std;
struct node
{
int number;
node* next;
};
bool isNull(node *&first);
char menu();
void insertFirst(node *&first, node *&last, int number);
void insert(node *&first, node *&last, int number);
void remove(node *&first, node *&last);
void printList(node *current);
bool isNull(node *&first)
{
if(first == NULL)
return true;
else
return false;
}
char menu()
{
char selection;
cout << "Menu Selection";
cout << "1. Add an item. ";
cout << "2. Remove an item. ";
cout << "3. Show list. ";
cout << "4. Exit system. ";
cin >> selection;
return selection;
}
void insertFirst(node *&first, node *&last, int number)
{
node *temp = new node;
temp->number = number;
temp->next= NULL;
first=temp;
last=temp;
}
void insert(node *&first, node *&last, int number)
{
if(isNull(first))
insertFirst(first, last, number);
else
{
node *temp = new node;
temp->number = number;
temp->next=NULL;
last->next=temp;
last=temp;
}
}
void remove(node *&first, node *&last)
{
if(isNull(first))
cout << "The list is already empty. ";
else if (first == last)
{
delete first;
first == NULL;
last == NULL;
}
else
{
node *temp = first;
first = first->next;
delete temp;
}
}
void printList(node *current)
{
if(isNull(current))
cout << "The list is empty ";
else
{
cout << "The list contatins: ";
while(current != NULL)
{
cout <<current->number << endl;
current = current->next;
}
}
}
int main ()
{
node *first = NULL;
node *last = NULL;
char selection;
int number;
do {
selection = menu();
switch(selection)
{
case '1': cout << "Please enter a selection number: ";
cin >> number;
insert(first, last, number);
break;
case '2': remove(first, last);
break;
case '3': printList(first);
break;
default: cout<< "System exit ";
}
} while(selection != '4');
return 0;
}
Explanation / Answer
#include <iostream>
using namespace std;
struct node
{
int number;
node* next;
};
bool isNull(node *&first);
int menu();
void insertFirst(node *&first, node *&last, int number);
void insert(node *&first, node *&last, int number);
void remove(node *&first, node *&last);
void printList(node *current);
bool isNull(node *&first)
{
// if the list is empty
if(first == NULL)
return true;
// if the list is not empty
else
return false;
}
int menu()
{
int selection;
cout << "Menu Selection ";
cout << "1. Add an item. ";
cout << "2. Remove an item. ";
cout << "3. Show list. ";
cout << "4. Exit system. ";
cin >> selection;
return selection;
}
int getLength(node *first)
{
node *trav = first;
int count = 0;
// loop untill list ends
while( trav )
{
count++;
// go to next node
trav = trav->next;
}
return count;
}
void insertFirst(node *&first, node *&last, int number)
{
// create a new node
node *temp = new node;
// The linked list current state is NULL (empty), A node with a new number should be the only one
// and be first in the list.
if( first == NULL )
temp->number = 1;
else
temp->number = number;
// make temp point to current first node of the list
temp->next= first;
// make temp as the new first node
first=temp;
// if the list was empty
if( last == NULL )
last=temp;
}
// check if x is the smaller than smallest number in list
bool ifSmallest( node *first , int x )
{
node *trav = first;
// loop untill list ends
while( trav )
{
// if x is not the smallest
if( trav->number < x )
return false;
// go to next node
trav = trav->next;
}
return true;
}
// check if x is the larger than largest number in list
bool ifLargest( node *first , int x )
{
node *trav = first;
// loop untill list ends
while( trav )
{
// if x is not the largest
if( trav->number > x )
return false;
// go to next node
trav = trav->next;
}
return true;
}
void insert(node *&first, node *&last, int number)
{
if(isNull(first))
insertFirst(first, last, number);
// if number is smaller than the smallest number in the list
else if( ifSmallest(first , number) )
insertFirst(first, last, number);
// if number is larger than the largest number in the list
// node goes at the last of the list
else if(ifLargest(first , number) )
{
node *temp = new node;
temp->number = number;
temp->next=NULL;
last->next=temp;
last=temp;
}
// The new number should be inserted inserted in the middle of the link list.
else
{
// get the length of the list
int len = getLength(first);
node *trav = first;
int i;
// go to the node before the middle node
for( i = 0 ; i < len - 2 ; i++ )
trav = trav->next;
// adjust the pointer
node *temp = new node;
temp->number = number;
temp->next=trav->next;
trav->next = temp;
}
}
void remove(node *&first, node *&last)
{
if(isNull(first))
cout << "The list is already empty. ";
else if (first == last)
{
delete first;
first == NULL;
last == NULL;
}
else
{
node *temp = first;
first = first->next;
delete temp;
}
}
void printList(node *current)
{
if(isNull(current))
cout << "The list is empty ";
else
{
cout << "The list contatins: ";
while(current != NULL)
{
cout <<current->number << endl;
current = current->next;
}
}
}
int main ()
{
node *first = NULL;
node *last = NULL;
int selection;
int number;
do {
selection = menu();
switch(selection)
{
case 1: cout << "Please enter a selection number: ";
cin >> number;
insert(first, last, number);
break;
case 2: remove(first, last);
break;
case 3: printList(first);
break;
case 4 : exit(0);
default: cout<< "System exit ";
}
} while(selection != '4');
return 0;
}