3 ms·
a double-ended queue is often implemented using a doubly linked list (like the one in use here) if you back it by two arrays then you can't do O(1) inserts in
by blibble 2y ago
a double-ended queue is often implemented using a doubly linked list (like the one in use here)
if you back it by two arrays then you can't do O(1) inserts in the middle (like is going on here)
- tialaramex 2y agoIt's true that awful Deque implementations are often built from a linked list. If you're taught about big-O notation and haven't noticed how modern computers work you might even do that today. I would expect that they're thinking of something more like Rust's VecDeque, so that's a conventional "growable array" (Rust's Vec, Java ArrayList, C++ std::vector) used internally with some head + tail tracking to form a circular buffer so as to deliver the Deque API (fast push to head or tail, fast pop from head or tail).
- blibble 2y agoyou can make mechanically sympathetic linked lists with low constant factors as long as you avoid pointers
- vanderZwan 2y agoDo you mean using indices into a backing array instead of pointers if the maximum length is known to be small? That probabdy helps but still has the cache issue to some degree no? (also I feel like this is arguing semantics a bit, but I'm sincerely wondering: is a linked list without pointers still a linked list?)