3 ms·
But a hash table using separate chaining requires linked lists, so still pretty fundamental.
by Something1234 7y ago
But a hash table using separate chaining requires linked lists, so still pretty fundamental.
- latch 7y agoAnd 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.