4 ms·
In almost all cases, it is better to use a vector for both those data structures. Cache locality is king, memcpy is blazing fast, and pointer chasing is general
by sunshowers 3y ago
In almost all cases, it is better to use a vector for both those data structures. Cache locality is king, memcpy is blazing fast, and pointer chasing is generally pretty bad for performance.
For a stack, just use a regular vector. Pushes are amortized O(1), and pops are O(1).
For a queue, a ring buffer backed by a vector. (This is how VecDeque in Rust's stdlib works.) Again, enqueue is amortized O(1) and dequeue is O(1).
Even if you do need to use a linked list, it's generally better to depend on someone else's implementation than write your own.
- dmitrygr 3y ago> it's generally better to depend on someone else I am the someone else who writes that, often enough… All y'all forget that behind your cute libraries and abstractions stands someone who wrote them in C or assembly…
- sunshowers 3y agoIn that case, you'll find that Rust is an excellent language for writing doubly-linked lists. A lot of the point of Rust is to make a few people do the hard work of writing some complex data structure in unsafe code, and let everyone else reap the benefits.
- keybored 3y agoWhere do I send the thank you card?