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.
[ Parent
| on HN ]
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.
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.
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
}