4) (40 pts) This programming problem deals creating a doubly-linked list of strings that can search for an item within the list from the front to back or vice-versa.

Your programming task for this assignment is to create a doubly-linked list sorted list (DLSList) that meets the following criteria:

i. The list items must be C++ strings rather than ints. For full credit you cannot use char[] arrays, and you must use compare for all string comparisons (rather than the standard relational operators like ==, <, etc.)

ii. The nodes of the list must be doubly-linked (i.e. pointers should exist to both next and previous nodes (with the previous node for the starting element simply pointing to NULL). In addition to ListStart, your list must have a ListEnd pointer, that always points to the final node in the list.

iii. It must have all operations common to LLSList. When searching for an item using the GetItem operation, however, the operation must proceed from front to back if the first character is between A and M, and back to front if the first character is between N and Z. (You can assume every string is capitalized.) Lastly, the GetItem call must indicate through simple output (e.g. cout) whether the search is being performed from front-to-back or back-to-front.

You must package your code within the included main.cpp file, and it is highly suggested you check to verify your code compiles and works correctly with the file.

main.cpp

#include  #include "DLSList.h" int main(int argc, char** argv) { DLSList TestList; std::cout<<"Newly Created List: "; TestList.PrintList(); TestList.PutItem("Robinson"); TestList.PutItem("Smith"); TestList.PutItem("Ananthakrishnan"); TestList.PutItem("Contreras"); TestList.PutItem("Bailey"); TestList.PutItem("Paddington"); TestList.PutItem("Sampson"); std::cout<<"List after 'PutItem' calls: "; TestList.PrintList(); std::cout<<"Length after 'PutItem' calls: " <