Singly-linked list/Reversal

From Rosetta Code
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

C

This code works by reversing the pointers in the list. The function returns the new beginning of the list, or NULL if passed a null pointer.

 #include <stdlib.h>
 
 struct node {
     struct node *next;
     int data;
 };
 
 struct node *
 reverse(struct node *head) {
     struct node *prev, *cur, *next;
     prev = NULL;
     for (cur = head; cur != NULL; cur = next) {
         next = cur->next;
         cur->next = prev;
         prev = cur;
     }
     return prev;
 }

Common Lisp

Common Lisp has functions for reversing a sequences in its standard library, which includes, but is not limited to, linked list reversal. The destructive version is called nreverse, and the version that makes a reversed copy is called reverse. However, it's simple to make your own versions of these functions. Here is a simplified version that only reverses lists:

A non-destructive reversal using dolist:

(defun my-reverse (list)
  (let ((result nil))
    (dolist (obj list)
      (push obj result))
    result))

A non-destructive reversal using reduce:

(defun my-reverse (list)
  (reduce #'(lambda (acc x)
              (cons x acc))
          list
          :initial-value NIL))

A destructive reversal using tail-recursion. It returns the new beginning of the reversed list, or the empty list when passed the empty list.

(defun my-nreverse (list)
  (labels ((iter (prev cur)
             (if (endp cur)
                 prev
                 (let ((next (cdr cur)))
                   (setf (cdr cur) prev)
                   (iter cur next)))))
    (iter nil list)))

Two versions using explicit iteration. They both do exactly the same thing, just one uses the DO macro and the other uses the LOOP macro.

(defun my-nreverse (list)
  ;; (cdr nil) is nil in Common Lisp, so (cdr list) is always safe.
  (do ((next (cdr list) (cdr next))
       (cur list next)
       (prev nil cur))
      ((endp cur) prev)
    (setf (cdr cur) prev)))
(defun my-nreverse (list)
  (loop for next = (cdr list) then (cdr next)
        and cur = list then next
        and prev = nil then cur
        until (endp cur)
        do (setf (cdr cur) prev)
        finally (return prev)))

Here is a slightly shorter way to define a destructive linked list reversal function without relying on tail recursion or the fact that (cdr nil) is nil (assuming the argument is proper without checking):

(defun my-nvreverse (list)
  (loop with prev = nil
        until (null list)
        do (rotatef (cdr list) prev list)
        finally (return prev)))

Delphi

Works with: Delphi version 6.0
Library: StdCtrls

This version uses standard Delphi concepts of block structure, passing objects, and avoiding pointers where possible. So, for example, here, the problem is broken down into a set of simple subroutines that take list-objects as arguments. While the code is slightly larger than inline examples, there are big payoffs for small increments in size. For example, the subroutines can be used independently on any linked-list. In this way, they could be used as the basis for a link-list library or linked-list object. Code-reuse is a fundamental tool for simplifying programing tasks and decreasing errors. So, in Delphi, even when you are writing simple code, the language encourages you to make it modular which makes it easy to reuse and easy to incorporate into libraries.

unit ReverseList;

interface

uses StdCtrls;

procedure LinkListTest(Memo: TMemo);

implementation

{}

const TestData: array [0..5] of string = ('Big','fjords','vex','quick','waltz','nymph');

{Structure contains one list item}

type TLinkItem = record
 Name: string;
 Link: integer;
 end;

{Define a dynamic array, linked list type}

type TLinkedList = array of TLinkItem;

{Define actual working linked-list}

var LinkedList: TLinkedList;


procedure AddItem(var LL: TLinkedList; S: string);
{Insert one string in the specified Linked List}
var Inx: integer;
begin
SetLength(LL,Length(LL)+1);
Inx:=High(LL);
LL[Inx].Name:=S;
LL[Inx].Link:=-1;
{if not first entry, link to previous entry}
if Inx>0 then LL[Inx-1].Link:=Inx;
end;



function GetReversedList(LL: TLinkedList): TLinkedList;
{Return the reverse of the input list}
var I,Next: integer;
var SA: array of string;
begin
SetLength(SA,Length(LL));
{Get names in linked order}
Next:=0;
for I:=0 to High(LL) do
	begin
	SA[I]:=LL[Next].Name;
	Next:=LL[Next].Link;
	end;
{Insert them in Linked List in reverse order}
for I:=High(SA) downto 0 do AddItem(Result,SA[I]);
end;


function ListToStr(LL: TLinkedList): string;
{Return list as string for printing or display}
var I,Next: integer;
begin
Result:='';
Next:=0;
for I:=0 to High(LL) do
	begin
	Result:=Result+LL[Next].Name+' ';
	Next:=LL[Next].Link;
	end;
end;


procedure LinkListTest(Memo: TMemo);
{Routine to test the code}
{returns output string in memo}
var I: integer;
var S: string;
var LL: TLinkedList;
begin
Memo.Clear;
for I:=0 to High(TestData) do AddItem(LinkedList,TestData[I]);
Memo.Lines.Add(ListToStr(LinkedList));
LL:=GetReversedList(LinkedList);
Memo.Lines.Add(ListToStr(LL));
end;

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 modern 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│││││││
 ││ ││ ││ ││ │└─┴┘│││││
 ││ ││ ││ │└─┴────┘││││
 ││ ││ │└─┴────────┘│││
 ││ │└─┴────────────┘││
 │└─┴────────────────┘│
└─┴────────────────────┘

jq

Works with: jq

Also works with gojq, the Go implementation of jq

For context and definitions of the basic SLL functions, see Singly-linked_list/Element_definition#jq.

include "rc-singly-linked-list" {search: "."}; # see [[Singly-linked_list/Element_definition#jq]]

# Convert the SLL to a stream of its values:
def items: while(has("item"); .next) | .item;

# Convert an array (possibly empty) into a SLL
def SLL:
  . as $in
  | reduce range(length-1; -1; -1) as $j ({next: null};
      insert($in[$j]) );

# Output an array
def reverse(stream):
  reduce stream as $x ([]; [$x] + .);

def reverse_singly_linked_list:
  reverse(items) | SLL;

def example: [1,2] | SLL;

example | reverse_singly_linked_list | items
Output:
2
1

FreeBASIC

Dim Shared As Integer ListLinks(5), DataInx
Dim Shared As String ListNames(5)

Sub AddItem(S As String)
    ListNames(DataInx) = S
    ListLinks(DataInx) = -1
    If DataInx > 0 Then ListLinks(DataInx - 1) = DataInx
    DataInx += 1
End Sub

Sub GetReversedList
    Dim As Integer i, sgte, cnt
    Dim SA(5) As String
    
    cnt = DataInx
    DataInx = 0
    sgte = 0
    For i = 0 To cnt - 1
        SA(i) = ListNames(sgte)
        sgte = ListLinks(sgte)
    Next i
    For i = cnt - 1 To 0 Step -1
        AddItem(SA(i))
    Next i
End Sub

Sub DisplayList
    Dim As Integer i, sgte
    
    sgte = 0
    For i = 0 To DataInx - 1
        Print ListNames(sgte); " ";
        sgte = ListLinks(sgte)
    Next i
    Print
End Sub

Dim As String TestData(5) = {"Big", "fjords", "vex", "quick", "waltz", "nymph"}
For i As Integer = 0 To 5
    AddItem(TestData(i))
Next i
DisplayList
GetReversedList
DisplayList

Sleep
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)

Nim

We duplicate here the code from Singly-linked list/Element definition#Nim and add a procedure “reversed” to reverse a list.

import strutils

type

  Node[T] = ref object
    next: Node[T]
    data: T

  SinglyLinkedList[T] = object
    head, tail: Node[T]

proc newNode[T](data: T): Node[T] =
  Node[T](data: data)

proc append[T](list: var SinglyLinkedList[T]; node: Node[T]) =
  if list.head.isNil:
    list.head = node
    list.tail = node
  else:
    list.tail.next = node
    list.tail = node

proc append[T](list: var SinglyLinkedList[T]; data: T) =
  list.append newNode(data)

proc prepend[T](list: var SinglyLinkedList[T]; node: Node[T]) =
  if list.head.isNil:
    list.head = node
    list.tail = node
  else:
    node.next = list.head
    list.head = node

proc prepend[T](list: var SinglyLinkedList[T]; data: T) =
  list.prepend newNode(data)

proc `$`[T](list: SinglyLinkedList[T]): string =
  var s: seq[T]
  var n = list.head
  while not n.isNil:
    s.add n.data
    n = n.next
  result = s.join(" → ")

proc reversed[T](list: SinglyLinkedList[T]): SinglyLinkedList[T] =
  var node = list.head
  while node != nil:
    result.prepend node.data
    node = node.next

var list: SinglyLinkedList[int]
for i in 1..5: list.append(i)

echo "List: ", list
echo "Reversed list: ", reversed(list)
let revList = reversed(list)
Output:
List: 1 → 2 → 3 → 4 → 5
Reversed 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 

Perl

Translation of: Raku
# 20240913 Perl programming solution

use strict;
use warnings;

my %node3 = ( data => 'Node 3', next => undef );
my %node2 = ( data => 'Node 2', next => \%node3 );
my %node1 = ( data => 'Node 1', next => \%node2 );
my $head  = \%node1;

sub print_list {
   my ($head_ref) = @_;
   my $current = $head_ref;
   while ($current) {
      print $current->{data}, " -> ";
      $current = $current->{next};
   }
   print "undef\n";
}

sub reverse_list {
   my ($head_ref) = @_;
   my ($prev, $current, $next) = (undef, $$head_ref);
   while ($current) {
      $next = $current->{next};
      $current->{next} = $prev;
      ($prev, $current) = ($current, $next);
   }
   $$head_ref = $prev;
}

print "Original list:\n";
print_list($head);
reverse_list(\$head);
print "\nList after reversal:\n";
print_list($head);

You may Attempt This Online!

Phix

Up to show() same as Singly-linked_list/Traversal#Phix, though I have just changed the terminator to NULL (on both).

with javascript_semantics
enum NEXT,DATA
constant empty_sll = {{NULL}}
sequence sll = deep_copy(empty_sll)
 
procedure insert_after(object data, integer pos=length(sll))
    sll = append(sll,{sll[pos][NEXT],data})
    sll[pos][NEXT] = length(sll)
end procedure
 
insert_after("ONE")
insert_after("TWO")
insert_after("THREE")
 
?sll
 
procedure show()
    integer idx = sll[1][NEXT]
    while idx!=NULL do
        ?sll[idx][DATA]
        idx = sll[idx][NEXT]
    end while
end procedure
show()

procedure invert()
    integer prev = NULL, next,
            idx = sll[1][NEXT]
    while idx!=NULL do
        next = sll[idx][NEXT]
        sll[idx][NEXT] = prev
        prev = idx
        idx = next
    end while
    sll[1][NEXT] = prev
end procedure

invert()
?sll
show()
Output:
{{2},{3,"ONE"},{4,"TWO"},{0,"THREE"}}
"ONE"
"TWO"
"THREE"
{{4},{0,"ONE"},{2,"TWO"},{3,"THREE"}}
"THREE"
"TWO"
"ONE"

Raku

Extending code from the Singly-linked_list/Element_definition#Raku Task

# 20240220 Raku programming solution

class Cell { has ($.value, $.next) is rw;

   method reverse {
      my ($list, $prev) = self, Nil;
      while $list.defined {
         my $next = $list.next;
         $list.next = $prev;
         ($list, $prev) = ($next, $list)
      }
      return $prev;
   }

   method gist {
      my $cell = self;
      return ( gather while $cell.defined {
         take $cell.value andthen $cell = $cell.next;
      } ).Str
   }
}

sub cons ($value, $next = Nil) { Cell.new(:$value, :$next) }

my $list = cons 10, (cons 20, (cons 30, (cons 40, Nil)));

say $list = $list.reverse;
say $list = $list.reverse;
Output:
40 30 20 10
10 20 30 40

You may Attempt This Online!

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("\n")

// 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 

XPL0

Works with: xpl0 version 0.0
Library: EXPLCodes.xpl

To avoid the use of pointers, the linked list is contained in two arrays; one for the name and one for the link. The code is broken down into a set of subroutines to handle the tasks of inserting items in the list, displaying the list and reversing the list. Although this results in code that is a bit larger than doing everything inline, it makes the code more modular and easier to debug and maintain.

inc	C:\CXPL\EXPLCodes.xpl;	\intrinsic declarations

\Program to reverse a Singly-linked list

int TestData;
int I;

\Array for use in Linked list. 

int ListNames;
int ListLinks;
int DataInx;


proc AddItem(S);
\Insert one string in the specified Linked List
char S;
begin
ListNames(DataInx):=S;
ListLinks(DataInx):=-1;
\if not first entry, link to previous entry
if DataInx>0 then ListLinks(DataInx-1):=DataInx;
DataInx:=DataInx+1;
end;



proc GetReversedList;
\Return the reverse of the input list
int I,Next,Cnt;
int SA;
begin
Cnt:=DataInx;
DataInx:=0;
SA:=Reserve(Cnt * sizeof(int));
\Get names in linked order
Next:=0;
for I:=0 to Cnt-1 do
	begin
	SA(I):=ListNames(Next);
	Next:=ListLinks(Next);
	end;
\Insert them in Linked List in reverse order
for I:=Cnt-1 downto 0 do AddItem(SA(I));
end;


proc DisplayList;
\Display all items in linked list
int I,Next;
begin
Next:=0;
for I:=0 to DataInx-1 do
	begin
	Text(0,ListNames(Next));
	Text(0," ");
	Next:=ListLinks(Next);
	end;
CRLF(0);
end;


begin
TestData:=["Big","fjords","vex","quick","waltz","nymph"];
ListNames:=Reserve(6 * sizeof(int));
ListLinks:=Reserve(6 * sizeof(int));
for I:=0 to 5 do AddItem(TestData(I));
DisplayList;
GetReversedList;
DisplayList;
end;
Output:
Big fjords vex quick waltz nymph 
nymph waltz quick vex fjords Big