|
|
|
|
|
|
|
5. Insert or delete the nth component in a list. |
|
|
|
|
|
|
|
|
6. Access the nth component in a list. |
|
|
|
|
|
|
|
|
7. Sort the components in a list. |
|
|
|
|
|
|
|
|
8. Search the list for a specific component. |
|
|
|
|
|
|
|
|
Reading components into a list is faster with an array representation than with a dynamic linked list because the new operation doesn't have to be executed for each component. Accessing the components in sequence takes approximately the same time with both structures. |
|
|
|
|
|
|
|
|
Inserting or deleting the first component is much faster using a linked representation. Remember that with an array, all the other list items have to be shifted down (for an insertion) or up (for a deletion). Conversely, inserting or deleting the last component is much more efficient with an array; there is direct access to the last component, and no shifting is required. In a linked representation, the entire list must be searched to find the last component. |
|
|
|
|
|
|
|
|
On average, the time spent inserting or deleting the nth component is about equal for the two types of lists. A linked representation would be better for small values of n, and an array representation would be better for values of n near the end of the list. |
|
|
|
|
|
|
|
|
Accessing the nth element is much faster in an array representation. We can access it directly by using n - 1 as the index into the array. In a linked representation, we have to access the first n- 1 components sequentially to reach the nth one. |
|
|
|
|
|
|
|
|
For many sorting algorithms, including the selection sort, the two representations are approximately equal in efficiency. However, there are some sophisticated, very fast sorting algorithms that rely on direct access to array elements by using array indices. These algorithms are not suitable for a linked representation, which requires sequential access to the components. |
|
|
|
|
|
|
|
|
In general, searching an ordered list for a specific component is much faster in an array representation because a binary search can be used. When the components in the list to be searched are not ordered, the two representations are about the same. |
|
|
|
|
|
|
|
|
When you are trying to decide whether to use an array representation or a linked representation, determine which of these common operations are likely to be applied most frequently. Use your analysis to determine which structure would be better in the context of your particular problem. |
|
|
|
|
|
|
|
|
There is one additional point to consider when deciding whether to use an array or a dynamic linked list. How accurately can you predict the maximum number of components in the list? Does the number of components in the list fluctuate widely? If you know the maximum and it remains fairly constant, an array representation is fine in terms of memory usage. Otherwise, it is better to choose a dynamic linked representation, in order to use memory more efficiently. |
|
|
|
|
|