"LinkedList lacks support for some basic linked list operations"


#1

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.


#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…


#4

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