//! # 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. //! // Copyright (C) 2019-2022 Ian Jackson // // This program is free software: you can redistribute it and/or modify // it under the terms of the GNU General Public License as published by // the Free Software Foundation, either version 3 of the License, or // (at your option) any later version. // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program. If not, see . //! How to use this crate //! ===================== //! //! See the [module-level documentation](dlist/index.html) //! //! 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`](https://lib.rs/crates/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`](https://lib.rs/crates/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](https://www.chiark.greenend.org.uk/~ianmdlvl/rc-dlist-deque/) //! 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. //! //! `rc-dlist-deque` is Copyright 2019-2022 Ian Jackson. //! GNU GPLv3+; NO WARRANTY. pub mod dlist;