Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

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 gif defines the OrderedList interface. The OrderedList interface extends the SearchableContainer interface defined in Program gif. Recall that a searchable container is a container that supports the following additional operations:

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

Program: OrderedList interface.

The OrderedList interface adds the following operations:

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

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

Program: Cursor interface.

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

used to access the object in the ordered list at the current cursor position;
used to insert an object into the ordered list after the current cursor position;
used to insert an object into the ordered list before the current cursor position; and
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 gif presents an array version of ordered lists; Section gif, an implementation using on the LinkedList class.

next up previous contents index

Bruno Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.