> On 10 Apr 2016, at 22:44, Ted F.A. van Gaalen via swift-evolution > <[email protected]> wrote: > >> Say you wanted to stride through a singly-linked list, it would actually be >> beneficial to support only forward strides, the same is true of sequences, >> as you either may not know what the endpoint is, or would have to step >> through the whole sequence to find it (plus buffer every value in order to >> do-so safely). > What if you are already somewhere in the middle (perhaps landed there by > means of some other reference/link) of that linked list and want to stride > backward?
You can’t; if it’s singly-linked then there’s no way to do that directly with the target of O(1) complexity, i.e- for every step backward you’d have to start again from the beginning of the list and step forward till you reach the correct element, which would make it O(n) performance. For this reason, a singly linked list would want to provide only a ForwardIndex, as it isn’t suited to stepping backwards through its elements (that’s what a doubly-linked list is for, at the cost of even more overhead). _______________________________________________ swift-evolution mailing list [email protected] https://lists.swift.org/mailman/listinfo/swift-evolution
