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:

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.

   program8708
Program: OrderedList interface.

The OrderedList interface adds the following operations:

this[int]
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 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.

   program8730
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:

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