[−][src]Crate rc_dlist_deque
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
orVecDeque
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. -
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 dlv-list-rs
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
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 | ||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Type | After altering list at front/back | After altering list in middle | After removing ref'd element | Given ref to elem | Without ref to elem | |||||||||
Choose one of these approaches | ||||||||||||||
std VecDeque |
usize |
wrong element if alteration at start | wrong element | wrong element | Rich API can invalidate indices | T |
O(n) | O(n) | sequential | - | ++ | Yes | Good | Use if you don't need persistent cursors |
std VecDeque with front counter |
isize |
valid | wrong element | wrong element | T |
O(n) | O(n) | sequential | - | DIY | Yes | Good | 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) | O(n) | scattered to heap | Yes | + | - | Safe | Consider if you need each element on multiple lists |
dlv-list-rs |
Index<T> |
valid | valid | gives None ([] panics) |
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 (exc.IterMut ) |
Otherwise, use this |
indexlist |
Index<T> |
T |
O(1) | O(n) | - | -- | Yes | Safe | No IterMut |
|||||
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 |
|||
ixlist |
Cursor |
T |
O(1) | O(n) | random order in vector | - | Yes | Safe (exc.IterMut ) |
||||||
linked-list |
Cursor |
T |
O(1) | O(n) | scattered to heap | - | Yes | uses unsafe |
||||||
std LinkedList |
Not supported. This defeats the point of using a doubly linked list. | T |
O(n) | scattered to heap | - | Yes | ||||||||
doubly |
T |
O(n) | scattered to heap | - | Yes | uses unsafe |
Not considered here because single-ended, or special purpose):
index_queue
,
c_linked_list
,
linked_list_allocator
,
linked-tail-list
,
static-linkedlist
.
Not considered here because no Rustdocs, does not build with modern Rust:
dynalist
.
It can be hard to implement IterMut
without using
unsafe
, so no criticism is intended for those crates
that use unsafe for this.
Last updated May 2019.
Modules
dlist | See the crate-level documentatio for a discussion of whether to use this crate. |
Macros
DlistDefineStaticSelector |
|
DlistImplSelector |
|