DEV Community

Discussion on: How to write a Stack in Rust

elshize profile image
Michał Siedlaczek

I don't think their statement has anything to do with it being doubly-linked.

The reason why it is generally a good idea to use Vec for a stack is the same why we use vectors instead of linked lists in the first place. And it is exactly what you quoted above.

Note that the vector is reallocated but then the capacity is doubled, so you will have a linear amortized number of allocated values. However, you will allocate far fewer times than you would in case of a linked list, which would be each time you push. You'd also have to keep deallocating when popped, while in case of a vector, a pop operation is very cheap, it isn't deallocated right away if at all.

I think in general, you should always question the use of a linked list. There must be a very good reason to use it. And I mean a really good reason.