• 1

• 35.2k
• 13
• 134
• 238

• 173
• 7

The struct and the prototypes of the functions were given in the question. I am unfortunately aware that this is more C code and less C++ code.

I look forward to reading your comments. Regards.

Version 1.0: Singly linked list

#include <iostream>
using namespace std;
struct node_ll
{
 int payload;
 node_ll* next;//Pointer to the next node
};
void print_ll (node_ll** list)
{
 node_ll* temp = *list;
 while(temp)
 {
 cout << temp->payload << endl;
 temp = temp->next;
 }
}
void head_insert(node_ll** list, int pload)
{
 node_ll *node = new node_ll;
 node->payload = pload;
 node->next = *list;
 *list = node;
};
void tail_insert(node_ll** list, int pload)
{
 if (!*list)
 {
 head_insert(list, pload);
 }
 else
 {
 node_ll* temp = *list;
 while(temp->next)
 {
 temp = temp->next;
 }
 head_insert(&temp->next, pload);
 }
}
int head_return (node_ll** list)
{
 if (!*list)
 {
 return -1;//Error: List is empty.
 }
 node_ll* trash = *list;
 int i = trash->payload;
 *list = trash->next;
 delete trash;
 return i;
}
int tail_return (node_ll** list)
{
 if (!*list)
 {
 return -1;//Error: List is empty.
 }
 if (!(*list)->next)
 {
 return head_return(list);
 }
 else
 {
 node_ll* temp = *list;
 while(temp->next->next)
 {
 temp = temp->next;
 }
 return head_return(&temp->next);
 }
}
bool ordered_list(node_ll** list)
{
 if (!*list || !(*list)->next)
 {
 return true;
 }
 if ((*list)->payload < (*list)->next->payload)
 {
 return ordered_list(&(*list)->next);
 }
 else
 {
 return false;
 }
}
void ordered_insert(node_ll** list, int pload)
{
 if (!ordered_list(list))
 {
 return;//Error: List is not ordered;
 }
 if (!*list || (*list)->payload > pload)//If list is null or first payload is greater than new payload.
 {
 head_insert(list, pload);
 }
 else
 {
 node_ll* temp = *list;
 while(temp->next)
 {
 if (temp->next->payload > pload)
 {
 head_insert(&temp->next, pload);
 return;
 }
 temp = temp->next;
 }
 head_insert(&temp->next, pload);//If all payloads are less than or equal to new payload.
 }
}
void find_remove (node_ll** list, int pload)
{
 if (!*list)
 {
 return;//List is empty.
 }
 while (*list && (*list)->payload == pload)//While loop required as node will become node->next on head_return(node).
 {
 head_return(list);
 }
 if (*list && (*list)->next)
 {
 find_remove(&(*list)->next, pload);
 }
}
int main()
{
 node_ll* alist = NULL;
 cout << "Empty list a to start." << endl;
 head_insert(&alist, 2);
 head_insert(&alist, 4);
 head_insert(&alist, 6);
 cout << "List a after head insertion of 2,4,6 is: " << endl;
 print_ll(&alist);
 cout << "Tail return: " << tail_return(&alist) << endl;
 cout << "Tail return: " << tail_return(&alist) << endl;
 cout << "Tail return: " << tail_return(&alist) << endl;
 cout << "Tail return: " << tail_return(&alist) << endl;
 cout << endl;
 node_ll* blist = NULL;
 cout << "Empty list b to start." << endl;
 tail_insert(&blist, 2);
 tail_insert(&blist, 4);
 tail_insert(&blist, 6);
 cout << "List b after tail insertion of 2,4,6 is: " << endl;
 print_ll(&blist);
 cout << "Head return: " << head_return(&blist) << endl;
 cout << "Head return: " << head_return(&blist) << endl;
 cout << "Head return: " << head_return(&blist) << endl;
 cout << "Head return: " << head_return(&blist) << endl;
 cout << endl;
 node_ll*clist = NULL;
 cout << "Empty list c to start." << endl;
 tail_insert(&clist, 2);
 tail_insert(&clist, 4);
 tail_insert(&clist, 6);
 cout << "List c after tail insertion of 2,4,6 is: " << endl;
 print_ll(&clist);
 if (ordered_list(&clist))
 {
 cout << "List c is ordered." << endl;
 }
 else
 {
 cout << "List c is not ordered." << endl;
 }
 ordered_insert(&clist, 1);
 ordered_insert(&clist, 3);
 ordered_insert(&clist, 7);
 cout << "List c after ordered insertion of 1,3,7 is: " << endl;
 print_ll(&clist);
 cout << endl;
 node_ll* dlist = NULL;
 cout << "Empty list d to start." << endl;
 tail_insert(&dlist, 2);
 tail_insert(&dlist, 2);
 tail_insert(&dlist, 3);
 tail_insert(&dlist, 4);
 tail_insert(&dlist, 4);
 tail_insert(&dlist, 9);
 tail_insert(&dlist, 6);
 tail_insert(&dlist, 6);
 cout << "List d after tail insertion of 2,2,3,4,4,5,6,6 is: " << endl;
 print_ll(&dlist);
 if (ordered_list(&dlist))
 {
 cout << "List d is ordered." << endl;
 }
 else
 {
 cout << "List d is not ordered." << endl;
 }
 find_remove(&dlist, 2);
 find_remove(&dlist, 4);
 find_remove(&dlist, 6);
 cout << "List c after find and remove of 2,4,6 is: " << endl;
 print_ll(&dlist);
 cout << endl;
 system("PAUSE");
 return 0;
}