4 ms·
> There is almost no case where you need to traverse a list in both directions But you might need to remove a given element that you have a pointer to in O(1),
by dmitrygr 1y ago
> There is almost no case where you need to traverse a list in both directions
But you might need to remove a given element that you have a pointer to in O(1), which a singly linked list will not do
- dwattttt 1y agoIf that's a specific use case you need to handle, it's O(1) again if you have a pointer to both the node to be removed and the previous node. Whether it's more efficient to carry a second pointer around when manipulating the list, or store a second pointer in every list node (aka double linked list) is up to your problem space. Or whether an O(n) removal is acceptable.
- MeetingsBrowser 1y agoGetting 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.
- dmitrygr 1y agoYou’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.