Question

C++

What Should This Program Do?

Linked List Class

• Design your own linked list class (List.h) to hold a series of strings.
• The linked list node should be implemented as a struct.
• The class should have member functions for appending, inserting, and deleting nodes.
• You should also have a display function that will traverse the list & display each node’s value.
• Don’t forget to add a destructor that destroys the list.

DRIVER – driver.cpp

Write a driver program (driver.cpp) that will do the following:

1. Create a linked list object
2. Call the linked list’s append function to append the following strings to your linked list. Afterwards, print to the screen to tell the user that you are inserting several strings to the list.
   1. “boogeyman”
   2. “ghost”
   3. “scarecrow”
   4. “witch”
   5. “zombie”
3. Now call the linked list’s display function to print the list.
4. Now call the linked list’s insert function to insert the “vampire” string in the correct sorted position. Print to the screen to tell the user that you are inserting “vampire” in to the list.
5. Now call the linked list’s display function again to print the list.
6. Now call the delete function to delete “ghost” from the list. Print to the screen to tell the user that you are deleting “ghost” from the list.
7. Last, call the linked list’s display function again to print the list.

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

Sample Output

The linked list has been created.

I am appending several strings to the list.

boogeyman

ghost

scarecrow

witch

zombie

I am inserting vampire in the list.

boogeyman

ghost

scarecrow

vampire

witch

zombie

I am deleting ghost from the list.

boogeyman

scarecrow

vampire

witch

zombie

All list nodes have been removed.

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

What to Turn In

• List.h
• driver.cpp

Answer 1

Okay I have coded it for you,

Heres the List.h

#ifndef LINKED_LIST
#define LINKED_LIST

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

struct ListNode {
        string data;
        ListNode* next;
};



void append(ListNode *head,string s);
void insert(ListNode *head,string s);
void deleteNode(ListNode *head, string s);
void display(ListNode* head);

#endif

And heres the Main.cpp

#include <iostream>
#include "List.h"
using namespace std;

//void List()

void append(ListNode *head,string s){
    
    ListNode *newNode=new ListNode;
    newNode->data=s;
    newNode->next=NULL;
    if(head==NULL){
        head=newNode;
        return;
    }
    ListNode *curr=head;
    while(curr){
        if(curr->next==NULL){
            curr->next=newNode;
            return;
        }
        curr=curr->next;
    }
}

void insert(ListNode *head,string s){
    cout<<"I am inserting "<<s<<" to the list"<<endl;
    ListNode *newNode=new ListNode;
    newNode->data=s;
    newNode->next=NULL;
    ListNode *curr=head;
    ListNode *prev=new ListNode;
    prev->data="";
    prev->next=NULL;
    while(!(prev->data<=s&&s<=curr->data)){
        prev=curr;
        curr=curr->next;
    }
    if(curr != NULL){
        newNode->next = curr;
    }
    if(prev != NULL){
        prev->next = newNode;
    }
    else{
        head = newNode;
    }
}

void deleteNode(ListNode *head, string s){
    cout<<"I am deleting "<<s<<" from the list"<<endl;
    ListNode *curr=head;
    ListNode *prev=NULL;
    while(curr){
        if(curr->data==s) break;
        prev=curr;
        curr=curr->next;
    }
    if(curr==head){
        head=curr->next;
        delete curr;
        return;
    }
    if(curr->next==NULL){
        prev->next=NULL;
        delete curr;
        return;
    }
    
    prev->next=curr->next;
    delete curr;
    return;
}
void display(ListNode* head){
    ListNode *curr=head;
    while(curr){
        cout<<curr->data<<" ";
        curr=curr->next;
    }
    cout<<endl;
}
int main(){
    ListNode *head=new ListNode();
    cout<<"The linked list has been created"<<endl;
    cout<<"I am appending several strings to the list"<<endl;
    append(head,"boogeyman");
    append(head,"ghost");
    append(head,"scarecrow");
    append(head,"witch");
    append(head,"zombie");
    display(head);
    insert(head,"vampire");
    display(head);
    deleteNode(head,"ghost");
    display(head);
    return 0;
}

Please reach out in the comments if you have any doubt