"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.

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
closed #5

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