3 ms·

Wait are linked lists not better for first-in first-out data structures? I thought arrays were not preferred in those cases because shift/unshift are highly ine

by pitaj 8y ago

Wait are linked lists not better for first-in first-out data structures? I thought arrays were not preferred in those cases because shift/unshift are highly inefficient. Am I wrong? I thought array-based queues resulted in O(n) queue/dequeue. Now for stacks, which are last-in first-out, it makes sense to use an array.

eximius 8y ago
You use an array with pointers to the front and back of the queue, essentially a circular buffer. You might need to resize, but that happens for any array backed structure and is one (or two) memcpys.
deathanatos 8y ago
> I thought array-based queues resulted in O(n) queue/dequeue. Not necessarily. A circular buffer[1] can be used as a queue with O(1) queue/dequeue. C++ implementations (gcc?), IIRC, uses an interesting array-of-arrays approach; it also has O(1) queue/dequeue. I'm not sure why the array-of-arrays approach is better than a circular buffer, though. Array based designs can result is less allocations, and maybe less overhead. For example, if you have a circular buffer with space for 16 items, it only needs to allocate space if you need more room, whereas a linked list queue would allocate for each and every item placed into it. Linked lists also require space for the pointer to the next link, for each link in the list. (And, if you keep them, back pointers, though these aren't necessary for just a queue.) Arrays might have some unused slack space, however. [1]: https://en.wikipedia.org/wiki/Circular_buffer https://en.wikipedia.org/wiki/Circular_buffer
- jayd16 8y ago
  Resizing a fully contiguous circle buffer would cause a copy every element as well forcing you to make a single contiguous memory section. Array of arrays just needs to resize the top level array.
  - manwe150 8y ago
    But the copy only has to move n items, but was constructed with m items, where n < m (and usually n << m). Where n is the max size of the queue and m is the total number of items that will ever be enqueued. On the other hand, an array of arrays (no recursion) doesn’t change the big-O complexity cost, just the constant multiplier. That should definitely improve performance of the uncommon operation (the copy), but hypothetically might slow down the actual queuing operations (and drastically reduce throughout) But maybe you meant the array of arrays to be recursive? That seems like it would alter the big-O (from n+m to log(n)+m). But typically m>>n, so the net result is the same.
manwe150 8y ago
Only if you eagerly shift all elements on every operation. If you allocate extra space, and only shift every N operations (N being the max size of the list), it’s O(n/n), eg O(1) amortized. As mentioned already, you can represent it as a circular buffer to save a bit of memory. But this cost analysis also means that a simple array can be much faster than a linked list for almost all operations in theory (excludes random insert given an insert token, which is not an index). I believe there’s also experimental evidence of this showing that an array is almost always preferable to a linked list - even in the cases were a linked list is often taught as the obvious choice (such as a queue). Yep, surprised me quite a bit too.

by pitaj 8y ago

eximius 8y ago

You use an array with pointers to the front and back of the queue, essentially a circular buffer. You might need to resize, but that happens for any array backed structure and is one (or two) memcpys.

deathanatos 8y ago

> I thought array-based queues resulted in O(n) queue/dequeue. Not necessarily. A circular buffer[1] can be used as a queue with O(1) queue/dequeue. C++ implementations (gcc?), IIRC, uses an interesting array-of-arrays approach; it also has O(1) queue/dequeue. I'm not sure why the array-of-arrays approach is better than a circular buffer, though. Array based designs can result is less allocations, and maybe less overhead. For example, if you have a circular buffer with space for 16 items, it only needs to allocate space if you need more room, whereas a linked list queue would allocate for each and every item placed into it. Linked lists also require space for the pointer to the next link, for each link in the list. (And, if you keep them, back pointers, though these aren't necessary for just a queue.) Arrays might have some unused slack space, however. [1]: https://en.wikipedia.org/wiki/Circular_buffer https://en.wikipedia.org/wiki/Circular_buffer

jayd16 8y ago
Resizing a fully contiguous circle buffer would cause a copy every element as well forcing you to make a single contiguous memory section. Array of arrays just needs to resize the top level array.
- manwe150 8y ago
  But the copy only has to move n items, but was constructed with m items, where n < m (and usually n << m). Where n is the max size of the queue and m is the total number of items that will ever be enqueued. On the other hand, an array of arrays (no recursion) doesn’t change the big-O complexity cost, just the constant multiplier. That should definitely improve performance of the uncommon operation (the copy), but hypothetically might slow down the actual queuing operations (and drastically reduce throughout) But maybe you meant the array of arrays to be recursive? That seems like it would alter the big-O (from n+m to log(n)+m). But typically m>>n, so the net result is the same.

manwe150 8y ago

Only if you eagerly shift all elements on every operation. If you allocate extra space, and only shift every N operations (N being the max size of the list), it’s O(n/n), eg O(1) amortized. As mentioned already, you can represent it as a circular buffer to save a bit of memory. But this cost analysis also means that a simple array can be much faster than a linked list for almost all operations in theory (excludes random insert given an insert token, which is not an index). I believe there’s also experimental evidence of this showing that an array is almost always preferable to a linked list - even in the cases were a linked list is often taught as the obvious choice (such as a queue). Yep, surprised me quite a bit too.