"LinkedList lacks support for some basic linked list operations"

libs
1

https://www.reddit.com/r/rust/comments/8wlkbe/actixweb_has_removed_all_unsound_use_of_unsafe_in/e1y4ynr/

The standard LinkedList lacks support for some basic linked list operations, such as insertion in the middle of the list.

If this is still true, it should probably be fixed.

1 Like
2

I believe the closest that exists currently is

let mut list: LinkedList;

let mut tail = list.split_off(idx); // O(n), seek idx and split
list.push_back(el); // O(1), push to back
list.append(&mut tail); // O(1), move tail's elements back to list

Without dependent typing, a safe O(1) insert cannot be provided from the LinkedList itself. Perhaps a Cursor API could be added that allows you to travel up and down the tape, thus separating the seek and insert costs?

(Unquoted context:

O(1) insertion is often the reason why linked list gets chosen as data structure, and is what the quoted [source of unsafety in actix-web] implements.

)

3

Unfortunately itā€™s just hard, since usually with a linked list you want something like ā€œinsert it after this spot I got from someone elseā€, but that interacts poorly with borrowing in most cases.

Iā€™d love to find a way to make an API allowing all the things that iterators can do in C++, but safeā€¦

1 Like
4

I know of 2 implementations of cursors for linked lists on crates.io:

2 Likes
5

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.