## Description

This lab provides an introduction to doubly-linked lists. In particular, you are asked to implement a circular doublylinked 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.

CPE 202 Lab 4, Page 2 of 2

## 2 Testing

As mentioned in the syllabus, your code is periodically graded prior to the deadline and you will receive automated

feedback based on the results of my tests. But, in order to receive any feedback, your tests much provide 100% test

coverage of the code you are submitting.

If you do not have 100% coverage, this is the only feedback you will receive.

100% test coverage means that every line of your code is run at some point in some test. Imagine if that weren’t the

case. That means that you have a line of code (or multiple lines of code) that could do anything, and you’d never

know. You never tested them!

Your tests will go in files named ordered_list_tests.py.

## 3 GitHub Submission

Push your finished code back to GitHub. Refer to Lab 0, as needed, to remember how to push your local code.