4 ms·
The place I see linked lists pop up the mosts are when implementing LRU caches. You need a linked hashmap of sorts where the hashmap gives O(1) lookup to the li
by gamegoblin 4y ago
The place I see linked lists pop up the mosts are when implementing LRU caches. You need a linked hashmap of sorts where the hashmap gives O(1) lookup to the linked list node in question, and then you can extract that node and move it to the head of the queue in O(1) as well.
This is a special case of where they also appear: linked hashmap implementations, where you want a hashmap that has a consistent iteration order.
- josephg 4y agoI’ve seen them show up in lots of situations through intrusive lists, which I think is the general form of the example you’re giving. Intrusive lists are used in the Linux kernel, in physics engines (eg Chipmunk2d) and game engines. The way Redis uses them for TTL expiry follows the same pattern.
- xxs 4y agoHaving linked nodes of a hashmap, is just that - I'd not call it a linked list. You can do moving median with a binary tree and linked nodes, too.