Incidentally, if you're worried about the appends' reallocations throwing off your linear time, take a look at Objects/listobject.c : /* This over-allocate

Incidentally, if you're worried about the appends' reallocations throwing off your linear time, take a look at Objects/listobject.c : /* 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);