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-evolut...@haravikk.me> wrote: > > >>> On 10 Apr 2016, at 22:44, Ted F.A. van Gaalen via swift-evolution >>> <swift-evolution@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).
_______________________________________________ swift-evolution mailing list swift-evolution@swift.org https://lists.swift.org/mailman/listinfo/swift-evolution
