A Better Data Storage Structure Motivation Arrays and lists are very useful data structures with their own advantages and disadvantages for data storage. However, neither are completely efficient for some common usage patterns.
Lists waste access time and memory to make updating easy.
Arrays provide excellent access time and compact storage while making random insertion and deletion hideously expensive. The spike in a process's working set during the copy can hurt performance and increase a process's internal memory fragmentation. Array allocation requires a large block of contiguous memory which may be expensive to acquire on garbage collection systems, or in a traditional heap-based model with large amounts of internal memory fragmentation. Lists waste one pointer's worth of memory per element. This overhead becomes more significant on 64bit OS's.