Hands-On Data Structures and Algorithms with Rust
上QQ阅读APP看书,第一时间看更新

Upsides

The main benefits of a linked list are the abilities to grow very large in size cheaply, always maintain a certain direction, and allow to access items individually. What makes this data structure unique?

There are a few points:

  • Low overhead allocation per item.
  • Item count is only limited by heap memory.
  • Mutation while iterating is possible.
  • A direction is strictly enforced—there is no going back.
  • Implementation is fairly simple (even in Rust).
  • Efficient append, prepend, delete, and insert operations—compared to an array (no shifting required).

Generally, the linked list performs well in an environment where limited memory does not allow overhead allocation (as dynamic arrays do), or as a basis for an exotic lock-free data structure.