Singly and Doubly Linked List collections in standard library

Evolution Discussion
65

I've updated the Gist with a sample singly-linked list type. I still haven't really tested it, though.

There's one thing I found out:

  • public subscript(bounds: Range<Index>) -> SinglyLinkedList
  • public mutating func trade(_ subrange: inout LeftOpenRange<Index>, with other: inout SinglyLinkedList, along otherSubrange: inout LeftOpenRange<Index>)

at most one of these can be O(1).

The original plan was trade(_: with: along:) being O(1). This means that all the nodes need to be directly visible when doing the trading. But this means that I have to layout all the nodes when constructing a sub-sequence; so a subscript would be O(n).

But the Standard Library prefers subscripting to be O(1). This means storing only the class pointer to the storage and the end points. So I can only get all of the specified nodes during trade(_: with: along:) by walking the list, making that O(n) instead.

`RangeExpression`s with exclusive lower bounds