3 ms·
They're useful where you need to grow a collection in constant time. Re-sizing arrays is potentially very expensive.
by justin_hancock 13y ago
They're useful where you need to grow a collection in constant time. Re-sizing arrays is potentially very expensive.
- alayne 13y agoThat'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.
- Bill_Dimm 13y agoYou 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-never-ever-ever-use-linked-list-in-your-code-again/#TOC_LOCALITY_OF_REF_1 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.
- voidlogic 13y agoIf 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 13y agoIf you're using C++ you don't need to roll your own because the standard library provides it. It is called deque.