←back to thread

178 points todsacerdoti | 3 comments | | HN request time: 0.68s | 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 #
lelanthran ◴[] No.26341167[source]
> Although I'm still genuinely interested when a linked list is best suited.

I can think of a few use-cases where I've opted for linked-lists over resizable arrays:

1. When you have enough memory for the set of all elements you want to store but not enough contiguous memory for the set of all elements you want to store (i.e. You have the available memory, but it's all fragmented).

2. When you have multiple threads adding to/removing from the container, a linked list lets each thread (in theory) insert/remove nodes at the same time. For example, one thread can be adding to the head of a queue while another thread is removing from the tail of the same queue; they don't need to both wait for the same lock to resize the container.

3. When you have large insertions/removals. For example, concatenating two lists into one is just reassigning two/four pointers in linked lists. With arrays or similar you have to have enough free memory to make of a copy of the smaller list, at least).

   Another example is "zipping" two lists together - you simply go through the lists and reassign pointers. With arrays you have to allocate enough memory for the final list before copying elements over.

   Same goes for splitting lists into two: for example, applying a predicate function to remove and return all elements that satisfies the predicate takes no extra memory using lists, but with arrays will need the destination to be allocated first).
4. Finally, you may want to store cycles in your container (perhaps the traversal maintains state so you can use the cycle to make traversal of some nodes repeat, or maybe you're simply insane and like to confuse readers of your code :-).

Okay, fair enough, that last one is me stretching things a bit :-)

replies(2): >>26341243 #>>26341268 #
1. jcelerier ◴[] No.26341268[source]
> When you have enough memory for the set of all elements you want to store but not enough contiguous memory for the set of all elements you want to store

That's only relevant if you don't have an MMU tho. So not on any desktop or embedded system where ram is measured in gigabytes.

Otherwise it's up to the OS to handle that - only individual memory pages are contiguous, but not sets of pages.

replies(2): >>26341345 #>>26341769 #
2. ◴[] No.26341345[source]
3. saagarjha ◴[] No.26341769[source]
If your memory is fragmented enough you can have many pages that are lightly used, at which point a MMU isn't going to help.