next up previous
Next: Recursive sequence data Up: Comparison of Sequence Previous: Comparison of Sequence

Basic sequence data structures

The array method is just too slow for Inserts and Deletes. In addition its paging behavior is very bad (it touches lots of pages). It might be useful for a one line text editor or a text editor where few edits are expected.

The linked list method takes far too much space for long sequences. It is useful for short in-memory sequences where the edits and ItemAts are not localized. The linked list method has one great advantage and that is that the items never move in memory. This makes it easy to embed a list sequence in another data structures (such as a tree to provide fast searching).

Of the basic sequence data structures, only the gap method can be seriously considered for a general purpose text editor. The gap method has one major problem and that is when the gap fills up. This will require lots of item movement to reestablish the gap.

REDO: be more positive about the gap method.

The lines of code measure was taken from the sample implementations.

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