steveklabnik/indexlist

---

steveklabnik/indexlist.json

{
  "createdAt": "2018-09-14T21:23:37Z",
  "defaultBranch": "master",
  "description": "indexlist: A doubly linked list, backed by a vector",
  "fullName": "steveklabnik/indexlist",
  "homepage": null,
  "language": "Rust",
  "name": "indexlist",
  "pushedAt": "2023-08-30T21:42:40Z",
  "stargazersCount": 85,
  "topics": [
    "data-structures",
    "rust"
  ],
  "updatedAt": "2025-11-08T18:15:40Z",
  "url": "https://github.com/steveklabnik/indexlist"
}

indexlist - A doubly linked list, backed by a vector.

This crate provides a struct, IndexList<T>, which is a doubly-linked list. However, unlike a traditional linked list, which heap allocates each of its nodes individually, all nodes are stored in a vector. Rather than provide pointers to nodes, an Index struct can be used to access a particular element in the middle of the list.

Safety

This crate uses #![deny(unsafe_code)] to ensure everything is implemented in 100% Safe Rust.

Generational indexes

Index uses a generations scheme, so that if you hold an Index to a node, and it’s removed, and a new node is allocated in its place, you do not access the new node.

Performance

In general, performance is quite good. Benchmarks against the standard library’s LinkedList<T> are provided. But some other details:

• The list keeps track of its head and tail for efficient insertion.
• The underlying vector only grows, never shrinks. When a node is removed, its entry is marked as free for future insertions.
• Free entries are themselves kept as a singly-linked list, meaning that they can be re-used efficiently.

Missing features

Right now, I’ve only implemented a minimal number of features; there’s iter but no into_iter and iter_mut. This is on the to-do list. PRs welcome!