Deques and Doubly Linked Lists
Description:
For this programming assignment, you will implement a DEQUE whose size can grow as elements are inserted into the DEQUE. Specifically, you will implement a DEQUE with a doubly linked list. All of your functions should run in O(1).
Coding Portion (100 Points):
• Start with the template: Deque.h and fill in all of the member functions. Do NOT modify the definition of the functions of the DEQUE or put the declarations in a different file. We will be compiling the code you turn in with a set of tests and need your code to have the correct interface to compile the results. An example main.cpp that we will use to test the correctness of your data structure is provided.
• The implementation for the Node class has been provided.
• Be sure to test the correctness of your algorithms and implementations.
• When handling errors, please use an assert statement to indicate to the user what has gone wrong or throw an exception that indicates what has occurred. For example, if the user calls removeFirst(), assert that the Deque contains a node, or you can check if the Deque contains a node and throw an exception if it does not. The functions first, last, removeFirst, and removeLast should each throw exceptions under some circumstances.
• Your code will be graded based on whether or not it compiles, runs, produces the expected output, produces correct output, and your coding style (does the code follow proper indentation/style and comments).
Grading Rubric
1. Valid file name as per submission instructions: 1 point
2. Executable code: 5 points
3. Doubly Linked List: 20 points
4. Each Function in Deque.h: 50 points (5 points each)
5. Correct output for all operations: 8 points (1 point each)
6. Organized and Readable code: 4 points
7. All operations in O(1): 12 points (1.5 point for each)
