rc-dlist-deque - Doubly-linked list based on std::Rc

This crate provides a doubly-linked list implementation for circumstances where Rc is suitable for managing the individual nodes.

How to use this crate

See the module-level documentation

When not to use this crate

Many programmers new to Rust look for a linked list when another data structure is better. Consider Vec and VecDeque. A doubly-linked list is good if:

You need to retain and store, long-term, a reference to the middle of your list, and you need quick access to the corresponding item, and
You need to be able to quickly add or remove items in the middle of your list, based on such references; or your references into the middle of the list must remain valid even as you add or remove other items elsewhere in the middle, and
Your lists might be long.

In other circumstances, which is most circumstances, you probably wanted Vec or VecDeque instead. They have much lower overhead and are simpler to work with.

In particular:

If you don’t need to add/remove items in the middle, then a Vec or VecDeque works well. You can use array indices as your references.
If you want a VecDeque with stable indices, this can be achieved by maintaining a signed counter of elements pushed/popped at the start, as done by vecdeque-stableix.
If you don’t need to retain long-term references to the middle of the list, then you can use a vector. Adding or removing items in the middle does mean copying to shuffle items up or down, but if you aren’t keeping a reference to the modification location you will have to walk along to find the right place anyway.

Note that there are a number of deque-ish alternatives to std::VecDeque which are not doubly linked lists and do not aim to support modification in the middle of the list, at least some of which seem like they might be useful. Search crates.io for deque, and also consider blist.

Other doubly-linked list libraries

If you do need a doubly-linked list, but do not need your items to be on more than one list at once, consider generational_token_list instead. It has a much simpler ownership model and will be faster too.

If you want each item to be able to be on more than one list at once (perhaps even selecting the linked list link within each node dynamically at runtime), then this crate rc-dlist-deque may be what you want.

Survey of available Rust doubly linked lists, compared to VecDeque

(This table is rendered rather poorly by Rustdoc, lib.rs, etc. Use the correctly formatted version built standalone with pandoc, instead.)

Crate or module	Ref to element (aka Index or Cursor)				Other misuse possible, and consequences	List owns (`T` is element type)	Cost of editing in middle		Memory locality	Element can be on multiple lists	API completeness	`Send/Sync`	Safety	Comments
Crate or module	Type	After altering list at front/back	After altering list in middle	After removing ref’d element	Other misuse possible, and consequences	List owns (`T` is element type)	Given ref to elem	Without ref to elem	Memory locality	Element can be on multiple lists	API completeness	`Send/Sync`	Safety	Comments
Choose one of these approaches
`std VecDeque` (or another deque library)	`usize` position	wrong element if alteration at start	wrong element (or `None` or panic)		Rich API can invalidate indices	`T`	O(n)	O(n)	sequential	-	++	Yes	Good	Use if you don’t need persistent cursors
`vecdeque-stableix`	`i64 isize` …	valid	not supported		Index can overflow, giving panics.	`T`	O(n)		sequential	-	+	Yes	Safe	Consider if you need to modify only at ends
`rc-dlist-deque`	`Pointer<L,S>`	valid	valid	valid	Specify wrong list for alteration: `debug_assert`, “tangling”	`Rc<T>`	O(1)		scattered to heap	Yes	+	-	Safe	Consider if you need each element on multiple lists
`generational_token_list`	`ItemToken` slot+gen.	valid	valid	reliably `None` (`[]` panics)	Specify wrong list for access or alteration: Maybe detected by luck, giving `None`, otherwise wrong element	`T`			random order in vector	-	++	Yes	Safe (exc.`IterMut`)	Otherwise, use one of these
`dlv-list`	`Index<T>` slot+gen.	valid	valid	reliably `None` (`[]` panics)		`T`			random order in vector	-	++	Yes	Safe (exc.`IterMut`)	Otherwise, use one of these
Use `generational_token_list` or `dlv-list` instead of any of the following
`chainlink`	`Index` slot+gen.	valid	valid	reliably `None`	Specify wrong list for access or alteration: Maybe detected by luck, giving `None`, otherwise wrong element	`T`	O(1)	O(n)	random order in vector	-	-	Yes	Safe	No `IterMut`; otherwise plausible
`indexlist`	`Index<T>` slot+gen.			reliably `None`						-	- -	Yes	Safe	No `IterMut`; otherwise plausible
`index_list`	`Index` slot			`None` (or panic), or (later) wrong element						-	+	Yes	Safe
`slabigator`	`usize` slot					`T`	O(1)		random order in vector	-	-	Yes	uses `unsafe`	`usize` slot indices are a poor API choice
`array-linked-list`	`usize` slot					`T`	O(1)		random order in vector	-	+	Yes	needless `unsafe`	`usize` slot indices are a poor API choice
`im/im-rc Vector`	`usize` position	wrong element if alteration at start	wrong element (or `None` or panic)			`T`	O(log(n))		chunks in heap	-	+	`im`	uses `unsafe`	`usize` position indices are a correctness hazard
`skip-linked-list`	`usize` position	wrong element if alteration at start	wrong element (or `None` or panic)			`T`	O(log(n))		scattered to heap	-	-	-	uses `unsafe`	`usize` position indices are a correctness hazard
`cddl`	`Cursor`, `DoubleCursor`	valid	valid	not supported		`T`	O(1)		scattered to heap	-	- - -	-	uses `unsafe`	Strange and limited API
Use VecDeque instead of any of the following
`intrusive-collections linked_list`	`Cursor`[`Mut`]	Mutation not possible while any other cursor exists (prevented by lifetimes). This almost entirely defeats the point of using a doubly linked list.				Various	O(1)	O(n)	scattered to heap	Yes	+	Yes	uses `unsafe`	If this API is enough for you, use `VecDeque` instead
`cordyceps List`	`Cursor`[`Mut`] (roughly)					`unsafe impl Handle`			scattered to heap	-		Yes	`unsafe` to use!
`tsil_cev`	`Cursor`[`Mut`]					`T`			random order in vector	-		Yes	Safe (exc.`IterMut`)
`ixlist`	`Cursor`					`T`			random order in vector	-	+	Yes	needless `unsafe`
`linked-list`	`Cursor`					`T`			scattered to heap	-		Yes	uses `unsafe`
`cyclic_list`	`Cursor`[`Mut`]					`T`			scattered to heap			Yes	uses `unsafe`
`pin-list`	`Cursor`[`Mut`]					Complicated			user provides `Pin<&mut Node>`	-		Yes	uses `unsafe`
`key-node-list`	`Cursor`[`Mut`]					`T`	O(log(n))		in vector (via `HashMap`)	-	-	Yes
`std LinkedList`	Not supported. This defeats the point of using a doubly linked list.					`T`	n/a		scattered to heap	-		Yes
`doubly`						`T`			scattered to heap	-		Yes	uses `unsafe`
`linked_lists_rs` / `rust_linked_list`						`T`			scattered to heap	-		Yes	uses `unsafe`
`xor_list`						`T`			scattered to heap	-		-	uses `unsafe`
`index_queue`						`T`			sequential	-	- -	Yes		Reimplementation of `VecDeque`

It can be hard to implement IterMut without using unsafe , so no criticism is intended for those crates that use unsafe for this.

Not considered

Single-ended, or special purpose)

Not considered here because they are a single-ended list (so there is little reason to use anything but a Vec); or because they are special purpose:

c_linked_list, char-list, concurrent_list, cons-list, doubly_linked_list, fplist, functional_list, fwdlist, im-list, linked_hash_map, linked_hash_set, linked_list_allocator, linked-tail-list, list, moonlight_collections, nerdondon-hopscotch, nt_list, persistent-list, rose_bloom, secured_linked_list, simple-stack, stack_list, static-linkedlist, weak-list2, uell, unrolled_linked_list.

Not intended (or not suitable) for general use

Not considered here because of poor or missing docs, very poor API, Nightly-only, won’t build, or other indications that they’re not intended (or suitable) for use by the world in general:

cll, clist, double_linkedlist, dynalist, ilist, linkedlist, rs_trie, static-linkedlist, matecito-dll.

Survey colophon

Last updated, and last resurveyed, November 2022. If I do a future survey, I may look at only the most popular crates. Please let me know if you think your library ought to be listed in the section “Choose one of these approaches”.

Changelog and colophon for `rc-dlist-deque`

Minimum Supported Rust Version is 1.31.0. MSRV policy: We do not anticipate changing the MSRV in the foreseeable future. If we do, it will be at least a minor version bump. We will not increase the MSRV beyond that available in Debian oldstable.

1.1.2

Minor updates to doubly linked list survey (crate level docs).
No API or implementation changes.

1.1.1

Minor updates to doubly linked list survey (crate level docs).
No API or implementation changes.

1.1.0

MSRV 1.31.0 (was 1.30.0)
Change to 2018 edition.
Add this Changelog.
Update doubly linked list survey (crate level docs).
Changes to documentation generation and release arrangements.

1.0.0

Documentation. No API or implemnetation changes.

0.1.0

First public release.