Singly-linked list/Traversal

From Rosetta Code
Task
Singly-linked list/Traversal
You are encouraged to solve this task according to the task description, using any language you may know.

Traverse from the beginning of a singly-linked list to the end.

See also

ACL2[edit]

The standard list data type is a singly linked list.

(defun traverse (xs)
(if (endp xs)
(cw "End.~%")
(prog2$ (cw "~x0~%" (first xs))
(traverse (rest xs)))))

ActionScript[edit]

See Singly-Linked List (element) in ActionScript

var A:Node;
//...
for(var i:Node = A; i != null; i = i.link)
{
doStuff(i);
}

Ada[edit]

The Ada standard container library provides a doubly-linked list. List traversal is demonstrated for the forward links.

with Ada.Containers.Doubly_Linked_Lists;
with Ada.Text_Io; use Ada.Text_Io;
 
procedure Traversal_Example is
package Int_List is new Ada.Containers.Doubly_Linked_Lists(Integer);
use Int_List;
procedure Print(Position : Cursor) is
begin
Put_Line(Integer'Image(Element(Position)));
end Print;
The_List : List;
begin
for I in 1..10 loop
The_List.Append(I);
end loop;
-- Traverse the list, calling Print for each value
The_List.Iterate(Print'access);
end traversal_example;

ALGOL 68[edit]

Works with: ALGOL 68 version Revision 1 - no extensions to language used
Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny
Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8-8d

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:

MODE STRINGLIST = STRUCT(STRING value, REF STRINGLIST next);
 
STRINGLIST list := ("Big",
LOC STRINGLIST := ("fjords",
LOC STRINGLIST := ("vex",
LOC STRINGLIST := ("quick",
LOC STRINGLIST := ("waltz",
LOC STRINGLIST := ("nymph",NIL))))));
 
REF STRINGLIST node := list;
WHILE node ISNT REF STRINGLIST(NIL) DO
print((value OF node, space));
node := next OF node
OD;
print(newline)
Output:
Big fjords vex quick waltz nymph

ALGOL W[edit]

begin
 % record type to hold a singly linked list of integers  %
record ListI ( integer iValue; reference(ListI) next );
 
 % inserts a new value after the specified element of a list  %
procedure insert( reference(ListI) value list
 ; integer value newValue
) ;
next(list) := ListI( newValue, next(list) );
 
 % declare variables to hold the list  %
reference(ListI) head, pos;
 
 % create a list of integers  %
head := ListI( 1701, ListI( 9000, ListI( 42, ListI( 90210, null ) ) ) );
 
 % insert a new value into the list  %
insert( next(head), 4077 );
 
 % traverse the list  %
pos := head;
 
while pos not = null do begin
write( iValue(pos) );
pos := next(pos);
end;
 
end.
Output:
          1701  
          9000  
          4077  
            42  
         90210  

AutoHotkey[edit]

a = 1
a_next = b
b = 2
b_next = c
c = 3
 
traverse("a")
return
 
traverse(element)
{
MsgBox % element . "= " . %element%
name := element . "_next"
while, %name%
{
element := %name%
msgbox % %name% . "= " . %element%
name := %name% . "_next"
}
}

Axe[edit]

LINK(L₁,1)→A
LINK(L₁+10,2)→B
LINK(L₁+50,3)→C
 
INSERT(A,B)
INSERT(A,C)
 
A→I
While I≠0
Disp VALUE(I)▶Dec,i
NEXT(I)→I
End

BBC BASIC[edit]

      DIM node{pNext%, iData%}
DIM a{} = node{}, b{} = node{}, c{} = node{}
 
a.pNext% = b{}
a.iData% = 123
b.iData% = 789
c.iData% = 456
 
PROCinsert(a{}, c{})
 
PRINT "Traverse list:"
pnode% = a{}
REPEAT
 !(^node{}+4) = pnode%
PRINT node.iData%
pnode% = node.pNext%
UNTIL pnode% = 0
 
END
 
DEF PROCinsert(here{}, new{})
new.pNext% = here.pNext%
here.pNext% = new{}
ENDPROC
 
Output:
Traverse list:
       123
       456
       789

C[edit]

See Singly-Linked List (element) in C.

struct link *first;
// ...
struct link *iter;
for(iter = first; iter != NULL; iter = iter->next) {
// access data, e.g. with iter->data
}

C++[edit]

Works with: C++11

For each traversal version.

#include <iostream>
#include <forward_list>
 
int main()
{
std::forward_list<int> list{1, 2, 3, 4, 5};
for (int e : list)
std::cout << e << std::endl;
}

C#[edit]

Simple iteration with a while loop.

//current is the first Link in the list
while(current != null){
System.Console.WriteLine(current.item);
current = current.next;
}

Clojure[edit]

(doseq [x xs] (println x))

Common Lisp[edit]

(dolist (x list)
(print x))

Using LOOP:

(loop for x in list do (print x))

Using MAPC

(mapc #'print list)

Using MAP

(map nil #'print list)


Not using builtin list iteration:

(loop for ref = list then (rest ref)
until (null ref)
do (print (first ref)))

Computer/zero Assembly[edit]

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 NIL value that is guaranteed not to be a valid address; in this implementation, we use 0 to represent NIL. The order of CONS cells in memory is of course entirely unimportant. For the sake of example, this program traverses the list '(1 2 3 4 5 6) 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).

start:  LDA  load
ADD car  ; head of list
STA ldcar
 
ADD one
STA ldcdr
 
ldcar: NOP
STA value
 
ldcdr: NOP
BRZ done  ; 0 == NIL
STA car
 
JMP start
 
done: LDA value
STP
 
load: LDA 0
value: 0
car: 28  ; head of list
one: 1
 
20,21: 6, 0
22,23: 2, 26
24,25: 5, 20
26,27: 3, 30
28,29: 1, 22
30,31: 4, 24

D[edit]

struct SLinkedNode(T) {
T data;
typeof(this)* next;
}
 
void main() {
import std.stdio;
 
alias N = SLinkedNode!int;
auto lh = new N(1, new N(2, new N(3, new N(4))));
 
for (auto p = lh; p; p = p.next)
write(p.data, " ");
writeln();
}
Output:
1 2 3 4 

Alternative Version[edit]

Using tango's collections (written by Doug Lea, ported to D):

import tango.io.Stdout;
import tango.util.collection.LinkSeq;
 
void main() {
auto m = new LinkSeq!(char[]);
m.append("alpha");
m.append("bravo");
m.append("charlie");
foreach (val; m)
Stdout(val).newline;
}

Delphi[edit]

uses system ;
 
type
 
// declare the list pointer type
plist = ^List ;
 
// declare the list type, a generic data pointer prev and next pointers
List = record
data : pointer ;
next : pList ;
end;
 
// since this task is just showing the traversal I am not allocating the memory and setting up the root node etc.
// Note the use of the carat symbol for de-referencing the pointer.
 
begin
 
// beginning to end
while not (pList^.Next = NIL) do pList := pList^.Next ;
 
end;

E[edit]

Using a list made from tuples:

var linkedList := [1, [2, [3, [4, [5, [6, [7, null]]]]]]]
 
while (linkedList =~ [value, next]) {
println(value)
linkedList := next
}

Using a list made from the structure defined at Singly-Linked List (element):

var linkedList := makeLink(1, makeLink(2, makeLink(3, empty)))
 
while (!(linkedList.null())) {
println(linkedList.value())
linkedList := linkedList.next()
}

EchoLisp[edit]

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 🌀))
 
(for-each write friends)→ albert ludwig elvis 🌀
 
; for loop
(for ((friend friends)) (write friend)) → albert ludwig elvis 🌀
 
; map a function
(map string-upcase friends)("ALBERT" "LUDWIG" "ELVIS" "🌀")
(map string-randcase friends)("ALBerT" "LudWIG" "elVis" "🌀")
 
; recursive way
(define (rscan L)
(unless (null? L)
(write (first L))
(rscan (rest L))))
 
(rscan friends) → albert ludwig elvis 🌀
 
; folding a list
; check that ∑ 1..n = n (n+1)/2
 
(define L (iota 1001))
(foldl + 0 L)500500 ; 1000 * 1001 / 2
 
 

Ela[edit]

traverse [] = []
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:

xs = [& x \\ x <- [1..1000]]//lazy list
 
traverse xs

Erlang[edit]

Use built in functions like lists:map/2 and lists:foldl/3.

1> lists:map( fun erlang:is_integer/1, [1,2,3,a,b,c] ).
[true,true,true,false,false,false]
4> lists:foldl( fun erlang:'+'/2, 0, [1,2,3] ).
6

Factor[edit]

: list-each ( linked-list quot: ( data -- ) -- )
[ [ data>> ] dip call ]
[ [ next>> ] dip over [ list-each ] [ 2drop ] if ] 2bi ; inline recursive
 
SYMBOLS: A B C ;
 
A <linked-list>
[ C <linked-list> list-insert ] keep
[ B <linked-list> list-insert ] keep
 
[ . ] list-each
Output:
A
B
C

Fantom[edit]

Using the definitions from Singly-Linked_List_(element_insertion):

    // traverse the linked list
Node? current := a
while (current != null)
{
echo (current.value)
current = current.successor
}

Forth[edit]

: last ( list -- end )
begin dup @ while @ repeat ;

And here is a function to walk a list, calling an XT on each data cell:

: walk ( a xt -- )
>r begin ?dup while
dup cell+ @ r@ execute
@ repeat r> drop ;

Testing code:

A ' emit walk ABC ok

Fortran[edit]

Fortran 95. See Singly-Linked List (element) in Fortran.

subroutine traversal(list,proc)
type(node), target :: list
type(node), pointer :: current
interface
subroutine proc(node)
real, intent(in) :: node
end subroutine proc
end interface
current => list
do while ( associated(current) )
call proc(current%data)
current => current%next
end do
end subroutine traversal

Print data from all nodes of a singly-linked list:

subroutine printNode(data)
real, intent(in) :: data
write (*,*) data
end subroutine
 
subroutine printAll(list)
type(node), intent(in) :: list
call traversal(list,printNode)
end subroutine printAll

Go[edit]

See Singly-Linked List (element) in Go.

start := &Ele{"tacos", nil}
end := start.Append("burritos")
end = end.Append("fajitas")
end = end.Append("enchilatas")
for iter := start; iter != nil; iter = iter.Next {
fmt.Println(iter)
}

Haskell[edit]

Lists are ubiquitous in Haskell, simply use Haskell's map library function:

map (>5) [1..10] -- [False,False,False,False,False,True,True,True,True,True]
 
map (++ "s") ["Apple", "Orange", "Mango", "Pear"] -- ["Apples","Oranges","Mangos","Pears"]
 
foldr (+) 0 [1..10] -- prints 55
 
traverse :: [a] -> [a]
traverse list = map func list
where func a = -- ...do something with a

Note that the traverse function is polymorphic; denoted by traverse :: [a] -> [a] where a can be of any type.

Icon and Unicon[edit]

Using either the record or class-based definitions from Singly-Linked List (element) in Icon and Unicon:

procedure main ()
ns := Node(1, Node(2, Node (3)))
until /ns do { # repeat until ns is null
write (ns.value)
ns := ns.successor
}
end

Prints the numbers 1, 2, 3 in turn.

J[edit]

Using the implementation mentioned at Singly-Linked List (element) in J, we can apply a function foo to each node the following way:

foo"0 {:"1 list

Java[edit]

Works with: Java version 1.5+

For Java.util.LinkedList<T>, use a for each loop (from Loop Structures):

LinkedList<Type> list = new LinkedList<Type>();
 
for(Type i: list){
//each element will be in variable "i"
System.out.println(i);
}

Note that java.util.LinkedList can also perform as a stack, queue, or doubly-linked list.

JavaScript[edit]

Extending Singly-Linked_List_(element)#JavaScript

LinkedList.prototype.traverse = function(func) {
func(this);
if (this.next() != null)
this.next().traverse(func);
}
 
LinkedList.prototype.print = function() {
this.traverse( function(node) {print(node.value())} );
}
 
var head = createLinkedListFromArray([10,20,30,40]);
head.print();

Uses the print() function from Rhino


Alternatively, translating the Haskell examples in terms of JavaScript's Array.map, Array.reduce, and Array.forEach:

var map = function (fn, list) {
return list.map(fn);
},
 
foldr = function (fn, acc, list) {
var listr = list.slice();
listr.reverse();
 
return listr.reduce(fn, acc);
},
 
traverse = function (list, fn) {
return list.forEach(fn);
};
 
var range = function (m, n) {
return Array.apply(null, Array(n - m + 1)).map(
function (x, i) {
return m + i;
}
);
};
 
// --> [false, false, false, false, false, true, true, true, true, true]
map(function (x) {
return x > 5;
}, range(1, 10));
 
// --> ["Apples", "Oranges", "Mangos", "Pears"]
map(function (x) {
return x + 's';
}, ["Apple", "Orange", "Mango", "Pear"])
 
// --> 55
foldr(function (acc, x) {
return acc + x;
}, 0, range(1, 10))
 
 
traverse(["Apple", "Orange", "Mango", "Pear"], function (x) {
console.log(x);
})
/* Apple */
/* Orange */
/* Mango */
/* Pear */

jq[edit]

In practice, jq's arrays would probably be used whenever a singly-linked list might otherwise be used, but to illustrate traversal through a linked list, let us use JSON objects with keys "car" and "cdr", where a "cdr" value of null indicates the end of the linked list.

For example:

def test_list:
{ "car": 1, "cdr": { "car": 2, "cdr": { "car": 3, "cdr": null }}};
 

To illustrate iteration along the links:

def traverse: .car, (.cdr | if . == null then empty else traverse end);

A more mind-bending approach is to use recurse/1:

 def traverse2: recurse( .cdr ) | .car;

test_list | traverse and test_list | traverse2 produce identical results: a stream of the "car" values.

Kotlin[edit]

Lists in Kotlin may be instanciated from Java classes or from Kotlin methods or extensions.

fun main(args: Array<String>) {
val list = IntRange(1, 50).toList()
 
// classic traversal:
for (i in list) { print("%4d ".format(i)); if (i % 10 == 0) println() }
 
// list iterator:
list.asReversed().forEach { print("%4d ".format(it)); if (it % 10 == 1) println() }
}
Output:
   1    2    3    4    5    6    7    8    9   10 
  11   12   13   14   15   16   17   18   19   20 
  21   22   23   24   25   26   27   28   29   30 
  31   32   33   34   35   36   37   38   39   40 
  41   42   43   44   45   46   47   48   49   50 
  50   49   48   47   46   45   44   43   42   41 
  40   39   38   37   36   35   34   33   32   31 
  30   29   28   27   26   25   24   23   22   21 
  20   19   18   17   16   15   14   13   12   11 
  10    9    8    7    6    5    4    3    2    1

[edit]

LAST is already a Logo built-in, but it could be defined this way:

to last :list
if empty? bf :list [output first :list]
output last bf :list
end

Logtalk[edit]

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).
 
:- public(show/0).
 
show :-
traverse([1,2,3]).
 
traverse([]).
traverse([Head| Tail]) :-
write(Head), nl,
traverse(Tail).
 
:- end_object.
 
Output:
 
| ?- singly_linked_list::show.
1
2
3
yes
 

Mathematica[edit]

Print /@ {"rosettacode", "kitten", "sitting", "rosettacode",  "raisethysword"}
->
rosettacode
kitten
sitting
rosettacode
raisethysword

MATLAB / Octave[edit]

Matlab and Octave do not have pointers. Linked lists are implemented as vectors (i.e. arrays of size 1xN)

list = 1:10; 
for k=1:length(list)
printf('%i\n',list(k))
end;

It is recommended to avoid loops and "vectorize" the code:

  printf('%d\n', list(:));    

NewLISP[edit]

(dolist (x '(a b c d e))
(println x))

Nim[edit]

type Node[T] = ref object
next: Node[T]
data: T
 
proc newNode[T](data: T): Node[T] =
Node[T](data: data)
 
var a = newNode 12
var b = newNode 13
var c = newNode 14
 
proc insertAppend(a, n: var Node) =
n.next = a.next
a.next = n
 
a.insertAppend(b)
b.insertAppend(c)
 
iterator items(a: Node) =
var x = a
while x != nil:
yield x
x = x.next
 
for item in a:
echo item.data

Objeck[edit]

 
for(node := head; node <> Nil; node := node->GetNext();) {
node->GetValue()->PrintLine();
};
 

Objective-C[edit]

(See Singly-Linked List (element))

RCListElement *current;
for(current=first_of_the_list; current != nil; current = [current next] )
{
// to get the "datum":
// id dat_obj = [current datum];
}

OCaml[edit]

# let li = ["big"; "fjords"; "vex"; "quick"; "waltz"; "nymph"] in
List.iter print_endline li ;;
big
fjords
vex
quick
waltz
nymph
- : unit = ()

Oforth[edit]

See Singly-Linked List/Element_insertion in Oforth for the full class definition.

Because forEachNext is defined, a linked list responds to all methods defined for Collections : apply, map, filter, ....

: testLink LinkedList new($A, null) dup add($B) dup add($C) ;
testLink apply(#println)
Output:
A
C
B

ooRexx[edit]

See Singly-Linked List/Element Definition in ooRexx for the full class definition.

 
say "Manual list traversal"
index = list~first -- demonstrate traversal
loop while index \== .nil
say index~value
index = index~next
end
 
say
say "Do ... Over traversal"
do value over list
say value
end
 
 

Pascal[edit]

See Delphi

Peloton[edit]

This makes a list of the Chinese Public Holiday and lists them first till last and then last till first.

<@ LETCNSLSTLIT>public holidays|開國紀念日^和平紀念日^婦女節、兒童節合併假期^清明節^國慶日^春節^端午節^中秋節^農曆除夕</@>
<@ OMT>From First to Last</@>
<@ ITEFORSZELSTLIT>public holidays|
<@ SAYLST>...</@><@ ACTMOVFWDLST>...</@>
</@>
<@ OMT>From Last to First (pointer is still at end of list)</@>
<@ ITEFORSZELSTLIT>public holidays|
<@ SAYLST>...</@><@ ACTMOVBKWLST>...</@>
</@>

This variable length Simplified Chinese rendition of the same code is

<# 指定构造列表字串>public holidays|開國紀念日^和平紀念日^婦女節、兒童節合併假期^清明節^國慶日^春節^端午節^中秋節^農曆除夕</#>
<# 忽略>From First to Last</#>
<# 迭代迭代次数结构大小列表字串>public holidays|
<# 显示列表>...</#><# 运行移位指针向前列表>...</#>
</#>
<# 忽略>From Last to First (pointer is still at end of list)</#>
<# 迭代迭代次数结构大小列表字串>public holidays|
<# 显示列表>...</#><# 运行移位指针向后列表>...</#>
</#>

Perl[edit]

We use Class::Tiny to get OO functionality with minimal effort.

package SSL_Node;
use strict;
use Class::Tiny qw( val next );
 
sub BUILD {
my $self = shift;
exists($self->{val}) or die "Must supply 'val'";
if (exists $self->{next}) {
ref($self->{next}) eq 'SSL_Node'
or die "If supplied, 'next' must be an SSL_Node";
}
return;
}
 
package main;
use strict;
# Construct an example list,
my @vals = 1 .. 10;
my $countdown = SSL_Node->new(val => shift(@vals));
while (@vals) {
my $head = SSL_Node->new(val => shift(@vals), next => $countdown);
$countdown = $head;
}
# ...then traverse it.
my $node = $countdown;
while ($node) {
print $node->val, "... ";
$node = $node->next;
}
print "\n";
Output:
10... 9... 8... 7... 6... 5... 4... 3... 2... 1...

Perl 6[edit]

Built-in list processing in Perl is not specifically based on singly-linked lists, but works at a higher abstraction level that encapsulates such implementation choices. Nonetheless, it's trivial to use the Pair type to build what is essentially a Lisp-style cons list, and in fact, the => pair constructor is right associative for precisely that reason. We traverse such a list here using a 3-part loop:

my $list = 1 => 2 => 3 => 4 => 5 => 6 => Mu;
 
loop (my $l = $list; $l; $l.=value) {
say $l.key;
}
Output:
1
2
3
4
5
6

It would be pretty easy to make such lists iterable as normal Perl lists, if anyone really cared to...

Well, shoot, let's just go ahead and do it. We'll pretend the Pair type is really a list type. (And we show how you turn an ordinary list into a cons list using a reduction. Note how the [=>] reduction is also right associative, just like the base operator.)

use MONKEY_TYPING;
augment class Pair {
method traverse () {
gather loop (my $l = self; $l; $l.=value) {
take $l.key;
}
}
}
 
my $list = [=>] 'Ⅰ' .. 'Ⅻ', Mu;
say ~$list.traverse;
Output:
Ⅰ Ⅱ Ⅲ Ⅳ Ⅴ Ⅵ Ⅶ Ⅷ Ⅸ Ⅹ Ⅺ Ⅻ

Phix[edit]

enum NEXT,DATA
constant empty_sll = {{1}}
sequence sll = 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!=1 do
 ?sll[idx][DATA]
idx = sll[idx][NEXT]
end while
end procedure
show()
Output:
{{2},{3,"ONE"},{4,"TWO"},{1,"THREE"}}
"ONE"
"TWO"
"THREE"

PicoLisp[edit]

We might use map functions

(mapc println '(a "cde" (X Y Z) 999))

or flow control functions

(for X '(a "cde" (X Y Z) 999)
(println X) )
Output:
for both cases:
a
"cde"
(X Y Z)
999

PL/I[edit]

*process source attributes xref or(!);
/*********************************************************************
* 25.10.2013 Walter Pachl
* 'set dd:in=d:\sll.txt,recsize(80)'
* 'sll'
*********************************************************************/

sll: Proc Options(main);
Dcl in Record Input;
Dcl sysprint Print;
Dcl 1 elem Based(p),
2 next Ptr Init(null()),
2 value Char(20) Var;
Dcl head Ptr;
Dcl p Ptr;
Dcl prev Ptr;
Dcl i Bin Fixed(31);
Dcl rec Char(80) Var;
Dcl null Builtin;
On Endfile(in) goto show;
Do i=1 By 1;
Read File(in) Into(rec);
alloc elem set(p);
If i=1 Then Do;
head=p;
prev=head;
value=rec;
End;
Else Do;
prev->next=p;
prev=p;
value=rec;
End;
End;
 
show:
p=head;
Do i=1 By 1 while(p^=null());
Put Edit(i,p->value)(skip,f(3),x(1),a);
p=p->next;
End;
End;
Output:
  1 Walter
  2 Pachl
  3 wrote
  4 this

PureBasic[edit]

Procedure traverse(*node.MyData)
While *node
;access data, i.e. PrintN(Str(*node\Value))
*node = *node\next
Wend
EndProcedure
 
;called using
traverse(*firstnode.MyData)

Python[edit]

for node in lst:
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.

class LinkedList(object):
"""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!
"""

def __init__(self, value, next):
self.value = value;
self.next = next
def __iter__(self):
node = self
while node != None:
yield node.value
node = node.next;
 
lst = LinkedList("big", next=
LinkedList(value="fjords",next=
LinkedList(value="vex", next=
LinkedList(value="quick", next=
LinkedList(value="waltz", next=
LinkedList(value="nymph", next=None))))));
 
for value in lst:
print value,;
print
Output:
big fjords vex quick waltz nymph

Racket[edit]

Since singly-linked lists that are made of cons cells are one of the most common primitive types in Racket, there is a lot of built-in functionality that scans these lists:

 
#lang racket
 
(define l (list 1 2 3))
 
;; scan the list and collect a list of function results
(map add1 l)
 
;; scan the list and run some function on each element for its side-effect
(for-each displayln l)
 
;; scan a list and sum up its elements
(foldl + 0 l)
 
;; same as the above three, using a more modern syntax that is often
;; more convenient
(for/list ([x (in-list l)]) (add1 x))
(for ([x (in-list l)]) (displayln x))
(for/fold ([sum 0]) ([x (in-list l)]) (+ x sum))
 
;; the same as the first, but make up a vector of results
(for/vector ([x (in-list l)]) (add1 x))
 
;; there is less support for mutable pairs, but it's still extensive
;; enough to cover all the basics
(require racket/mpair)
(define ml (mlist 1 2 3))
(mmap add1 ml)
(mfor-each displayln ml)
(for ([x (in-mlist ml)]) (displayln x))
 

Retro[edit]

: traverse ( l- ) repeat @ 0; again ;

Or, using combinators:

last [ drop ] ^types'LIST each@

With combinators you can also perform an operation on each element in a linked list:

last [ @d->name puts space ] ^types'LIST each@

REXX[edit]

/*********************************************************************
* 25.10.2013 Walter Pachl
*********************************************************************/

in='d:\sll.txt'
Do i=1 By 1 while lines(in)>0
rec=linein(in)
elem.i.val=rec
elem.i.next=0
ip=i-1
elem.ip.next=i
End;
c=1
Do While c<>0
Say c elem.c.val
c=elem.c.next
End

Ruby[edit]

referring to Singly-Linked List (element)#Ruby and Singly-Linked List (element insertion)#Ruby

head = ListNode.new("a", ListNode.new("b", ListNode.new("c")))
head.insertAfter("b", "b+")
 
# then:
head.each {|node| print node.value, ","}
puts
 
# or
current = head
begin
print current.value, ","
end while current = current.succ
puts
Output:
a,b,b+,c,
a,b,b+,c,

Run BASIC[edit]

list$ = "now is the time for all good men"
for lnk = 1 to 8
print lnk;"->";word$(list$,lnk)
next lnk
Output:
1->now
2->is
3->the
4->time
5->for
6->all
7->good
8->men

Rust[edit]

Extending Singly-Linked List (element)#Rust. Please see that page for the Linked List struct declarations.

In Rust, there are three ways to pass something: by value (which forfeits ownership), by reference (there can be infinitely many immutable references to an object), or by mutable reference (there may only be one mutable reference and no other immutable ones).

The following will demonstrate iteration all three ways.

// 
//
// Iteration by value (simply empties the list as the caller now owns all values)
//
//
pub struct IntoIter<T>(List<T>);
 
impl<T> Iterator for IntoIter<T> {
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
self.0.head.take().map(|node| {
let node = *node;
self.0.head = node.next;
node.elem
})
}
}
 
//
//
// Iteration by immutable reference
//
//
 
pub struct Iter<'a, T: 'a> {
next: Option<&'a Node<T>>,
}
 
impl<'a, T> Iterator for Iter<'a, T> {
type Item = &'a T;
fn next(&mut self) -> Option<Self::Item> {
self.next.take().map(|node| {
self.next = node.next.as_ref().map(|node| &**node);
&node.elem
})
}
}
 
//
//
// Iteration by mutable reference
//
//
 
pub struct IterMut<'a, T: 'a> {
next: Option<&'a mut Node<T>>,
}
 
impl<'a, T> Iterator for IterMut<'a, T> {
type Item = &'a mut T;
fn next(&mut self) -> Option<Self::Item> {
self.next.take().map(|node| {
self.next = node.next.as_mut().map(|node| &mut **node);
&mut node.elem
})
}
}
 
//
//
// Methods implemented for List<T>
//
//
 
impl<T> List<T> {
pub fn into_iter(self) -> IntoIter<T> {
IntoIter(self)
}
 
pub fn iter<'a>(&'a self) -> Iter<'a,T> {
Iter { next: self.head.as_ref().map(|node| &**node) }
}
 
pub fn iter_mut(&mut self) -> IterMut<T> {
IterMut { next: self.head.as_mut().map(|node| &mut **node) }
}
 
}

Scala[edit]

Scala has a Seq (for sequence) trait that is more general than singly-linked lists. These two examples are equivalent for SLL, but the second would be faster for other sequence types.

def traverse1[T](xs: Seq[T]): Unit = xs match {
case s if s.isEmpty => ()
case _ => { Console.println(xs.head);
traverse1(xs.tail)
}
}
def traverse2[T](xs: Seq[T]) = for (x <- xs) Console.println(x)

Scheme[edit]

(define (traverse seq func)
(if (null? seq)
'()
(begin
(func (car seq))
(traverse (cdr seq) func))))

Sidef[edit]

var list = 'a':'b':'c':nil;
#var list = ['a', ['b', ['c']]];
#var list = Pair.new('a', Pair.new('b', Pair.new('c', nil)));
 
for (var l = list; l != nil; l = l[1]) {
say l[0];
}
Output:
a
b
c

SSEM[edit]

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 '(1 2 3), and halts with the last value in the accumulator. It makes some use of instruction arithmetic (self-modifying code).

11101000000000100000000000000000   0. -23 to c
10011000000000010000000000000000 1. Sub. 25
10010000000001100000000000000000 2. c to 9
10101000000000010000000000000000 3. Sub. 21
11010000000001100000000000000000 4. c to 11
10010000000000100000000000000000 5. -9 to c
10010000000001100000000000000000 6. c to 9
11010000000000100000000000000000 7. -11 to c
11010000000001100000000000000000 8. c to 11
00000000000000000000000000000000 9. to be generated at run time
00101000000001100000000000000000 10. c to 20
00000000000000000000000000000000 11. to be generated at run time
00000000000000110000000000000000 12. Test
00011000000000000000000000000000 13. 24 to CI
10011000000001100000000000000000 14. c to 25
10011000000000100000000000000000 15. -25 to c
10011000000001100000000000000000 16. c to 25
01101000000000000000000000000000 17. 22 to CI
00101000000000100000000000000000 18. -20 to c
00000000000001110000000000000000 19. Stop
00000000000000000000000000000000 20. variable: negation of car
10000000000000000000000000000000 21. constant 1
11111111111111111111111111111111 22. constant -1
00000000000000100000000000000000 23. -0 to c
10001000000000000000000000000000 24. constant 17 (jump target)
00111000000000000000000000000000 25. 28 (pointer variable)
01000000000000000000000000000000 26. 2
01111000000000000000000000000000 27. pointer: 30
10000000000000000000000000000000 28. 1
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:

start:    load         loadZero
          add          pointer
          store        loadCar
          add          #1
          store        loadCdr
loadCar:  ; generated at run time
          store        value
loadCdr:  ; generated at run time
          branchOnZero end
          store        pointer
          jump         start
end:      load         value
          halt
value:            0 ; variable
loadZero: load         0
pointer:          28

26 and 27:        (2 . 30)
28 and 29:        (1 . 26)
30 and 31:        (3 . 0)

Tcl[edit]

Using the class definition from 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 version 8.6
oo::define List {
method for {varName script} {
upvar 1 $varName var
set elem [self]
while {$elem ne ""} {
set var [$elem value]
uplevel 1 $script
set elem [$elem next]
}
}
}

Now, a demonstration...

set list {}
foreach n {1 3 5 7 2 4 6 8} {
set list [List new $n $list]
}
$list for x {
puts "we have a $x in the list"
}

Trith[edit]

[1 2 3 4 5] [print] each

Visual Basic .NET[edit]

Private Sub Iterate(ByVal list As LinkedList(Of Integer))
Dim node = list.First
Do Until node Is Nothing
node = node.Next
Loop
End Sub

Wart[edit]

each x '(1 2 3)
prn x

XPL0[edit]

repeat Node:= Node(0) until Node=0

zkl[edit]

foreach n in (List(1,2,3) {...}
List(1,2,3).pump(...) // traverse and munge elements, generalized apply/map
List(1,2,3).filter(...)
List(1,2,3).filter22(...) // partition list
List(1,2,3).reduce(...)
List(1,2,3).apply(...)
List(1,2,3).sum()
List(1,2,3).run() // treat each element as f, perform f()
List(1,2,3).enumerate()
List(1,2,3).reverse()
List(1,2,3).concat()
List(1,2,3).shuffle()