Question

Modify the linked list code from class to work with strings. Insert the following food items into the list and display the list. The items are: bread, noodles, milk, bananas, eggs. Insert them in that order. Display the list. Then delete milk and redisplay the list. Then insert ice cream and redisplay the list. Then append zucchini and redisplay the list.

c++

Answer 1

#include <iostream>
#include <string>
using namespace std;
 
// A linked list node
struct Node
{
   string data;
   struct Node *next;
};

//insert a new node in front of the list
void push(struct Node** head, string node_data)
{
   /* 1. create and allocate node */
   struct Node* newNode = new Node;
 
   /* 2. assign data to node */
   newNode->data = node_data;
 
   /* 3. set next of new node as head */
   newNode->next = (*head);
 
   /* 4. move the head to point to the new node */
   (*head) = newNode;
}

/* insert new node at the end of the linked list */
void append(struct Node** head, string node_data)
{
/* 1. create and allocate node */
struct Node* newNode = new Node;
 
struct Node *last = *head; /* used in step 5*/
 
/* 2. assign data to the node */
newNode->data = node_data;
 
/* 3. set next pointer of new node to null as its the last node*/
newNode->next = NULL;
 
/* 4. if list is empty, new node becomes first node */
if (*head == NULL)
{
*head = newNode;
return;
}
 
/* 5. Else traverse till the last node */
while (last->next != NULL)
last = last->next;
 
/* 6. Change the next of last node */
last->next = newNode;
return;
}
 
// display linked list contents
void displayList(struct Node *node)
{
   //traverse the list to display each node
   while (node != NULL)
   {
      cout<<node->data<<"-->";
      node = node->next;
   }
 
if(node== NULL)
cout<<"null"; 
} 

// delete node from linked list
void deleteNode(struct Node **head, string key)
{
    // Store head node
    struct Node* temp = *head, *prev;
 
    // If head node itself holds the key to be deleted
    if (temp != NULL && temp->data == key)
    {
        *head = temp->next;   // Changed head
        free(temp);               // free old head
        return;
    }
 
    // Search for the key to be deleted, keep track of the
    // previous node as we need to change 'prev->next'
    while (temp != NULL && temp->data != key)
    {
        prev = temp;
        temp = temp->next;
    }
 
    // If key was not present in linked list
    if (temp == NULL) return;
 
    // Unlink the node from linked list
    prev->next = temp->next;
 
    free(temp);  // Free memory
}
/* main program for linked list*/
int main() 
{ 
/* empty list */
struct Node* head = NULL; 
 
// insert bread, noodles, milk, bananas, eggs
push(&head, "bread"); 
push(&head, "noodles");  
push(&head, "milk");  
push(&head, "bananas");  
push(&head, "eggs");

cout<<"After inserting foods in linked list: "<<endl;
displayList(head);

//delete milk
deleteNode(&head,"milk");

cout<<"\n\nAfter deleting milk from linked list: "<<endl;
displayList(head);

//insert ice cream
push(&head, "ice cream");

cout<<"\n\nAfter inserting ice cream in linked list: "<<endl;
displayList(head);

//append zucchini
append(&head, "zucchini"); 

cout<<"\n\nAfter appending zucchini in linked list: "<<endl;
displayList(head);
 
return 0;
}

OUTPUT :

*******************PLEASE UPVOTE********************************