Part 1.  Design and implement a class Menu which uses doubly linked lists as main data structures. A menu consists of main menu items, organized as a doubly linked list, each main menu item having associated a submenu, organized as a doubly linked list of submenu items (see the example of a Menu object in the attached file).
The class Menu should define a default constructor which builds an empty menu and the following methods: – addMainMenuItem, two overloaded methods for adding a main menu item having an empty submenu. One of the overloaded methods takes only one parameter, the name of the new main menu item. It adds the new main menu item to the end of the list. The other overloaded method takes three parameters: the name of the new main menu item, the name of an existing main menu item and a parameter which specifies whether the new main menu item will be added before or after the existing main menu item. – deleteMainMenuItem, deletes the main menu item specified by name; – addSubMenuItem, adds a submenu item specified by name to a main menu item specified by name; – toString, traverses the linked lists data structures and generates the string representation of a menu object, organized on lines. Each line should include the main menu item followed by its submenu items. The items should be separated by a semicolon character. The toString method will be invoked from other programs (such as the driver of Part 2) to display the menu.
Note. If necessary, additionally (housekeeping) methods may be defined for the class Menu. You are required to compile (without errors) the class Menu.java.
 
Part 2 Write a driver program MenuTest.java to test the Menu class.  In the driver program, do the following tasks: 
a) Read menu items from the input file Menu.txt and build a menu object which includes the specified items. Each file line contains a main menu item followed by its submenu items, all items being separated by the semicolon character. After reading the file and…