DEV Community

Discussion on: How to write a Stack in Rust

Collapse
virtualkirill profile image
Kirill Vasiltsov Author • Edited on

Maybe. The problem is that the native LinkedList implementation in Rust is a doubly-linked list. On its page authors say that

It is almost always better to use Vec or VecDeque because array-based containers are generally faster, more memory efficient, and make better use of CPU cache.

So we would need to first build a singly-linked list but it is much harder than Stack itself, so not very suitable for a beginner article.

Collapse
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.