4 ms·
Okay first of, before I read the rest of the article, I want to complain about the statement: > While you can hack together a “list” that will be backed by a V
by webkike 10y ago
Okay first of, before I read the rest of the article, I want to complain about the statement:
> While you can hack together a “list” that will be backed by a Vec of nodes with indices to the next / previous item, this approach is quite wasteful – and gains little compared to using the Vec directly.
How is this wasteful or hacky?? This is THE proper way of writing data structures that are not strict trees. Sure, this isn't the correct way to write a list data structure, but there's almost no reason to use a linked list in general.
- tyoverby 10y agoWhen most people ask for a linked list data structure, they probably don't mean "a vector of elements and a linked list of indexes into that vector" because it totally defeats the purpose of using a linked list in the first place.
- webkike 10y agoWell when most people ask for a linked list my first response would be "why?"
- charles-salvia 10y agoan LRU cache?
- webkike 10y agoI'm not saying there aren't reasons to use link lists, but often the correct approach is a hybrid one and additionally for cache aware programs a vector of entries with indirection integers is going to be more local