[swift-evolution] [Draft]: Introducing a striding(by:) method on 3.0 ranges

[ted van gaalen]

ah, you're right about that! 
somehow there was a doubly linked list in my head, sorry.

TedvG

> On 11 Apr 2016, at 11:20, Haravikk <swift-evolution at haravikk.me> wrote:
> 
> 
>>> On 10 Apr 2016, at 22:44, Ted F.A. van Gaalen via swift-evolution <swift-evolution at swift.org> 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).
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160411/8154f6bd/attachment.html>