Data Structures and Algorithms with Object-Oriented Design Patterns in Python

Ordered Lists

An ordered list is a list in which the order of the items is significant. However, the items in an ordered lists are not necessarily sorted. Consequently, it is possible to change the order of items and still have a valid ordered list.

Program defines the OrderedList class. The abstract OrderedList class extends the abstract Container class defined in Program . Recall that a searchable container is a container that supports the following additional operations:

insert: used to put objects into a the container;
withdraw: used to remove objects from the container;
find: used to locate objects in the container;
__contains__: used to test whether a given object instance is in the container.

The abstract OrderedList class adds the following operations:

__getitem__: used to access the object at a given position in the ordered list, and
findPosition: used to find the position of an object in the ordered list.

program8580
Program: Abstract OrderedList class.

In addition to self, the findPosition method of the abstract List class takes an object, obj, and searches the list for an object that matches the given one. The return value is an instance of a class derived from the Cursor class. Program defines the abstract Cursor class.

program8598
Program: Abstract Cursor class.

A cursor ``remembers'' the position of an item in a list. The abstract Program class given in Program defines the following operations:

datum: used to access the object in the ordered list at the current cursor position;
insertAfter: used to insert an object into the ordered list after the current cursor position;
insertBefore: used to insert an object into the ordered list before the current cursor position; and
withdraw: used to remove from the ordered list the object at the current cursor position.

As we did in the previous chapter with stacks, queues, and deques, we will examine two ordered list implementations--an array-based one and a linked-list one. Section presents an implementation using the Array class; Section , an implementation using on the LinkedList class.