Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Getting the pointer to that element means randomly hopping around the heap to traverse the list though.

Linked lists are perfect for inserting/deleting nodes, as long as you never need to traverse the list or access any specific node.



You’re assuming no other data structure points to the element. It may. Example: implement a cache.

Each element is: key, value, linked list node for hash table bucket, linked list node for LRU. Hash table to look up element. Element is both a member of hash table and of linked list. Linked list is used as LRU for feeling memory when needed.

LRU never traversed but often needs removal and reinsertion.




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

Search: