"LinkedList lacks support for some basic linked list operations"


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

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.



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

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

closed #5

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