Singly-linked list/Traversal: Difference between revisions
m
→{{header|Wren}}: Minor tidy
m (→{{header|Wren}}: Minor tidy) |
|||
(9 intermediate revisions by 7 users not shown) | |||
Line 7:
{{Template:See also lists}}
<br><br>
=={{header|6502 Assembly}}==
These implementations use the zero page to hold the linked list nodes. The equivalent implementation for any arbitrary address will be left as an exercise to the reader.
===Using self-modifying code===
In this example, we'll create three nodes, and read the value of the last node. You can copy and paste this code into easy6502 and run it there. Note that the debugger shows that the value in the accumulator is $25, just as expected.
Self-modifying code is an efficient way to perform this task. Unfortunately, easy6502 does not support <code>ORG</code> directives or compile-time pointer arithmetic, so the easiest way to do this was to place a jump to the main program at the beginning and put the self-modifying section between the jump and the main program. (Easy6502's memory layout starts execution at $0600 so it was a simple matter of knowing that <code>JMP</code> takes three bytes and <code>LDA</code> takes two.)
The program will look up the pointer to the next node, modify the operand of the traverse function with that address, and repeat until a null pointer ($00) is read. Then it uses the same traverse function to fetch the value.
<syntaxhighlight lang="6502asm">define nullptr 0
jmp main
traverse:
;change the $00 to anything you want
;by writing the desired value to $0604
LDA $00,X
rts
main:
;create three nodes
; node 0 = #$23 stored at $0003
; node 1 = #$24 stored at $0013
; node 2 = #$25 stored at $0033
LDA #$03
STA $0604
;alter our code to have the starting address.
;create the linked list.
LDA #$23
STA $03
LDA #$13
STA $04
LDA #$24
STA $13
LDA #$33
STA $14
LDA #$25
STA $33
LDA #nullptr
STA $34
;traverse to last element and load it into A.
LDX #1
loop_traverse:
jsr traverse
;CMP #nullptr ;LDA implicitly compares to zero.
BEQ done ;if equal to nullptr, exit.
STA $0604
jmp loop_traverse
done:
dex
jsr traverse ;get the value of the last element.
brk</syntaxhighlight>
===Without self-modifying code===
This is mostly the same, except it uses the <code>($nn),y</code> addressing mode which is a bit slower, but can be executed on ROM cartridges no problem.
<syntaxhighlight lang="6502asm">define nullptr 0
define tempptr $fc
main:
;create three nodes
; node 0 = #$23 stored at $0003
; node 1 = #$24 stored at $0013
; node 2 = #$25 stored at $0033
;create the linked list.
LDA #$03
STA $FC ;store the pointer to node 0.
LDA #$00
STA $FD ;if you're using the zero page to hold your linked list entries, you need to make the high byte zero.
LDA #$23
STA $03
LDA #$13
STA $04
LDA #$24
STA $13
LDA #$33
STA $14
LDA #$25
STA $33
LDA #nullptr
STA $34
LDY #1
loop:
jsr traverse
BEQ done
STA $FC
BNE loop ;branch always
done:
DEY
JSR traverse
brk
traverse:
LDA ($FC),Y
rts</syntaxhighlight>
=={{header|AArch64 Assembly}}==
{{works with|as|Raspberry Pi 3B version Buster 64 bits}}
<syntaxhighlight lang="aarch64 assembly">
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program afficheList64.s */
Line 130 ⟶ 235:
.include "../includeARM64.inc"
</syntaxhighlight>
=={{header|ACL2}}==
The standard list data type is a singly linked list.
<
(if (endp xs)
(cw "End.~%")
(prog2$ (cw "~x0~%" (first xs))
(traverse (rest xs)))))</
=={{header|Action!}}==
The user must type in the monitor the following command after compilation and before running the program!<pre>SET EndProg=*</pre>
{{libheader|Action! Tool Kit}}
<
INCLUDE "D2:ALLOCATE.ACT" ;from the Action! Tool Kit. You must type 'SET EndProg=*' from the monitor after compiling, but before running this program!
Line 224 ⟶ 329:
Clear()
RETURN</
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Singly-linked_list_traversal.png Screenshot from Atari 8-bit computer]
Line 234 ⟶ 339:
=={{header|ActionScript}}==
See [[Singly-Linked List (element)#ActionScript|Singly-Linked List (element) in ActionScript]]
<
//...
for(var i:Node = A; i != null; i = i.link)
{
doStuff(i);
}</
=={{header|Ada}}==
The Ada standard container library provides a doubly-linked list. List traversal is demonstrated for the forward links.
<
with Ada.Text_Io; use Ada.Text_Io;
Line 261 ⟶ 366:
-- Traverse the list, calling Print for each value
The_List.Iterate(Print'access);
end traversal_example;</
=={{header|ALGOL 68}}==
Line 269 ⟶ 374:
Linked lists are not built into ALGOL 68 ''per se'', nor any available standard library. However Linked lists are presented in standard text
book examples. Or can be manually constructed, eg:
<
STRINGLIST list := ("Big",
Line 283 ⟶ 388:
node := next OF node
OD;
print(newline)</
{{out}}
<pre>
Line 290 ⟶ 395:
=={{header|ALGOL W}}==
<
% record type to hold a singly linked list of integers %
record ListI ( integer iValue; reference(ListI) next );
Line 317 ⟶ 422:
end;
end.</
{{out}}
<pre>
Line 329 ⟶ 434:
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<syntaxhighlight lang="arm assembly">
/* ARM assembly Raspberry PI */
/* program afficheList.s */
Line 509 ⟶ 614:
bx lr @ leave function
iMagicNumber: .int 0xCCCCCCCD
</syntaxhighlight>
=={{header|ATS}}==
Line 521 ⟶ 626:
The traversal function is proven to terminate.
<
(* The Rosetta Code linear list type can contain any vt@ype.
Line 605 ⟶ 710:
implement
main0 () = ()</
{{out}}
Line 614 ⟶ 719:
=={{header|AutoHotkey}}==
<syntaxhighlight lang="autohotkey">a = 1
a_next = b
b = 2
Line 633 ⟶ 738:
name := %name% . "_next"
}
}</
=={{header|Axe}}==
<
LINK(L₁+10,2)→B
LINK(L₁+50,3)→C
Line 647 ⟶ 752:
Disp VALUE(I)▶Dec,i
NEXT(I)→I
End</
=={{header|
==={{header|BBC BASIC}}===
{{works with|BBC BASIC for Windows}}
<
DIM a{} = node{}, b{} = node{}, c{} = node{}
Line 675 ⟶ 781:
here.pNext% = new{}
ENDPROC
</syntaxhighlight>
{{out}}
<pre>Traverse list:
Line 684 ⟶ 790:
=={{header|C}}==
See [[Singly-Linked List (element)#C|Singly-Linked List (element) in C]].
<
// ...
struct link *iter;
for(iter = first; iter != NULL; iter = iter->next) {
// access data, e.g. with iter->data
}</
=={{header|C sharp|C#}}==
Uses the generic version of the node type located [[Singly-linked_list/Element_definition#C#|here]].
<
while(current != null)
{
Line 700 ⟶ 806:
current = current.Next;
}</
Alternatively, as a for loop:
<
{
// Do something with current.Value.
}</
=={{header|C++}}==
Line 712 ⟶ 818:
{{works with|C++11}}
For each traversal version.
<
#include <forward_list>
Line 720 ⟶ 826:
for (int e : list)
std::cout << e << std::endl;
}</
=={{header|Clojure}}==
<
=={{header|Common Lisp}}==
<
(print x))</
Using LOOP:
<
Using MAPC
<syntaxhighlight lang
Using MAP
<
Not using builtin list iteration:
<
until (null ref)
do (print (first ref)))</
=={{header|Computer/zero Assembly}}==
A linked list can be implemented as a chain of CONS cells, where each cell is made up of two neighbouring memory locations: the CAR, storing an item of data, and the CDR, storing the address of the next cell in the list. The CDR of the last cell contains not an address but a special <tt>NIL</tt> value that is guaranteed not to be a valid address; in this implementation, we use 0 to represent <tt>NIL</tt>. The order of CONS cells in memory is of course entirely unimportant. For the sake of example, this program traverses the list <tt>'(1 2 3 4 5 6)</tt> and halts with the final value in the accumulator. The program is reasonably straightforward, but it does make some use of instruction arithmetic (self-modifying code).
<
ADD car ; head of list
STA ldcar
Line 779 ⟶ 885:
26,27: 3, 30
28,29: 1, 22
30,31: 4, 24</
=={{header|D}}==
<
T data;
typeof(this)* next;
Line 796 ⟶ 902:
write(p.data, " ");
writeln();
}</
{{out}}
<pre>1 2 3 4 </pre>
===Alternative Version===
Using tango's collections (written by Doug Lea, ported to D):
<
import tango.util.collection.LinkSeq;
Line 811 ⟶ 917:
foreach (val; m)
Stdout(val).newline;
}</
=={{header|Delphi}}==
<
type
Line 835 ⟶ 941:
while not (pList^.Next = NIL) do pList := pList^.Next ;
end;</
=={{header|Dyalect}}==
Line 841 ⟶ 947:
Dyalect doesn't support linked lists out of the box, but it is fairly simple to implement one:
<
with Lookup
Line 875 ⟶ 981:
for x in xs {
print(x)
}</
It is also possible to provide an ad hoc solution to the problem:
Line 881 ⟶ 987:
{{trans|E}}
<
while xs is (value, tail) {
print(value)
xs = tail
}</
Here a linked list is emulated using tuples.
Line 892 ⟶ 998:
=={{header|E}}==
Using a list made from tuples:
<
while (linkedList =~ [value, next]) {
println(value)
linkedList := next
}</
Using a list made from the structure defined at [[Singly-Linked List (element)#E|Singly-Linked List (element)]]:
<
while (!(linkedList.null())) {
println(linkedList.value())
linkedList := linkedList.next()
}</
=={{header|EchoLisp}}==
Lists - linked-lists - are '''the''' fundamental data type in EchoLisp. A lot of fuctions exist to scan lists or operate on successive elements.
<
(define friends '( albert ludwig elvis 🌀))
Line 935 ⟶ 1,041:
(foldl + 0 L) → 500500 ; 1000 * 1001 / 2
</syntaxhighlight>
=={{header|Ela}}==
<
traverse (x::xs) = x :: traverse xs</
This function traverses a list and constructs a new list at the same time. For a list in Ela it is the same as identity function, e.g. traverse [1,2,3] == [1,2,3]. However it can be useful in some cases. For example, to enforce a lazy list:
<
traverse xs</
=={{header|Elena}}==
Simple iteration with a while loop.
<
while(nil != current){
console printLine(current.Item);
current := current.Next
}</
=={{header|Erlang}}==
Line 965 ⟶ 1,071:
=={{header|Factor}}==
<
[ [ data>> ] dip call ]
[ [ next>> ] dip over [ list-each ] [ 2drop ] if ] 2bi ; inline recursive
Line 975 ⟶ 1,081:
[ B <linked-list> list-insert ] keep
[ . ] list-each</
{{out}}
<pre>
Line 985 ⟶ 1,091:
=={{header|Fantom}}==
Using the definitions from [[Singly-Linked_List_(element_insertion)]]:
<
Node? current := a
while (current != null)
Line 991 ⟶ 1,097:
echo (current.value)
current = current.successor
}</
=={{header|Forth}}==
<
begin dup @ while @ repeat ;</
And here is a function to walk a list, calling an XT on each data cell:
<
>r begin ?dup while
dup cell+ @ r@ execute
@ repeat r> drop ;</
Testing code:
Line 1,007 ⟶ 1,113:
=={{header|Fortran}}==
Fortran 95. See [[Singly-Linked List (element)#Fortran|Singly-Linked List (element) in Fortran]].
<
type(node), target :: list
type(node), pointer :: current
Line 1,020 ⟶ 1,126:
current => current%next
end do
end subroutine traversal</
Print data from all nodes of a singly-linked list:
<
real, intent(in) :: data
write (*,*) data
Line 1,030 ⟶ 1,136:
type(node), intent(in) :: list
call traversal(list,printNode)
end subroutine printAll</
=={{header|FreeBASIC}}==
Requires the type definition and node insertion routine [[Singly-linked_list/Element_definition#FreeBASIC|here]] and [[Singly-linked_list/Element_insertion#FreeBASIC|here]] respectively. Also includes a routine for allocating space for a node.
<
function alloc_ll_int( n as integer ) as ll_int ptr
Line 1,062 ⟶ 1,168:
next i
traverse_ll_int( head )</
=={{header|Go}}==
See [[Singly-Linked List (element)#Go|Singly-Linked List (element) in Go]].
<
end := start.Append("burritos")
end = end.Append("fajitas")
Line 1,072 ⟶ 1,178:
for iter := start; iter != nil; iter = iter.Next {
fmt.Println(iter)
}</
=={{header|Haskell}}==
Lists are ubiquitous in Haskell, simply use Haskell's <em>map</em> library function:
<
map (++ "s") ["Apple", "Orange", "Mango", "Pear"] -- ["Apples","Oranges","Mangos","Pears"]
Line 1,084 ⟶ 1,190:
traverse :: [a] -> [a]
traverse list = map func list
where func a = -- ...do something with a</
Note that the <em>traverse</em> function is polymorphic; denoted by <em>traverse :: [a] -> [a]</em> where <em>a</em> can be of any type.
Line 1,090 ⟶ 1,196:
=={{header|Icon}} and {{header|Unicon}}==
Using either the record or class-based definitions from [[Singly-Linked List (element)#Icon_and_Unicon|Singly-Linked List (element) in Icon and Unicon]]:
<
ns := Node(1, Node(2, Node (3)))
until /ns do { # repeat until ns is null
Line 1,096 ⟶ 1,202:
ns := ns.successor
}
end</
Prints the numbers 1, 2, 3 in turn.
=={{header|J}}==
Using the implementation mentioned at [[Singly-Linked List (element)#J|Singly-Linked List (element) in J]], we can apply a function <tt>foo</tt> to each node the following way:
<
=={{header|Java}}==
{{works with|Java|1.5+}}
For Java.util.LinkedList<T>, use a for each loop (from [[Loop Structures]]):
<
for(Type i: list){
//each element will be in variable "i"
System.out.println(i);
}</
Note that <code>java.util.LinkedList</code> can also perform as a stack, queue, or doubly-linked list.
=={{header|JavaScript}}==
Extending [[Singly-Linked_List_(element)#JavaScript]]
<
func(this);
if (this.next() != null)
Line 1,127 ⟶ 1,233:
var head = createLinkedListFromArray([10,20,30,40]);
head.print();</
Uses the <code>print()</code> function from [[Rhino]]
Line 1,133 ⟶ 1,239:
Alternatively, translating the [[#Haskell | Haskell]] examples in terms of JavaScript's Array.map, Array.reduce, and Array.forEach:
<
return list.map(fn);
},
Line 1,178 ⟶ 1,284:
/* Orange */
/* Mango */
/* Pear */</
=={{header|Joy}}==
<syntaxhighlight lang="joy">['a 'b 'c '\n] [putch] step.</syntaxhighlight>
=={{header|jq}}==
Line 1,187 ⟶ 1,296:
Here we define a "map" filter as well as a traversal filter. The "map" filter is similar to the built-in `map` in that it can be used to remove items as per the comment below.
<syntaxhighlight lang="jq">
# Produce a stream of the items in the input SLL.
def items:
Line 1,197 ⟶ 1,306:
# If f evaluates to empty at any item, that item is removed;
# if f evaluates to more than one item, all are added separately.
def map_singly_linked_list(f): to_singly_linked_list( items | f );</
'''Examples'''
<
"item": 1,
"next": {
Line 1,207 ⟶ 1,316:
}
| reduce items as $item (null; .+$item),
map_singly_linked_list(- .)</
{{out}}
<pre>
Line 1,224 ⟶ 1,333:
Julia let you implement list traversal very easily: see [[Singly-linked_list/Element_definition#Julia]] for the <tt>LinkedList</tt> struct definition.
<
Base.done(ll::LinkedList{T}, st::AbstractNode{T}) where T = st isa EmptyNode
Base.next(ll::LinkedList{T}, st::AbstractNode{T}) where T = st.data, st.next
Line 1,235 ⟶ 1,344:
for n in lst
print(n, " ")
end</
=={{header|Kotlin}}==
Lists in Kotlin may be instanciated from Java classes or from Kotlin methods or extensions.
<
val list = IntRange(1, 50).toList()
Line 1,247 ⟶ 1,356:
// list iterator:
list.asReversed().forEach { print("%4d ".format(it)); if (it % 10 == 1) println() }
}</
{{out}}
<pre> 1 2 3 4 5 6 7 8 9 10
Line 1,262 ⟶ 1,371:
=={{header|Limbo}}==
Lists are a built-in type in Limbo.
<
include "sys.m";
Line 1,281 ⟶ 1,390:
sys->print("%d\n", hd l);
# the unary 'hd' operator gets the head of a list
}</
=={{header|Logo}}==
LAST is already a Logo built-in, but it could be defined this way:
<
if empty? bf :list [output first :list]
output last bf :list
end</
=={{header|Logtalk}}==
The built-in list type can be viewed as a singly linked list.
Traversing can be trivially done using a tail-recursive predicate:
<
:- object(singly_linked_list).
Line 1,307 ⟶ 1,416:
:- end_object.
</syntaxhighlight>
{{out}}
<
| ?- singly_linked_list::show.
1
Line 1,315 ⟶ 1,424:
3
yes
</syntaxhighlight>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
{{out}}
<pre>rosettacode
Line 1,330 ⟶ 1,439:
Matlab and Octave do not have pointers.
Linked lists are implemented as vectors (i.e. arrays of size 1xN)
<
for k=1:length(list)
printf('%i\n',list(k))
end; </
It is recommended to avoid loops and "vectorize" the code:
<
=={{header|MiniScript}}==
We're choosing here to use the built-in list type, rather than make our own from scratch, since this is more representative of how one is likely to actually use MiniScript.
<
for i in myList
print i
end for</
{{out}}
<pre>
Line 1,356 ⟶ 1,465:
{{trans|C}}
See [[Singly-Linked List (element)#Nanoquery|Singly-Linked List (element) in Nanoquery]].
<
//
for (iter = first) (iter != null) (iter = iter.next)
println iter.data
end</
=={{header|NewLISP}}==
<
(println x))</
=={{header|Nim}}==
<
next: Node[T]
data: T
Line 1,392 ⟶ 1,501:
for item in a:
echo item.data</
=={{header|Objeck}}==
<
for(node := head; node <> Nil; node := node->GetNext();) {
node->GetValue()->PrintLine();
};
</syntaxhighlight>
=={{header|Objective-C}}==
(See [[Singly-Linked List (element)]])
<
for(current=first_of_the_list; current != nil; current = [current next] )
{
// to get the "datum":
// id dat_obj = [current datum];
}</
=={{header|OCaml}}==
<
List.iter print_endline li ;;
big
Line 1,419 ⟶ 1,528:
waltz
nymph
- : unit = ()</
=={{header|Odin}}==
<syntaxhighlight lang="odin">package main
import "core:fmt"
Node :: struct {
data: rune,
next: ^Node,
}
insert_after :: proc(node, new_node: ^Node) {
new_node.next = node.next
node.next = new_node
}
main :: proc() {
a := new(Node)
a.data = 'A'
b := new(Node)
b.data = 'B'
c := new(Node)
c.data = 'C'
insert_after(a, b) // A -> B
insert_after(a, c) // A -> C -> B
for n := a; n != nil; n = n.next {
fmt.print(n.data)
} // prints: ACB
}
</syntaxhighlight>
=={{header|Oforth}}==
Line 1,427 ⟶ 1,570:
Because forEachNext is defined, a linked list responds to all methods defined for Collections : apply, map, filter, ....
<
testLink apply(#println)</
{{out}}
Line 1,439 ⟶ 1,582:
=={{header|ooRexx}}==
See [[Singly-linked_list/Element_definition#ooRexx|Singly-Linked List/Element Definition in ooRexx]] for the full class definition.
<
say "Manual list traversal"
index=list~first
Line 1,451 ⟶ 1,594:
do value over list
say value
end</
{{out}}
<pre>Manual list traversal
Line 1,465 ⟶ 1,608:
=={{header|Pascal}}==
See [[Singly-linked_list/Traversal#Delphi
=={{header|Peloton}}==
This makes a list of the Chinese Public Holiday and lists them first till last and then last till first.
<
<@ OMT>From First to Last</@>
<@ ITEFORSZELSTLIT>public holidays|
Line 1,477 ⟶ 1,620:
<@ ITEFORSZELSTLIT>public holidays|
<@ SAYLST>...</@><@ ACTMOVBKWLST>...</@>
</@></
This variable length Simplified Chinese rendition of the same code is
<
<# 忽略>From First to Last</#>
<# 迭代迭代次数结构大小列表字串>public holidays|
Line 1,487 ⟶ 1,630:
<# 迭代迭代次数结构大小列表字串>public holidays|
<# 显示列表>...</#><# 运行移位指针向后列表>...</#>
</#></
=={{header|Perl}}==
We use Class::Tiny to get OO functionality with minimal effort.
<
use strict;
use Class::Tiny qw( val next );
Line 1,520 ⟶ 1,663:
$node = $node->next;
}
print "\n";</
{{out}}
<pre>10... 9... 8... 7... 6... 5... 4... 3... 2... 1...
Line 1,527 ⟶ 1,670:
=={{header|Phix}}==
See also [[Singly-linked_list/Element_removal#Phix|Removal]].
<!--<
<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: #
<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>
Line 1,545 ⟶ 1,688:
<span style="color: #008080;">procedure</span> <span style="color: #000000;">show</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: #
<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>
Line 1,552 ⟶ 1,695:
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">show</span><span style="color: #0000FF;">()</span>
<!--</
{{out}}
<pre>
{{2},{3,"ONE"},{4,"TWO"},{
"ONE"
"TWO"
Line 1,563 ⟶ 1,706:
=={{header|PicoLisp}}==
We might use map functions
<
or flow control functions
<
(println X) )</
{{out}} for both cases:
<pre>a
Line 1,574 ⟶ 1,717:
=={{header|PL/I}}==
<
/*********************************************************************
* 25.10.2013 Walter Pachl
Line 1,614 ⟶ 1,757:
p=p->next;
End;
End;</
{{out}}
<pre> 1 Walter
Line 1,622 ⟶ 1,765:
=={{header|PureBasic}}==
<
While *node
;access data, i.e. PrintN(Str(*node\Value))
Line 1,630 ⟶ 1,773:
;called using
traverse(*firstnode.MyData)</
=={{header|Python}}==
<
print node.value</
Any Python class can define ''next()'' and ''__iter__()'' methods so that it can be used with the normal ''for'' iteration syntax.
In this example the "lst" could be an instance of any Python list, tuple, dictionary, or any sort of object which defines an iterator.
It could also be a generator (a type of function which ''yields'' results upon each successive invocation).
The notion of a "singly linked list" is somewhat more primitive than normal Python built-in objects.
<
"""USELESS academic/classroom example of a linked list implemented in Python.
Don't ever consider using something this crude! Use the built-in list() type!
Line 1,661 ⟶ 1,804:
for value in lst:
print value,;
print</
{{out}}
<pre>
Line 1,671 ⟶ 1,814:
Since singly-linked lists that are made of <tt>cons</tt> cells are one of the most common primitive types in Racket, there is a lot of built-in functionality that scans these lists:
<syntaxhighlight lang="racket">
#lang racket
Line 1,701 ⟶ 1,844:
(mfor-each displayln ml)
(for ([x (in-mlist ml)]) (displayln x))
</syntaxhighlight>
=={{header|Raku}}==
Line 1,710 ⟶ 1,853:
but works at a higher abstraction level that encapsulates such implementation choices. Nonetheless, it's trivial to use the <tt>Pair</tt> type to build what is essentially a Lisp-style cons list, and in fact, the <tt>=></tt> pair constructor is right associative for precisely that reason.
We traverse such a list here using a 3-part loop:
<syntaxhighlight lang="raku"
loop (my $l = $list; $l; $l.=value) {
say $l.key;
}</
{{out}}
<pre>1
Line 1,730 ⟶ 1,873:
Note how the <tt>[=>]</tt> reduction is also right associative,
just like the base operator.)
<syntaxhighlight lang="raku"
augment class Pair {
method traverse () {
Line 1,740 ⟶ 1,883:
my $list = [=>] 'Ⅰ' .. 'Ⅻ', Mu;
say ~$list.traverse;</
{{out}}
Line 1,749 ⟶ 1,892:
Extending <tt>class Cell</tt> from [[Singly-linked_list/Element_definition#Raku]]:
<syntaxhighlight lang="raku"
self, *.next ...^ !*
}</
Usage:
<syntaxhighlight lang="raku"
for $list.Seq -> $cell {
say $cell.value;
}</
{{out}}
<pre>10
Line 1,766 ⟶ 1,909:
=={{header|Retro}}==
<
Or, using combinators:
<
With combinators you can also perform an operation on each element in a linked list:
<
=={{header|REXX}}==
<
* 25.10.2013 Walter Pachl
*********************************************************************/
Line 1,788 ⟶ 1,931:
Say c elem.c.val
c=elem.c.next
End</
=={{header|Ruby}}==
referring to [[Singly-Linked List (element)#Ruby]] and [[Singly-Linked List (element insertion)#Ruby]]
<
head.insertAfter("b", "b+")
Line 1,804 ⟶ 1,947:
print current.value, ","
end while current = current.succ
puts</
{{out}}
<pre>a,b,b+,c,
Line 1,810 ⟶ 1,953:
=={{header|Run BASIC}}==
<
for lnk = 1 to 8
print lnk;"->";word$(list$,lnk)
next lnk</
{{out}}
<pre>1->now
Line 1,831 ⟶ 1,974:
The following will demonstrate iteration all three ways.
<
//
// Iteration by value (simply empties the list as the caller now owns all values)
Line 1,908 ⟶ 2,051:
}
}</
=={{header|Scala}}==
You can use pattern matching for traversing a list.
<
/*
Here is a basic list definition
Line 1,929 ⟶ 2,072:
}
}
</syntaxhighlight>
=={{header|Scheme}}==
<
(if (null? seq)
'()
(begin
(func (car seq))
(traverse (cdr seq) func))))</
=={{header|Sidef}}==
<
#var list = ['a', ['b', ['c']]];
#var list = Pair.new('a', Pair.new('b', Pair.new('c', nil)));
Line 1,946 ⟶ 2,089:
for (var l = list; l != nil; l = l[1]) {
say l[0];
}</
{{out}}
<pre>
Line 1,956 ⟶ 2,099:
=={{header|SSEM}}==
Linked lists are a comparatively easy data structure to implement in machine language, although the SSEM does not really have enough storage to make them practically useful. A linked list consists of any number of cons cells, i.e. pairs of successive words in storage where the first word holds a data item and the second holds either a pointer to the next pair or else a special nil value—represented here by 0, although any negative address would also work—indicating we have reached the end of the list. The pairs or cons cells can be scattered arbitrarily through the available storage space. This program traverses the list <tt>'(1 2 3)</tt>, and halts with the last value in the accumulator. It makes some use of instruction arithmetic (self-modifying code).
<
10011000000000010000000000000000 1. Sub. 25
10010000000001100000000000000000 2. c to 9
Line 1,987 ⟶ 2,130:
01011000000000000000000000000000 29. pointer: 26
11000000000000000000000000000000 30. 3
00000000000000000000000000000000 31. 0 (nil)</
SSEM programs can be difficult to take in: the constant negations, subtractions, and indirect jumps often obscure the underlying algorithm. To clarify what is going on, here is a pseudocode version of the same program:
<pre>start: load loadZero
Line 2,016 ⟶ 2,159:
Using the class definition from [[Singly-Linked List (element)#Tcl|Singly-Linked List (element)]] (and bearing in mind the general notes on lists given there) we'll modify that class so that lists have an iteration method...
{{works with|Tcl|8.6}}
<
method for {varName script} {
upvar 1 $varName var
Line 2,026 ⟶ 2,169:
}
}
}</
Now, a demonstration...
<
foreach n {1 3 5 7 2 4 6 8} {
set list [List new $n $list]
Line 2,034 ⟶ 2,177:
$list for x {
puts "we have a $x in the list"
}</
=={{header|Trith}}==
<
=={{header|Visual Basic .NET}}==
<
Dim node = list.First
Do Until node Is Nothing
node = node.Next
Loop
End Sub</
=={{header|Wart}}==
<
prn x</
=={{header|Wren}}==
{{libheader|Wren-llist}}
{{libheader|Wren-fmt}}
<
import "./fmt" for Fmt
//create a new linked list and add the first 50 positive integers to it
Line 2,064 ⟶ 2,207:
Fmt.write("$4d ", i)
if (i % 10 == 0) System.print()
}</
{{out}}
Line 2,076 ⟶ 2,219:
=={{header|XPL0}}==
<
int Node, List;
[Node:= List; \traverse the linked list
while Node # 0 do
Node:= Node(Link); \move to next node
]</
=={{header|Yabasic}}==
<
// by Galileo, 02/2022
Line 2,165 ⟶ 2,308:
print
traverseList()
</syntaxhighlight>
{{out}}
<pre>1000
Line 2,178 ⟶ 2,321:
Using the <code>LinkedList</code> struct definition from [[Singly-Linked List (element)#Zig|Singly-Linked List (element)]]
<
pub fn main() anyerror!void {
Line 2,193 ⟶ 2,336:
std.log.info("> {}", .{ head.value });
}
}</
{{out}}
Line 2,205 ⟶ 2,348:
=={{header|zkl}}==
<
List(1,2,3).pump(...) // traverse and munge elements, generalized apply/map
List(1,2,3).filter(...)
Line 2,216 ⟶ 2,359:
List(1,2,3).reverse()
List(1,2,3).concat()
List(1,2,3).shuffle()</
|