4 ms·

For most use cases a ring buffer either with or without a maximum length will do much better as a queue than a linked list will. There are some niche use cases

For most use cases a ring buffer either with or without a maximum length will do much better as a queue than a linked list will. There are some niche use cases where linked lists are good. Lock-free queues are one, and another big set of use cases is where you need hard O(1) insert even with a high constant factor, not amortized O(1).

anonymoushn 4y ago
High-performance SPSC queues are always implemented with an array. If you need hard O(1) insert you can usually just allocate an array much bigger than you will need. The combination of hard performance requirements and willingness to wait for an allocator all the time is unusual.
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 ago
  I’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 ago
  Having 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.
xxs 4y ago
>where you need hard O(1) insert even with a high constant factor You will need a truly concurrent memory allocator for that, too... or if you are just the kernel (one of the reasons the linux kernel can benefit from linked lists) Overall, allocating new objects/memory is not guaranteed O(1).

anonymoushn 4y ago

High-performance SPSC queues are always implemented with an array. If you need hard O(1) insert you can usually just allocate an array much bigger than you will need. The combination of hard performance requirements and willingness to wait for an allocator all the time is unusual.

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 ago
I’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 ago
Having 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.

xxs 4y ago

>where you need hard O(1) insert even with a high constant factor You will need a truly concurrent memory allocator for that, too... or if you are just the kernel (one of the reasons the linux kernel can benefit from linked lists) Overall, allocating new objects/memory is not guaranteed O(1).