Question

C++ Compsci 165: For your twelfth programming assignment you will be implementing a program that uses a linked list.You will be implementing the following structure and functions:

struct LinkedList

{

int value;

LinkedList *next;

};

Note that with a singly linked list, you need to maintain a head pointer (pointer to the beginning of the list). Typically a tail pointer (pointer to the end of the list) is not maintained in a singly linked list (because you can only iterate from the beginning to the end), although it can be.

append_node: appends a new node (created using the new statement) to the end of the linked list

insert_node: inserts a new node(created using the new statement)at the specified location in the list

delete_node: deletes a node from the specified location in the list

search_node: searches the list for a value

destroy_list: At the end of the program, this function loops through the entire list and destroys the list by using the delete statement on each dynamically allocated linked list node (to avoid a memory leak).

Answer 1

#include<bits/stdc++.h>
using namespace std;

struct Node
{
   int value;
   Node *next;
};

Node* append_node(struct Node *head, int new_data)
{
  
   Node *nn = new Node();
   nn->value = new_data;
   nn->next = NULL;
   if(head==NULL) //if it is the first node, then head becomes newnode...
   {
       head = nn;
   }
   else //otherwise traverse till last and add this newnode...
   {
       Node *temp = head;
       while(temp->next != NULL)
       {
           temp = temp->next;
       }
       temp->next = nn;
   }
   return head;
}

void insert_node(struct Node *head, int new_data, int position)
{
   Node *nn = new Node;
   nn->value = new_data;
   nn->next = NULL;
  
   Node *temp = head;
  
   if(position == 1) //if it is in starting, then link with head and make this as new head....
   {
       nn->next=temp;
       head=nn;
   }
   else //otherwise loop till position, then insert...
   {
       for(int i=1;i<position-1;i++)
       {
           temp = temp->next;
       }
      
       nn->next=temp->next;
       temp->next=nn;
   }
}

void delete_node(struct Node *head, int position)
{
   Node *temp = head;
  
   if(position == 1) //change head to next node, and free the old head...
   {
       head=temp->next;
       free(temp);
   }
   else //otherwise traverse till position...
   {
       for(int i=1;i<position-1;i++)
       {
           temp = temp->next;
       }
      
       Node *next = temp->next->next; //storing the next node of deleting node in *next...

   free(temp->next); // deleting current node...
  
   temp->next = next; // attaching next to the previous node...
   }  
  
}

void search_node(Node *head, int data)
{
   //cout<<"hai";
   Node *temp=head;
   int i = 1, flag = 0;
  
   while(temp != NULL)
   {
       if(temp->value == data)
       {
           cout<<"Found at position "<<i<<endl;
           flag = 1;
           break;
       }
       i++;
       temp=temp->next;
   }
   if(flag==0)
   cout<<"Not Found"<<endl;
}

void destroy_list(Node* head)
{
while(head != NULL)
{
Node *temp = head;
head = temp->next;
delete temp;
}
cout<<"Destroyed Successfully\n";
}
void printList(struct Node* head)
{
while (head != NULL) {
cout << " " << head->value;
head = head->next;
}
cout << endl;
}

int main()
{
   struct Node* head = NULL;
  
   //appending nodes....
   head=append_node(head, 7);
head=append_node(head, 1);
head=append_node(head, 3);
head=append_node(head, 2);
head=append_node(head, 8);
  
printList(head); //printing List after appending...
  

insert_node(head,9,2); //inserting node at second position...
printList(head); //print..
  
  
insert_node(head,97,4); //inserting node at fourth position...
printList(head); //print..
  
  
delete_node(head,5); //deleting node at fifth position...
printList(head); //print..
  
  
search_node(head,3); //searching node with value 3...
  
  
search_node(head,97); //searching node with value 97...
  
destroy_list(head); //Destroying list...
  
printList(head); // prints random numbers Because list is already destroyed....
}

---------------------------------------------------------------------------------------------------------------------

Output: 7 1 3 28 791328 9 1 97 3 2 8 7 9 1 97 2 8 Not Found Found at position 4 Destroyed Successfully 34471600 34471536 34475808 34471568 34475840 34471632

----------------------------------------------------------------------------------------------------------------------