←back to thread

178 points todsacerdoti | 1 comments | | HN request time: 0.211s | source
Show context
jokoon ◴[] No.26340841[source]
Thanks for the article, there should be a huge list of those type of classic C++ misconceptions/FAQ style.

One of my favorite is "you don't need a linked list".

Although I'm still genuinely interested when a linked list is best suited. I'm also curious why they were invented and why they're taught, maybe just for teaching purposes...

replies(12): >>26340881 #>>26340918 #>>26340936 #>>26341086 #>>26341090 #>>26341157 #>>26341167 #>>26341203 #>>26341240 #>>26341290 #>>26341787 #>>26347246 #
creata ◴[] No.26341157[source]
Linked lists are pretty nice.

* Lazy linked lists are the same thing as iterators, a fact which is used pervasively in Haskell.

* Intrusive or otherwise inline linked lists like are used everywhere, e.g. the DOM has a doubly linked list of children for each node, simple memory pools are often implemented as free lists, and tons of resources inside kernels are members of many linked lists.

* Linked lists are guaranteed O(1) append, but dynamic arrays are only amortized O(1) append. Intrusive linked lists also never need to allocate. That makes them useful inside resource-constrained places.

replies(1): >>26341229 #
1. jpcooper ◴[] No.26341229[source]
Agreed on linked lists in Haskell if you’re doing forward iteration. You can have lazy byte strings under the bonnet while providing a ‘pure’ linked list interface. No worries about explicit iteration.