Singly-linked list/Reversal

I don't even know how to reverse a linked-list, and I don't even know what that is. -- a YouTuber.

Reverse a linked list. Obviously you can do it by turning it into a normal list and back, but feel free to use a smarter, possibly more efficient way.

ALGOL 68

Using the code from the Singly-linked list/Traversal#ALGOL_68 Task
LOC and HEAP are like NEW in other languages. LOC generates a new item on the stack and HEAP a new item on the heap (which is garbage collected).
The use of LOC in the outermost level is OK as the generated elements will exist until the final END, but HEAP must be used in the loop creating the reverse list elements, to ensure they still exist when the loop exits.

BEGIN
  MODE STRINGLIST = STRUCT(STRING value, REF STRINGLIST next);

  # construct a STRINGLIST with a few elements #
  STRINGLIST list := ("Big",
    LOC STRINGLIST := ("fjords",
      LOC STRINGLIST := ("vex",
        LOC STRINGLIST := ("quick",
          LOC STRINGLIST := ("waltz",
            LOC STRINGLIST := ("nymph",NIL))))));

  # print the list and build the reverse list #
  REF STRINGLIST node    := list;
  REF STRINGLIST reverse := REF STRINGLIST(NIL);
  WHILE node ISNT REF STRINGLIST(NIL) DO
    reverse := HEAP STRINGLIST
            := STRINGLIST( value OF node, reverse );
    print((value OF node, space));
    node := next OF node
  OD;
  print(newline);
  # print the reverse list #
  node := reverse;
  WHILE node ISNT REF STRINGLIST(NIL) DO
    print((value OF node, space));
    node := next OF node
  OD;
  print(newline)
END

Output:

Big fjords vex quick waltz nymph
nymph waltz quick vex fjords Big

Julia

Modern processors with large caches and fast memory access for ordinary vectors and databases for larger types of data structures have made linked lists nearly obsolete. In Julia, arrays are almost always preferred to linked lists. A linked list class is available in the DataStructures.jl package. The code below is abridged from that module, which can be read in its full form at https://github.com/JuliaCollections/DataStructures.jl/blob/master/src/list.jl.

abstract type LinkedList{T} end

Base.eltype(::Type{<:LinkedList{T}}) where T = T

mutable struct Nil{T} <: LinkedList{T} end

mutable struct Cons{T} <: LinkedList{T}
    head::T
    tail::LinkedList{T}
end

cons(h, t::LinkedList{T}) where {T} = Cons{T}(h, t)

nil(T) = Nil{T}()
nil() = nil(Any)

head(x::Cons) = x.head
tail(x::Cons) = x.tail

function Base.show(io::IO, l::LinkedList{T}) where T
    if isa(l,Nil)
        if T === Any
            print(io, "nil()")
        else
            print(io, "nil(", T, ")")
        end
    else
        print(io, "list(")
        show(io, head(l))
        for t in tail(l)
            print(io, ", ")
            show(io, t)
        end
        print(io, ")")
    end
end

function list(elts...)
    l = nil(Base.promote_typeof(elts...))
    for i=length(elts):-1:1
        l = cons(elts[i],l)
    end
    return l
end

Base.iterate(l::LinkedList, ::Nil) = nothing
function Base.iterate(l::LinkedList, state::Cons = l)
    state.head, state.tail
end

function Base.reverse(l::LinkedList{T}) where T
    l2 = nil(T)
    for h in l
        l2 = cons(h, l2)
    end
    return l2
end

llist = list(1, 2, 3, 4, 5)
revlist = reverse(llist)
@show llist revlist

Output:

llist = list(1, 2, 3, 4, 5)  
revlist = list(5, 4, 3, 2, 1)

Wren

Library: Wren-llist

Library: Wren-iterate

The LinkedList class in Wren-llist represents a singly-linked list.

It's possible to iterate backwards through this without creating an intermediate list by traversing through it until you reach the last element, then traversing through it again until you reach the penultimate element and so on until you reach the first element. This is easy to code since LinkedList has an indexer which works in precisely this manner.

It's also possible to iterate backwards through the linked list using the generic reverse iterator in Wren-iterate. However, this does create a list internally and then iterates backwards through that.

You could, of course, create a new LinkedList and then add elements to it as you iterate through them in reverse order.

However, it's also possible to reverse the LinkedList in place by successively exchanging elements at both ends. Internally, the 'exchange' method uses the indexer to swap elements.

import "./llist" for LinkedList
import "./iterate" for Reversed

var pangram = "Big fjords vex quick waltz nymph"
var elements = pangram.split(" ")
var sll = LinkedList.new(elements)

// iterate forwards
for (e in sll) System.write("%(e) ")
System.print("\n")

// iterate backwards without creating a list
for (i in sll.count-1..0) System.write("%(sll[i]) ")
System.print("\n")

// iterate backwards by creating a list internally
for (e in Reversed.new(sll)) System.write("%(e) ")
System.print()

// reverse the linked list in place
var i = 0
var j = sll.count - 1
while (i < j) {
    sll.exchange(i, j)
    i = i + 1
    j = j - 1
}
// now we can iterate forwards
for (e in sll) System.write("%(e) ")
System.print()

Output:

Big fjords vex quick waltz nymph 

nymph waltz quick vex fjords Big 

nymph waltz quick vex fjords Big

nymph waltz quick vex fjords Big