[voidlogic]

If really needed you can have it both ways, you could roll a data structure that is a linked list of arrays. Then you have constant time growth and good caching/prefetching.

Toy example:

  struct ListSegment {
    T[64] items
    int nextItem = 0
    ListSegment* nextSeg, prevSeg
  }

[Bill_Dimm]

If you're using C++ you don't need to roll your own because the standard library provides it. It is called deque.