next up previous
Next: Recursive Sequence Data Up: Basic Sequence Data Previous: The gap method

The linked list method

At the other extreme is the linked list method which has a span for each item in the sequence and the span is kept in the descriptor. This requires a large (and file content dependent) number of descriptors which must be sequenced. If we link the descriptors together into a linked list then we really only have to remember one descriptor, the head of the list. (See Figure 4)

Figure 4: The linked list method  

Inserts and Deletes are fast and easy (just move some pointers) but ItemAt is more expensive than the array or gap methods since several pointers may have to be followed.

The linked list method uses a lot of extra space and so is not appropriate for a large sequence but is frequently used as a way of implementing a sequence of descriptors required in the more complex sequence data structures. In fact, it is the most common method for that.

One could think of the array method as a special case of the linked list method. An array is really a linked list with the links implicit, that is, the link is computed to be the next physically sequential address after the current item. In this view, the linked list method the only primitive sequence data type. The array method is a special case if linked list method and the gap method is a variation on the array method.

Charlie Crowley
Thu Jun 27 15:36:10 MDT 1996