CLRS 3e 1.1-3

1.1-3 Select a data structure that you have seen previously, and discuss its strengths and limitations.

Array Lists - Linear sequence of elements.

Advantages


• Search by index takes constant time.
• Search by value takes liner time or can be improved by using binary search for sorted arrays.
• Setting an element to new value with known index takes constant time, with unknown index takes linear time.
 
Disadvantages
• Insertion and deletion can take liner time in worst case.  It is not very friendly to change.  
• Mostly need continuous blocks of memory for storage which can be unwieldy for large lists.
• Size is fixed and although dynamic array can expand if more space is needed it takes linear time to double the size.