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

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 interface. The OrderedList interface extends the SearchableContainer interface 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;
isMember: used to test whether a given object instance is in the container.

program8638
Program: OrderedList interface.

The OrderedList interface adds the following methods:

get: 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.

The findPosition method of the the List interface takes a Comparable object and searches the list for an object that matches the given one. The return value is a Cursor. Program defines the Cursor interface.

program8660
Program: Cursor interface.

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

getDatum: 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 array version of ordered lists; Section , an implementation using on the LinkedList class.