3 ms·
And linked lists are the backbone of most persistent data structures and are commonly used as a build block for a ton of things, like LRU caches, queues, ...
by latch 7y ago
And linked lists are the backbone of most persistent data structures and are commonly used as a build block for a ton of things, like LRU caches, queues, ...
- deathanatos 7y agoI agree w/ the LRU, but isn't a vector more efficient for building a queue? (You use it as a ring-buffer. Push/pop are O(1) (amortized for push), and it interacts well with the CPU cache since the memory is contiguous. And you get O(1) indexing, too.) Then there's the rather interesting datastructure that C++ has, std::deque, which seems to get implemented as a vector of pointers to vectors. Still O(1) push/pop/index.