Circular representation of SinglyLinkedList

[kaspar030]

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]

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

[kaspar030]

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.