CPE 202 Doubly Linked Ordered List

This lab provides an introduction to doubly-linked lists. In particular, you are asked to implement a circular doubly- linked list where the elements are in order.

1 Doubly Linked Ordered List

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 circular doubly linked list. That is to say the "first" item in the list will be the smallest and the last item in the list will be the largest.

Your implementation should use a single dummy node as the "head" as seen in class.

• insert This function takes an ordered list and a value as arguments and inserts the value into the proper location in the list. This function must have O(n) performance in the worst case.
• remove This function takes an ordered list and a value as arguments and removes the value from the list. If the value is not in the list, then this function should raise a ValueError. This function must have O(n) performance in the worst case.
• contains This function takes an ordered list and a value as arguments and returns whether or not the value is in the list (True if it is, False otherwise). This function must have O(n) performance in the worst case.
• index This function takes an ordered list and a value as arguments and returns the index of the first occurrence of the value in the list. If the value is not in the list, then this function should raise a ValueError. This function must have O(n) performance in the worst case.
• get This function takes an ordered list and an index as arguments and returns the value at the given index. If the index is outside the bounds of the list, then this function should raise an IndexError. This function must have O(n) performance in the worst case.
• pop This function takes an ordered list and an index as arguments and removes (and returns) the value at the given index. If the index is outside the bounds of the list, then this function should raise an IndexError. This function must have O(n) performance in the worst case.
• is_empty This function takes an ordered list as an argument and returns whether or not the list is empty (True if it is, False otherwise). This function must have O(1) performance in the worst case.
• size This function takes an ordered list as an argument and returns the number of items in the list. This function must have O(1) performance in the worst case.

Note that you can (and should) assume that all items added to your list are comparable with the < operator and can be compared for equality with ==. You cannot make any other assumptions about the items in your list.