Arrays allow records to be stored contiguously and to be accessed randomly. With pointer arrays, random access is possible even for variable-length records. Lists are also data structures containing records. Lists provide the flexibility, when needed, to separate records?/FONT>enhancing the ability to insert or delete, but reducing the capability of accessing records at random. Stored records can be traversed using either the sequential array or list implementation. The time to carry out the traversal need not be significantly different for the two methods.
Suppose that instead of processing the records in sequential order, as in a traversal, your program must access the records in arbitrary order. (In an airplane reservation system, for example, seat reservations must be processed immediately, in random order.) Having to access the records in arbitrary order means that the program must access and process the records even though the programmer cannot predict the order in which this must be done. The sequential representation, because it allows selection for fixed-length records, allows this random accessing to be accomplished in constant time. The list representation requires that random accessing be done by traversing to the needed record, starting from the first and accessing each succeeding record until the desired one is reached. If the required record is the ith, traversal will take time proportional to i. Thus randomly accessing records takes constant time for each record accessed with the sequential implementation, but time proportional to the desired record number for the list representation. This can result in significantly greater processing time for the list implementation when you are randomly processing records.
To insert one record in the collection (say, after the ith record) when using the sequential implementation, all succeeding records (the (i + 1)th, (i + 2)th, . . . , nth) must be moved down in the data array. This operation will take time proportional to the number of succeeding records (n - 1). Adding a record as the new first record gives the worst-case time, which is proportional to n. Inserting a new record using the list implementation, again assuming you have determined where it is to be inserted, takes a constant time?/FONT>the time needed to change two pointers.
To delete one record, say the ith, using the sequential representation, requires that the succeeding i - 1 records be moved up. Thus the time required is proportional to i - 1. Using the list implementation requires a constant time for this deletion?/FONT>the time needed to change one pointer. The time for deletion with a sequential implementation in the worst case is also proportional to n. It is obvious that insertion and deletion of one record can result in much greater execution time for the sequential implementation as compared to the list implementation.
The contrast is especially striking when record accesses, insertions, or deletions are performed on m records. The worst-case time to randomly access an entire collection of m records becomes proportional to m and m2, for the sequential and list implementations, respectively. For random insertions and deletions, these are reversed in favor of lists. This means that if m is doubled or tripled, the respective times increase fourfold or ninefold instead of merely doubling or tripling.
When selecting an implementation, the basic considerations are comparative execution times and relative frequencies for random access, insertion, or deletion.
The list implementation will require at least as much memory as the sequential implementation. For instance, if each record requires one element for the information field, and the list implementation requires another element for the link field, then lists would require twice as much storage. It is possible that part of the storage used to implement a record would be left unused in any case, so that using it for the link field requires no extra storage.