search

Amanieu / intrusive-rs

Intrusive collections for Rust
Apache License 2.0
400 stars 47 forks source link

Circular representation of SinglyLinkedList #54

Open kaspar030 opened 3 years ago

kaspar030 commented 3 years ago

IIUC the SinglyLinkedList provides front(), push_front() and pop_front(), as only those can be accessed in O(1), when the list keeps track of the list head.

If the list would keep track of the list tail, with the tail (or sentinel) connected circularly, wouldn't back() and push_back() be possible in O(1), (with one indirection for the front operations, e.g., front() = back().next())?

IMO that extends the space savings of a singly linked list (vs. doubly linked list) to many more use cases.

Amanieu commented 3 years ago

That's a neat idea! I'm happy to accept a PR for it.

kaspar030 commented 3 years ago

That's a neat idea! I'm happy to accept a PR for it.

Cool! I'll look into it. Don't expect results soon.