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

>So the first question: Why are you using a doubly-linked list? :-)

Honestly 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.

In a linked list you can just overwrite the previous node to link to the next node.

However what I do is I just swap the element with the last one in a vector and delete the last element. This doesn't preserve the order of the list but for me this has never been a significant issue.




”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: