News for hackers. Stuff that matters.
Re:Stop Using Linked Lists by justin_hancock on Wednesday May 22, 2013 @12:55PM (#5752126)
They're useful where you need to grow a collection in constant time. Re-sizing arrays is potentially very expensive.
Re:Stop Using Linked Lists by Bill_Dimm on Wednesday May 22, 2013 @01:11PM (#5752256)
You might want to take a look at the graph (scroll down a little) in this article that is linked in the blog post:

http://kjellkod.wordpress.com/2012/02/25/why-you-should-neve...

It's not just growing the collection (it does read and insert), but it may be a bit surprising.

Re:Stop Using Linked Lists by alayne on Wednesday May 22, 2013 @01:08PM (#5752241)
That's why you use a growth factor, say doubling the backing array when you need to grow. That makes the amortized cost of adding an item constant.

The only case where a LL may be preferable are when you care about performance of inserting/deleting in the middle of a list.

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.