Singly-linked list/Reversal

Singly-linked list/Reversal is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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

J

Linked lists in J tend to be tremendously inefficient, and of limited utility. (And, generally speaking, their cache footprint tends to conflict with any theoretical algorithmic gains on other machines in other languages also, but J is worse here.)

But let's ignore those problems and implement a routine to build us a linked list and then a routine to reverse it:

car=: 0{::]
cdr=: 1{::]
list2linkedlist=: ]`(car;<@$:@}.)@.(*@#)
reverselinkedlist=: '' {{x [`((car;<@[) $: cdr)@.(*@#@]) y }} ]

Example use:

   list2linkedlist i.6
┌─┬────────────────────┐
│0│┌─┬────────────────┐│
│ ││1│┌─┬────────────┐││
│ ││ ││2│┌─┬────────┐│││
│ ││ ││ ││3│┌─┬────┐││││
│ ││ ││ ││ ││4│┌─┬┐│││││
│ ││ ││ ││ ││ ││5│││││││
│ ││ ││ ││ ││ │└─┴┘│││││
│ ││ ││ ││ │└─┴────┘││││
│ ││ ││ │└─┴────────┘│││
│ ││ │└─┴────────────┘││
│ │└─┴────────────────┘│
└─┴────────────────────┘
   reverselinkedlist list2linkedlist i.6
┌─┬────────────────────┐
│5│┌─┬────────────────┐│
│ ││4│┌─┬────────────┐││
│ ││ ││3│┌─┬────────┐│││
│ ││ ││ ││2│┌─┬────┐││││
│ ││ ││ ││ ││1│┌─┬┐│││││
│ ││ ││ ││ ││ ││0│││││││
│ ││ ││ ││ ││ │└─┴┘│││││
│ ││ ││ ││ │└─┴────┘││││
│ ││ ││ │└─┴────────┘│││
│ ││ │└─┴────────────┘││
│ │└─┴────────────────┘│
└─┴────────────────────┘

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)

Pascal

Free Pascal

Reverting list by reverting the pointers.

program RevSingleLinkedList;
type
  tdata = string[15];
  tpsList = ^tsList;
  tsList = record
             data:tData;
             next : tpsList; 
           end;   
const
  cData: array[1..6] of string = ('Big','fjords','vex','quick','waltz','nymph');           

var
  root : tpsList;

function InitLList(cnt:integer):tpsList;
var
  root,tmpList : tpsList;
  i : integer;
begin
  tmpList := new(tpsList);
  root := tmpList;
  root^.data := cData[1];
  For i := 2 to high(cData) do
  begin
    tmpList^.next := new(tpsList);
    tmpList := tmpList^.next;  
    tmpList^.data := cData[i];
  end;  
  tmpList^.next := NIL;
  InitLList := root; 
end;  

procedure OutList(root:tpsList);
begin
  while root <> NIL do
  begin
    write(root^.data,' ');
    root := root^.next;
  end;
  writeln;
end;    

procedure RevList(var root:tpsList);
var
  NextinList,NewNext : tpsList;
begin
  if (root = NIL) OR (root^.next = nil) then
    EXIT;
  NextinList := root^.next;
  root^.next := NIL;
  while NextinList <> NIL do
  begin 
    //memorize list element before
    NewNext := root;
    //root set to next element of root
    root := NextinList;
    //get the next in list 
    NextinList := NextinList^.next;
    //correct pointer to element before
    root^.next := NewNext;
  end; 
end;  

procedure DeleteList(var root:tpsList);
var
  tmpList : tpsList;
begin
  while root <> nil do
  begin
    tmpList := root^.next;
    dispose(root);
    root := tmpList;
  end;
end;    

begin
 root := InitLList(100);
 OutList(root);
 writeln('Reverse 3 times');
 RevList(root);OutList(root); 
 RevList(root);OutList(root); 
 RevList(root);OutList(root); 
 DeleteList(root);
 OutList(root); 
end.

Output:

Big fjords vex quick waltz nymph 
Reverse 3 times
nymph waltz quick vex fjords Big 
Big fjords vex quick waltz nymph 
nymph waltz quick vex fjords Big 

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