<html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body dir="auto"><div>ah, you're right about that! </div><div id="AppleMailSignature">somehow there was a doubly linked list in my head, sorry.<br><br><div><div><div apple-content-edited="true"><div><div><font color="#000000"><span style="background-color: rgba(255, 255, 255, 0);"></span></font></div></div></div></div></div></div><div id="AppleMailSignature">TedvG</div><div><br>On 11 Apr 2016, at 11:20, Haravikk <<a href="mailto:swift-evolution@haravikk.me">swift-evolution@haravikk.me</a>> wrote:<br><br></div><blockquote type="cite"><div><span></span><br><blockquote type="cite"><span>On 10 Apr 2016, at 22:44, Ted F.A. van Gaalen via swift-evolution <<a href="mailto:swift-evolution@swift.org">swift-evolution@swift.org</a>> wrote:</span><br></blockquote><blockquote type="cite"><span></span><br></blockquote><blockquote type="cite"><blockquote type="cite"><span>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).</span><br></blockquote></blockquote><blockquote type="cite"><span>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? </span><br></blockquote><span></span><br><span>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).</span></div></blockquote></body></html>