Hacker News new | past | comments | ask | show | jobs | submit login

”there is only one legitimate usecase for a linked list that can only be solved suboptimally with a continguous array. Removing elements in the middle of a list assuming you already know the pointer to the linked list node.”

You will be surprised to see how large a memmove you can do on modern hardware in the time it would chase those pointers.

For an extreme example (moving array data gets slower if your elements grow larger), see https://youthdev.net/en/performance-of-array-vs-linked-list-...




The usecase imtringued was talking about:

> assuming you already know the pointer to the linked list node

For example a LinkedHashMap where a hash provides the primary means of looking up elements and the nodes contain an intrusive linked list. Removing an element from that list doesn't involve chasing pointers from the start of it.

The linked benchmark is for a different scenario.




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: