Singly-linked list/Reversal: Difference between revisions
Added FreeBASIC
(→{{header|ALGOL 68}}: typos) |
(Added FreeBASIC) |
||
| (23 intermediate revisions by 11 users not shown) | |||
Line 9:
Using the code from the [[Singly-linked list/Traversal#ALGOL_68]] Task
<br>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).
<br>The use of LOC in the outermost level
<syntaxhighlight lang="algol68">
BEGIN
MODE STRINGLIST = STRUCT(STRING value, REF STRINGLIST next);
# construct a STRINGLIST with a few
STRINGLIST list := ("Big",
LOC STRINGLIST := ("fjords",
Line 45:
Big fjords vex quick waltz nymph
nymph waltz quick vex fjords Big
</pre>
=={{header|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.
<syntaxhighlight lang="C">
#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;
}
</syntaxhighlight>
=={{header|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:
<syntaxhighlight lang="Lisp">
(defun my-reverse (list)
(let ((result nil))
(dolist (obj list)
(push obj result))
result))
</syntaxhighlight>
A non-destructive reversal using reduce:
<syntaxhighlight lang="Lisp">
(defun my-reverse (list)
(reduce #'(lambda (acc x)
(cons x acc))
list
:initial-value NIL))
</syntaxhighlight>
A destructive reversal using tail-recursion. It returns the new beginning of the reversed list, or the empty list when passed the empty list.
<syntaxhighlight lang="Lisp">
(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)))
</syntaxhighlight>
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.
<syntaxhighlight lang="Lisp">
(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)))
</syntaxhighlight>
<syntaxhighlight lang="Lisp">
(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)))
</syntaxhighlight>
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|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.
<syntaxhighlight lang="Delphi">
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.
</syntaxhighlight>
{{out}}
<pre>
Big fjords vex quick waltz nymph
nymph waltz quick vex fjords Big
</pre>
=={{header|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:
<syntaxhighlight lang=J>
car=: 0{::]
cdr=: 1{::]
list2linkedlist=: ]`(car;<@$:@}.)@.(*@#)
reverselinkedlist=: '' {{x [`((car;<@[) $: cdr)@.(*@#@]) y }} ]</syntaxhighlight>
Example use:
<syntaxhighlight lang=J> list2linkedlist i.6
┌─┬────────────────────┐
│0│┌─┬────────────────┐│
│ ││1│┌─┬────────────┐││
│ ││ ││2│┌─┬────────┐│││
│ ││ ││ ││3│┌─┬────┐││││
│ ││ ││ ││ ││4│┌─┬┐│││││
│ ││ ││ ││ ││ ││5│││││││
│ ││ ││ ││ ││ │└─┴┘│││││
│ ││ ││ ││ │└─┴────┘││││
│ ││ ││ │└─┴────────┘│││
│ ││ │└─┴────────────┘││
│ │└─┴────────────────┘│
└─┴────────────────────┘
reverselinkedlist list2linkedlist i.6
┌─┬────────────────────┐
│5│┌─┬────────────────┐│
│ ││4│┌─┬────────────┐││
│ ││ ││3│┌─┬────────┐│││
│ ││ ││ ││2│┌─┬────┐││││
│ ││ ││ ││ ││1│┌─┬┐│││││
│ ││ ││ ││ ││ ││0│││││││
│ ││ ││ ││ ││ │└─┴┘│││││
│ ││ ││ ││ │└─┴────┘││││
│ ││ ││ │└─┴────────┘│││
│ ││ │└─┴────────────┘││
│ │└─┴────────────────┘│
└─┴────────────────────┘
</syntaxhighlight>
=={{header|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]].
<syntaxhighlight lang="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
</syntaxhighlight>
{{output}}
<pre>
2
1
</pre>
=={{header|FreeBASIC}}==
<syntaxhighlight lang="vbnet">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</syntaxhighlight>
{{out}}
<pre>Big fjords vex quick waltz nymph
nymph waltz quick vex fjords Big</pre>
=={{header|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.
<syntaxhighlight lang="julia">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
</syntaxhighlight>{{out}}
<pre>
llist = list(1, 2, 3, 4, 5)
revlist = list(5, 4, 3, 2, 1)
</pre>
=={{header|Nim}}==
We duplicate here the code from [[Singly-linked list/Element definition#Nim]] and add a procedure “reversed” to reverse a list.
<syntaxhighlight lang="Nim">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)
</syntaxhighlight>
{{out}}
<pre>List: 1 → 2 → 3 → 4 → 5
Reversed list: 5 → 4 → 3 → 2 → 1
</pre>
=={{header|Pascal}}==
==={{header|Free Pascal}}===
Reverting list by reverting the pointers.
<syntaxhighlight lang="pascal">
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.</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|Phix}}==
Up to show() same as [[Singly-linked_list/Traversal#Phix]], though I have just changed the terminator to NULL (on both).
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">enum</span> <span style="color: #000000;">NEXT</span><span style="color: #0000FF;">,</span><span style="color: #000000;">DATA</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">empty_sll</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #004600;">NULL</span><span style="color: #0000FF;">}}</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">sll</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">empty_sll</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">insert_after</span><span style="color: #0000FF;">(</span><span style="color: #004080;">object</span> <span style="color: #000000;">data</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">pos</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sll</span><span style="color: #0000FF;">))</span>
<span style="color: #000000;">sll</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sll</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">sll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pos</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">],</span><span style="color: #000000;">data</span><span style="color: #0000FF;">})</span>
<span style="color: #000000;">sll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pos</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sll</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">insert_after</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"ONE"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">insert_after</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"TWO"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">insert_after</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"THREE"</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">sll</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">show</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">idx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">sll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">idx</span><span style="color: #0000FF;">!=</span><span style="color: #004600;">NULL</span> <span style="color: #008080;">do</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">sll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">][</span><span style="color: #000000;">DATA</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">idx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">sll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">show</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">invert</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">prev</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">NULL</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">next</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">idx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">sll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">idx</span><span style="color: #0000FF;">!=</span><span style="color: #004600;">NULL</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">next</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">sll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">sll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">prev</span>
<span style="color: #000000;">prev</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">idx</span>
<span style="color: #000000;">idx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">next</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #000000;">sll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">prev</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">invert</span><span style="color: #0000FF;">()</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">sll</span>
<span style="color: #000000;">show</span><span style="color: #0000FF;">()</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
{{2},{3,"ONE"},{4,"TWO"},{0,"THREE"}}
"ONE"
"TWO"
"THREE"
{{4},{0,"ONE"},{2,"TWO"},{3,"THREE"}}
"THREE"
"TWO"
"ONE"
</pre>
=={{header|Raku}}==
Extending code from the [[Singly-linked_list/Element_definition#Raku]] Task
<syntaxhighlight lang="raku" line># 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;</syntaxhighlight>
{{out}}
<pre>40 30 20 10
10 20 30 40</pre>
You may [https://ato.pxeger.com/run?1=fVI9T8MwEJUY-ytuyBBLISofA2rE1J0Fid0klyaqcZHtNKAqv4SlA_wpfg13tpMGUTHl4nvv2e_efXwaue2Ox6_O1Zd33xdPpZLWwhqVggM00kKa5HupOswgyTW-OQGtBdMXiwUAvKBrdhUY3KOxCAc-4-N3oqnWOiK9UlPAPVhUdQYPrSoiqG9aheBheYV1q7GaBIJGwvcRNWD4pzj1T4eM4FtmzT-3p14rCywRgUP8GnSd0TORYW5uQ4y5s6Tk4QRDxW-FFDbSNWhGb4w8583J7dj1swWpK-LpSTv05o4HEPmjM-F19D7bPUO505zPGE-cBY1YUHbroNCnqxGwSkJ-xGYbPAmCe5GrZQapr66n6maqbpc-OCEEpW7liRsyiOkX_7TCesUtG7ftBw Attempt This Online!]
=={{header|Wren}}==
{{libheader|Wren-llist}}
{{libheader|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.
<syntaxhighlight lang="wren">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()</syntaxhighlight>
{{out}}
<pre>
Big fjords vex quick waltz nymph
nymph waltz quick vex fjords Big
nymph waltz quick vex fjords Big
nymph waltz quick vex fjords Big
</pre>
=={{header|XPL0}}==
{{works with|xpl0|0.0}}
{{libheader|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.
<syntaxhighlight lang="xpl0">
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;
</syntaxhighlight>
{{out}}
<pre>
Big fjords vex quick waltz nymph
nymph waltz quick vex fjords Big
</pre>
| |||