I need help with my assignment. Here is the prompt:

The structure of an ordered list is a collection of items where each item holds a relative position that is based upon some underlying characteristic of the item. The ordering is typically either ascending or descending, and we assume that list items have a meaningful comparison operation that is already defined. Many of the ordered list operations are the same as those of the unordered list.

Implement the following operations for an ordered list of items ordered in ascending order using a doubly linked list. Let the head of the list be where the smallest items are and let the tail be where the largest items are. To keep track of the head and tail of the list, use a single dummy node as shown in class. You will also need to write thorough test cases for each function.

You may use iterative code for many of the methods, but you must implement the following methods using recursion:

size()

search()

python_list_reversed()

For these methods, you should use a helper method that will do the recursion

Notes:

You may assume that all items added to your list can be compared using the > operator, and can be compared for equality/inequality. Make no other assumptions about the items in your list.

If an attempt to add a duplicate item to the list, do not add the item.

Here is the code we have to edit:

class Node: '''Node for use with doubly-linked list''' def __init__(self, item): self.item = item self.next = None self.prev = None class OrderedList: '''A doubly-linked ordered list of items, from lowest (head of list) to highest (tail of list)''' def __init__(self): '''Use ONE dummy node ***No other attributes*** Do not have an attribute to keep track of size''' def is_empty(self): '''Returns back True if OrderedList is empty MUST have O(1) performance''' pass def add(self, item): '''Adds an item to OrderedList, in the proper location based on ordering of items from lowest (at head of list) to highest (at tail of list) If the item is already in the list, do not add it again MUST have O(n) average-case performance''' pass def remove(self, item): '''Removes an item from OrderedList. If item is removed (was in the list) returns True If item was not removed (was not in the list) returns False MUST have O(n) average-case performance''' pass def index(self, item): '''Returns index of an item in OrderedList (assuming head of list is index 0). If item is not in list, return None MUST have O(n) average-case performance''' pass def pop(self, index): '''Removes and returns item at index (assuming head of list is index 0). If index is negative or >= size of list, raises IndexError MUST have O(n) average-case performance''' pass def search(self, item): '''Searches OrderedList for item, returns True if item is in list, False otherwise" To practice recursion, this method must call a RECURSIVE method that will search the list MUST have O(n) average-case performance''' pass def python_list(self): '''Return a Python list representation of OrderedList, from head to tail For example, list with integers 1, 2, and 3 would return [1, 2, 3] MUST have O(n) performance''' pass def python_list_reversed(self): '''Return a Python list representation of OrderedList, from tail to head, using recursion For example, list with integers 1, 2, and 3 would return [3, 2, 1] To practice recursion, this method must call a RECURSIVE method that will return a reversed list MUST have O(n) performance''' pass def size(self): '''Returns number of items in the OrderedList To practice recursion, this method must call a RECURSIVE method that will count and return the number of items in the list MUST have O(n) performance'''

pass

Thank you for any and all help!