Question

Create a linked list of at least 15 different values that are prompted for and entered while the program is running. Appending a node attaches that node to the end of the list while inserting a node places it in order maintaining a sorted list. Create a menu driven program where you have the options to appended, insert, display, and delete a node. Display the list after first appending data showing it in no specific order, delete all nodes and then insert nodes and display them. You will see that the inserted nodes are all in ascending order.

Answer 1

C++ program :-

#include <bits/stdc++.h>
using namespace std;
  
// A linked list node
class Node
{
public:
int data;
Node *next;
};
  
void push(Node** head_ref, int new_data)
{
Node* new_node = new Node();
  
new_node->data = new_data;
  
new_node->next = (*head_ref);
  
(*head_ref) = new_node;
}

void deletelist(Node** head_ref)
{
Node* current = *head_ref;
Node* next;
  
while (current != NULL)
{
next = current->next;
free(current);
current = next;
}
*head_ref = NULL;
}
  
  
void insert(struct Node**head , int X)
{
   Node*temp = *head ;
   Node *t = new Node;
   //if list is empty
   if(*head==NULL)
   {
       *head = new Node;
       (*head)->data = X;
       (*head)->next = NULL;
   }
  
   else
   {
      
       if(X < temp->data) //start node
       {
           t = new Node;
           t->data = X;
           t->next = *head;
           *head = t;
       }
          
       else
       {
           while(temp->next != NULL and !(X < temp->next->data && X >= temp->data)) //as it is sorted so X must lie between the consecutive values or else at end
               temp=temp->next;
          
           if(temp->next == NULL) //X will go to end
           {
               temp->next = new Node;
               temp = temp->next;
               temp->data = X;
               temp->next = NULL;
           }
           else //X is inserted in between some nodes in list
           {
               t = new Node;
               t->data = X;
               t->next = temp->next; //make the new node's next as the next of current node because the 't' node will lie between consecutive nodes
               temp->next = t;
           }
       }
   }
}
  
void append(Node** head_ref, int new_data)
{
Node* new_node = new Node();
  
Node *last = *head_ref;
  
new_node->data = new_data;
  
new_node->next = NULL;
  
if (*head_ref == NULL)
{
*head_ref = new_node;
return;
}
  
while (last->next != NULL)
last = last->next;
  
last->next = new_node;
return;
}
  
void printList(Node *node)
{
while (node != NULL)
{
cout<<" "<<node->data;
node = node->next;
}
}
  
int main()
{
Node* head = NULL;

push(&head, 12);
push(&head, 54);
push(&head, 13);
push(&head, 12);
push(&head, 32);
push(&head, 26);
push(&head, 12);
push(&head, 8);
push(&head, 87);
push(&head, 34);
push(&head, 9);
push(&head, 63);
push(&head, 15);
push(&head, 76);
push(&head, 56);
push(&head, 10);
cout<<"The list :"<<endl;
printList(head);
  
append(&head, 26);
cout<<endl<<"The list after apending : "<<endl;
printList(head);
  
deletelist(&head);
  
cout<<endl<<"List is deleted "<<endl;
  
insert(&head, 12);
insert(&head, 54);
insert(&head, 13);
insert(&head, 12);
insert(&head, 32);
insert(&head, 26);
insert(&head, 12);
insert(&head, 8);
insert(&head, 87);
insert(&head, 34);
insert(&head, 9);
insert(&head, 63);
insert(&head, 15);
insert(&head, 76);
insert(&head, 56);
insert(&head, 10);
  
cout<<endl<<"The list after inserting values : "<<endl;
printList(head);
  
return 0;
}

Output:-

Execute Result... CPU Time: 0.ee sec(s), Memory: 3288 kilobyte (s) The list 10 56 76 15 63 9 34 87 8 12 26 32 12 13 54 12 The list after apending: 10 56 76 15 63 9 34 87 8 12 26 32 12 13 54 12 26 List is deleted The list after inserting values : 8 9 10 12 12 12 13 15 26 32 34 54 56 63 76 87