Objective: to maintain an ordered list implemented as a doubly linked list

Modify your earlier U.S. Capitals Lab to store cities in a doubly linked list. You will need to modify your node structure and add the prev field. Use a header node and a trailer node if you want.

     //U.S.Capitals Lab               //U.S.Cities Lab 
     struct node                      struct  node
     {                                {
          apstring data;                   apstring data;
          node * next;                      node * next, * prev;
     };                               };

a) It is possible with a doubly linked list to make a set of errors that may leave all the forward links in place but leave the backward links dangling. Write a function to check for this and add the corresponding command to your menu.

     void DislayListReverse( node * list)
     // Will traverse the list backward
     {

b) Write a function that matches a string of characters against a pattern containing MS-DOS wildcard characters:'?' and '*'. The wildcard character '?' matches any character in the corresponding position. '*' matches that character and all that follow. For example, the cities "Boston" and "Reston" both match the pattern "??ston" and the cities "New York", "New Haven", and "Newark" all match the pattern "New*".

     void MoveToTop(node* &list, apstring pattern)
     // will move all nodes that match a given pattern to the top (beginning) of the list.
     {

The function should perform the operation in one traversal of the list and should keep the moved nodes in the same order (so that if "New Haven" was above "New York" and both were moved to the top of the list, "New Haven" would remain above.)