Program Plan: Defines a class IndexedList which has following data members and member functions. node *head = NULL; map<char, node&*gt;list_index; member functions node* getNewNode (string); void searchIndexedList (string); void insertInIndexedList (string); void deleteFromIndexedList (string); void createIndex (); void displayList (); A map is defined to keep a map of starting alphabet of names and their node address. Define main to use the above function of a linked list. Program Description: The main objective of this program is to improve search and deletion for a node from the linked list. In this implementation, we will keep starting point of search from the node which is available in the previously created map. With this approach, the search will improve to great extent. Program: #include<iostream> #include<map> usingnamespace std; /* structure of a single linked list node*/ typedefstructlist_node{ string studentName; structlist_node*next;// pointer to next node in the list }node; classIndexedList{ node *head =NULL; map<char, node&*gt;list_index; public: node*getNewNode(string); voidsearchIndexedList(string); voidinsertInIndexedList(string); voiddeleteFromIndexedList(string); voidcreateIndex(); voiddisplayList(); IndexedList() { head =NULL; } }; /* create new node */ node*IndexedList::getNewNode(string name){ node *new_node=new node; new_node->studentName= name; new_node->next =NULL; returnnew_node; } /* displays the list elements */ voidIndexedList::displayList(){ cout<<"Displaying List : "; node *new_node=new node; new_node=this->head; while(new_node!=NULL){ cout<<new_node->studentName<<" -> "; new_node=new_node->next; } cout<<"NULL "<<endl; } /* Search the node with the element as data Return the pointer to the node if found else return NULL */ voidIndexedList::searchIndexedList(string name){ node *new_node=new node; if(this->list_index.find(name.at(0))!=this->list_index.end()){ new_node=this->list_index.at(name.at(0)); if(new_node!=NULL) { while(new_node!=NULL){ if(new_node->studentName== name) { cout<<"Name found in list"; break; } else { new_node=new_node->next; } } }else{ cout<<"List is empty"; } } else{ cout<<"Name NOT found in list"; } if(new_node==NULL){ cout<<"Name NOT found in list"; } } voidIndexedList::createIndex(){ cout<<"Creating Index : "; node *new_node=new node; new_node=this->head; while(new_node!=NULL){ cout<<new_node->studentName<<" -> "; cout<<new_node->studentName.at(0)<<endl; if(this->list_index.find(new_node->studentName.at(0))==this->list_index.end()){ this->list_index.insert(pair<char,node&*gt;(new_node->studentName.at(0),new_node)); } new_node=new_node->next; } cout<<"Print Index"<<endl; for(auto it =this->list_index.cbegin(); it !=this->list_index.cend();++it) { cout<< it->first <<" "<< it->second <<"\n"; } } voidIndexedList::deleteFromIndexedList(string name){ node *new_node=new node; node *temp_node=new node; if(this->list_index.find(name.at(0))!=this->list_index.end()){ new_node=this->list_index.at(name.at(0)); temp_node=new_node; if(new_node!=NULL) { while(new_node!=NULL){ if(new_node->studentName== name) { cout<<"Name found in list"; temp_node->next =new_node->next; deletenew_node; break; } else { temp_node=new_node; new_node=new_node->next; } } }else{ cout<<"List is empty"; } }else{ cout<<"Name NOT found in list"; } } /* insert a node at the end of the list */ voidIndexedList::insertInIndexedList(string name){ node *ptr=getNewNode(name); if(this->head ==NULL){//if list is empty this->head =ptr; } else{ node *temp =this->head; while(temp->next !=NULL){// move to the last node temp = temp->next; } temp->next =ptr;// insert node at the end } } intmain(){ string name; IndexedList list; int choice =0; while(1) { cout<<"-----------------"<<endl; cout<<"Operations on Linked List"<<endl; cout<<"-----------------"<<endl; cout<<"1.Insert Element to Indexed List "<<endl; cout<<"2.Remove Element from Indexed List "<<endl; cout<<"3.Search List"<<endl; cout<<"4.Display List"<<endl; cout<<"5.Display Index"<<endl; cout<<"6.Quit"<<endl; cout<<"Enter your choice : "; cin>>choice; switch(choice) { case1: cout<<" Enter Name to insert to Linked List >> "; cin>> name; list.insertInIndexedList(name);// 9 -> 4 -> 12 -> 3 -> 11 -> 6 break; case2: cout<<" Enter Name to be removed from Linked List >> "; cin>> name; list.deleteFromIndexedList(name);// 9 -> 4 -> 12 -> 3 -> 11 -> 6 break; case3: cout<<" Enter Name to search in Linked List >> "; cin>> name; list.searchIndexedList(name); break; case4: list.displayList(); break; case5: list.createIndex(); break; case6: return1; default: cout<<"Wrong choice"<<endl; } } return0; } Sample Output: ----------------- Operations on Linked List ----------------- 1. Insert Element to Indexed List 2. Remove Element from Indexed List 3. Search List 4. Display List 5. Display Index 6. Quit Enter your choice: 1 Enter Name to insert to Linked List >>california ----------------- Operations on Linked List ----------------- 1. Insert Element to Indexed List 2. Remove Element from Indexed List 3. Search List 4. Display List 5. Display Index 6. Quit Enter your choice: 1 Enter Name to insert to Linked List >>pittsburgh ----------------- Operations on Linked List ----------------- 1. Insert Element to Indexed List 2. Remove Element from Indexed List 3. Search List 4. Display List 5. Display Index 6. Quit Enter your choice: 1 Enter Name to insert to Linked List >>newyork ----------------- Operations on Linked List ----------------- 1. Insert Element to Indexed List 2. Remove Element from Indexed List 3. Search List 4. Display List 5. Display Index 6. Quit Enter your choice: 1 Enter Name to insert to Linked List >>seattle ----------------- Operations on Linked List ----------------- 1.Insert Element to Indexed List 2.Remove Element from Indexed List 3.Search List 4.Display List 5.Display Index 6.Quit Enter your choice : 1 Enter Name to insert to Linked List >>microsoft ----------------- Operations on Linked List ----------------- 1.Insert Element to Indexed List 2.Remove Element from Indexed List 3.Search List 4.Display List 5.Display Index 6.Quit Enter your choice : 1 Enter Name to insert to Linked List >>samsung ----------------- Operations on Linked List ----------------- 1. Insert Element to Indexed List 2. Remove Element from Indexed List 3. Search List 4. Display List 5. Display Index 6. Quit Enter your choice: 4 Displaying List: california ->pittsburgh ->newyork ->seattle ->microsoft ->samsung -> NULL ----------------- Operations on Linked List ----------------- 1. Insert Element to Indexed List 2. Remove Element from Indexed List 3. Search List 4. Display List 5. Display Index 6. Quit Enter your choice: 3 Enter Name to search in Linked List >>newyork Name NOT found in list----------------- Operations on Linked List ----------------- 1. Insert Element to Indexed List 2. Remove Element from Indexed List 3. Search List 4. Display List 5. Display Index 6. Quit Enter your choice: 5 Creating Index: california -> c pittsburgh -> p newyork -> n seattle -> s microsoft -> m samsung -> s Print Index c 0x9f4440 m 0x9f4500 n 0x9f44a0 p 0x9f4470 s 0x9f44d0 ----------------- Operations on Linked List ----------------- 1. Insert Element to Indexed List 2. Remove Element from Indexed List 3. Search List 4. Display List 5. Display Index 6. Quit Enter your choice: 3 Enter Name to search in Linked List >>newyork Name found in list----------------- Operations on Linked List ----------------- 1. Insert Element to Indexed List 2. Remove Element from Indexed List 3. Search List 4. Display List 5. Display Index 6. Quit Enter your choice: 2 Enter Name to be removed from Linked List >>newyork Name found in list----------------- Operations on Linked List ----------------- 1. Insert Element to Indexed List 2. Remove Element from Indexed List 3. Search List 4. Display List 5. Display Index 6. Quit Enter your choice: 4 Displaying List: california ->pittsburgh -> ->seattle ->microsoft ->samsung -> NULL ----------------- Operations on Linked List ----------------- 1. Insert Element to Indexed List 2. Remove Element from Indexed List 3. Search List 4. Display List 5. Display Index 6. Quit Enter your choice:

C++ How to Program (Early Objects Version)

10th Edition

ISBN: 9780134448824

Author: Paul Deitel; Harvey M. Deitel

Publisher: Pearson Education (US)

See similar textbooks

Videos

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Chapter 19, Problem 19.27E

Chapter 20, Problem 20.5E

Students have asked these similar questions

Complete my C++ program: Instructions: You have to continue on implementing your Array List namely the following functions: Example ArrayList: [10, 30, 40, 50] void addAt(int num, int pos) This method will add the integer num to the posth position of the list. Performing addAt(20, 2) in the example list will add 20 at the 2nd position and the array will now look like this: [10, 20, 30, 40, 50] When the value of pos is greater than the size + 1 or less than one, output "Position value invalid" void removeAt(int pos) Removes the number in the posth position of the list. Performing removeAt(3) in the example list will remove the 3rd element of the list and the updated array will be: [10, 30, 50] When the value of pos is greater than the size or less than one, output "Position value invalid" void removeAll(int num) Removes all instances of num in the array list. In this array [10, 10, 20, 30, 10], performing removeAll(10) will remove all 10's and the list will look like this: [20,…

C++ PROGRAMMING (Linked list) complete the functions: You have to continue on implementing your Array List namely the following functions: Example ArrayList: [10, 30, 40, 50] void addAt(int num, int pos) This method will add the integer num to the posth position of the list. Performing addAt(20, 2) in the example list will add 20 at the 2nd position and the array will now look like this: [10, 20, 30, 40, 50] When the value of pos is greater than the size + 1 or less than one, output "Position value invalid" void removeAt(int pos) Removes the number in the posth position of the list. Performing removeAt(3) in the example list will remove the 3rd element of the list and the updated array will be: [10, 30, 50] When the value of pos is greater than the size or less than one, output "Position value invalid" My incomplete code: #include <cstdlib>#include <iostream>using namespace std; class ArrayList : public List { // : means "is-a" / extend int* array; int index;…

Python Language - Total Damage

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Solution Summary: The author explains the purpose of the program, which is to improve search and deletion for a node from the linked list.

Videos

Want to see the full answer?

Chapter 19 Solutions