Instead of wasting more energy on improving the (overused) linked list, write a little resizable array library that doubles size on each fill-up. It's easy and

Instead of wasting more energy on improving the (overused) linked list, write a little resizable array library that doubles size on each fill-up. It's easy and much faster. Don't do this. Doubling the size of your allocation whenever you expand can easily lead to large amounts of wasted storage in common scenarios. "Yes," you may say. "But memory is cheap." Which it is at the small scale, but when you're allocating 1GB to store a 512MB array you have a problem. A vastly better approach is to use some form of adaptive rescaling which avoids excessive overcommits. Here, for example, is the code (and explanatory comment) Python uses to determine the new allocation size for an expanding list: /* This over-allocates proportional to the list size, making room * for additional growth. The over-allocation is mild, but is * enough to give linear-time amortized behavior over a long * sequence of appends() in the presence of a poorly-performing * system realloc(). * The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ... */ new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6) + newsize; if (newsize == 0) new_allocated = 0; Note that you will also want to avoid using the same calculation for expanding and contracting the allocation size, to avoid thrashing allocations when the list size varies around the pivot point. (i.e., add one element, triggering an expansion; remove the element, triggering a contraction; repeat.)