Singly-linked list/Reversal: Difference between revisions
Added FreeBASIC
(Added FreeBASIC) |
|||
| (10 intermediate revisions by 7 users not shown) | |||
Line 47:
</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}}==
Line 195 ⟶ 278:
└─┴────────────────────┘
</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}}==
Line 263 ⟶ 431:
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>
Line 418 ⟶ 651:
"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}}==
Line 431 ⟶ 699:
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="
import "./iterate" for Reversed
Line 448 ⟶ 716:
// 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
Line 470 ⟶ 738:
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>
| |||