(from @hawkw): It occurs to me that if we want to not have the insert operation be O(n), but we also don't want to go with a full intrusive tree implementation, we could probably use a skip list and binary search. If we went down that route, though, we would have to go with a Links type that's more complex than the stack::Links type, to include the skiplist pointers. However, we might still be able to maintain the ability to link a value into both a SortedList and a Stack if we did something like this:

// in sorted list module
pub struct Links<T> {
     layer_0: stack::Links<T>,
     skip_layers: [Option<NonNull<T>>; NUM_SKIP_LAYERS],
}

// Make anything that has sorted-list links "count" as having stack links too
impl<T: Linked<stack::Links<T>>> for  T where T: Linked<Links<T>> {
    // ... some wacky unsafe code to offset the pointers returned by the
    // `Linked<Links<T>>` impl to get the `stack::Links` out of them, which
    // i didn't want to write, but i'm sure is possible...
}

Originally posted by @hawkw in #520 (comment)