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
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 list in its standard library. The destructive version is called nreverse, and the version that makes a reversed copy of the list is called reverse. However, it's simple to make your own versions of these functions.
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)))
Delphi
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
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
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
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
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