Singly-linked list/Reversal: Difference between revisions
Added FreeBASIC
(Added FreeBASIC) |
|||
| (6 intermediate revisions by 4 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 229 ⟶ 312:
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 517 ⟶ 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 530 ⟶ 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 547 ⟶ 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
| |||