Comment #0 by bearophile_hugs — 2014-04-12T00:50:58Z
I suggest to add to std.container.SList a method that reverses the list in-place efficiently (O(n) and with no or nearly no memory allocations), equivalent to this functions that reverses a singly linked list:
Node* reverse(Node* s1) pure nothrow {
Node* s2;
while (s1) {
auto next = s1.next;
s1.next = s2;
s2 = s1;
s1 = next;
}
return s2;
}
Comment #1 by monkeyworks12 — 2014-06-07T12:44:34Z
Why not use std.range.retro? The only downside is that you can't assign the result back to the original SList.
Comment #2 by bearophile_hugs — 2014-06-07T16:23:22Z
(In reply to monkeyworks12 from comment #1)
> Why not use std.range.retro? The only downside is that you can't assign the
> result back to the original SList.
A SList is usually implemented with a chain of 2-structs that contain a cargo plus a forward pointer. So you can't walk them backwards with retro. And indeed this doesn't compile:
void main() {
import std.stdio: writeln;
import std.container: SList;
import std.range: retro;
auto list = SList!int([1, 7, 42]);
list[].writeln;
list[].retro.writeln;
list.retro.writeln;
}