News for hackers. Stuff that matters.
Re:Stop Using Linked Lists by voidlogic on Wednesday May 22, 2013 @01:13PM (#5752275)
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
  }
Re:Stop Using Linked Lists by Bill_Dimm on Wednesday May 22, 2013 @01:42PM (#5752458)
If you're using C++ you don't need to roll your own because the standard library provides it. It is called deque.