O'Reilly logo
  • You Wang thinks this is interesting:

A specific solution for appending is to use what’s often called a dynamic array, or vector.4 The idea is to allocate an array that is too big and then to reallocate it in linear time whenever it overflows. It might seem that this makes the append just as bad as the insert. In both cases, we risk having to move a large number of elements. The main difference is that it happens less often with the append. In fact, if we can ensure that we always move to an array that is bigger than the last by a fixed percentage (say 20 percent or even 100 percent), the average cost, amortized over many appends, is constant.


Cover of Python Algorithms: Mastering Basic Algorithms in the Python Language, Second Edition


‘insert' moves all elements always. 'append' moves less frequently because of pre-allocation, which trades time with space.