Stack based on vector is bad idea, because vector internally based on array, that need to be reallocated, when capacity is reached.
You must use linked list instead
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.
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.
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
Stack based on vector is bad idea, because vector internally based on array, that need to be reallocated, when capacity is reached.
You must use linked list instead
Maybe. The problem is that the native
LinkedListimplementation in Rust is a doubly-linked list. On its page authors say thatSo 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.
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
Vecfor 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.