Singly-linked list/Traversal: Difference between revisions

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

 

{{Template:See also lists}}

 

=={{header|ACL2}}==

The standard list data type is a singly linked list.

(if (endp xs)

(cw "End.~%")

(prog2$ (cw "~x0~%" (first xs))

 

=={{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;

 

-- Traverse the list, calling Print for each value

The_List.Iterate(Print'access);

 

=={{header|ALGOL 68}}==

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",

node := next OF node

OD;

{{out}}

<pre>

 

=={{header|ALGOL W}}==

% record type to hold a singly linked list of integers %

record ListI ( integer iValue; reference(ListI) next );

end;

 

{{out}}

<pre>

90210

</pre>

=={{header|ARM Assembly}}==

{{works with|as|Raspberry Pi}}

/* ARM assembly Raspberry PI */

/* program afficheList.s */

bx lr @ leave function

iMagicNumber: .int 0xCCCCCCCD

=={{header|AutoHotkey}}==

a_next = b

b = 2

name := %name% . "_next"

}

 

=={{header|Axe}}==

LINK(L₁+10,2)→B

LINK(L₁+50,3)→C

Disp VALUE(I)▶Dec,i

NEXT(I)→I

 

{{works with|BBC BASIC for Windows}}

DIM a{} = node{}, b{} = node{}, c{} = node{}

here.pNext% = new{}

ENDPROC

{{out}}

<pre>Traverse list:

=={{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)

{

 

current = current.Next;

 

Alternatively, as a for loop:

{

// Do something with current.Value.

 

=={{header|Clojure}}==

 

=={{header|Common Lisp}}==

 

Using LOOP:

 

 

Using MAPC

 

 

Using MAP

 

 

 

Not using builtin list iteration:

 

until (null 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

26,27: 3, 30

28,29: 1, 22

 

=={{header|D}}==

T data;

typeof(this)* next;

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;

 

foreach (val; m)

Stdout(val).newline;

 

=={{header|Delphi}}==

type

while not (pList^.Next = NIL) do pList := pList^.Next ;

 

=={{header|Dyalect}}==

Dyalect doesn't support linked lists out of the box, but it is fairly simple to implement one:

 

var list = List.Nil()

}

return list

}

}

}

for x in xs {

print(x)

 

It is also possible to provide an ad hoc solution to the problem:

{{trans|E}}

 

 

while xs is (value, tail) {

print(value)

xs = tail

 

Here a linked list is emulated using tuples.

=={{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 🌀))

 

(foldl + 0 L) → 500500 ; 1000 * 1001 / 2

 

 

=={{header|Ela}}==

 

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:

 

 

=={{header|Elena}}==

Simple iteration with a while loop.

while(nil != current){

console printLine(current.Item);

current := current.Next

 

=={{header|Erlang}}==

 

=={{header|Factor}}==

[ [ data>> ] dip call ]

[ [ next>> ] dip over [ list-each ] [ 2drop ] if ] 2bi ; inline recursive

[ B <linked-list> list-insert ] keep

 

{{out}}

<pre>

=={{header|Fantom}}==

Using the definitions from [[Singly-Linked_List_(element_insertion)]]:

Node? current := a

while (current != null)

echo (current.value)

current = current.successor

 

=={{header|Forth}}==

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

>r begin ?dup while

dup cell+ @ r@ execute

 

Testing code:

=={{header|Fortran}}==

Fortran 95. See [[Singly-Linked List (element)#Fortran|Singly-Linked List (element) in Fortran]].

type(node), target :: list

type(node), pointer :: current

current => current%next

end do

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

real, intent(in) :: data

write (*,*) data

type(node), intent(in) :: list

call traversal(list,printNode)

 

=={{header|Go}}==

See [[Singly-Linked List (element)#Go|Singly-Linked List (element) in Go]].

end := start.Append("burritos")

end = end.Append("fajitas")

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"]

traverse :: [a] -> [a]

traverse list = map func list

 

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.

=={{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

ns := ns.successor

}

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)

 

var head = createLinkedListFromArray([10,20,30,40]);

Uses the <code>print()</code> function from [[Rhino]]

 

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

 

return list.map(fn);

},

/* Orange */

/* Mango */

 

=={{header|jq}}==

 

 

 

 

 

=={{header|Julia}}==

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

for n in lst

print(n, " ")

 

=={{header|Kotlin}}==

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

val list = IntRange(1, 50).toList()

 

// 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

20 19 18 17 16 15 14 13 12 11

10 9 8 7 6 5 4 3 2 1</pre>

=={{header|Limbo}}==

Lists are a built-in type in Limbo.

 

include "sys.m";

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

 

=={{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).

 

 

:- end_object.

{{out}}

| ?- singly_linked_list::show.

1

3

yes

 

kitten

sitting

rosettacode

 

=={{header|MATLAB}} / {{header|Octave}}==

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))

 

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

 

 

=={{header|NewLISP}}==

 

=={{header|Nim}}==

next: Node[T]

data: T

iterator items(a: Node) =

var x = a

yield x

x = x.next

 

for item in a:

 

=={{header|Objeck}}==

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

node->GetValue()->PrintLine();

};

 

=={{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

waltz

nymph

 

=={{header|Oforth}}==

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

 

 

{{out}}

=={{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

do value over list

say value

{{out}}

<pre>Manual list traversal

 

=={{header|Pascal}}==

 

=={{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|

<@ ITEFORSZELSTLIT>public holidays|

<@ SAYLST>...</@><@ ACTMOVBKWLST>...</@>

This variable length Simplified Chinese rendition of the same code is

<# 忽略>From First to Last</#>

<# 迭代迭代次数结构大小列表字串>public holidays|

<# 迭代迭代次数结构大小列表字串>public holidays|

<# 显示列表>...</#><# 运行移位指针向后列表>...</#>

 

=={{header|Perl}}==

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

use strict;

use Class::Tiny qw( val next );

$node = $node->next;

}

{{out}}

<pre>10... 9... 8... 7... 6... 5... 4... 3... 2... 1...

</pre>

 

=={{header|Phix}}==

See also [[Singly-linked_list/Element_removal#Phix|Removal]].

{{out}}

<pre>

"ONE"

"TWO"

=={{header|PicoLisp}}==

We might use map functions

or flow control functions

{{out}} for both cases:

<pre>a

 

=={{header|PL/I}}==

/*********************************************************************

* 25.10.2013 Walter Pachl

p=p->next;

End;

{{out}}

<pre> 1 Walter

 

=={{header|PureBasic}}==

While *node

;access data, i.e. PrintN(Str(*node\Value))

 

;called using

 

=={{header|Python}}==

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!

for value in lst:

print value,;

{{out}}

<pre>

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:

 

#lang racket

 

(mfor-each displayln ml)

(for ([x (in-mlist ml)]) (displayln x))

 

=={{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

*********************************************************************/

Say c elem.c.val

c=elem.c.next

 

=={{header|Ruby}}==

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

head.insertAfter("b", "b+")

 

print current.value, ","

end while current = current.succ

{{out}}

<pre>a,b,b+,c,

 

=={{header|Run BASIC}}==

for lnk = 1 to 8

print lnk;"->";word$(list$,lnk)

{{out}}

<pre>1->now

The following will demonstrate iteration all three ways.

 

//

// Iteration by value (simply empties the list as the caller now owns all values)

}

 

 

=={{header|Scala}}==

You can use pattern matching for traversing a list.

 

/*

Here is a basic list definition

}

}

 

=={{header|Scheme}}==

(if (null? seq)

'()

(begin

(func (car seq))

 

=={{header|Sidef}}==

#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];

{{out}}

<pre>

=={{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

01011000000000000000000000000000 29. pointer: 26

11000000000000000000000000000000 30. 3

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

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

}

}

Now, a demonstration...

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"

 

=={{header|Trith}}==

 

=={{header|Visual Basic .NET}}==

Dim node = list.First

Do Until node Is Nothing

node = node.Next

Loop

 

=={{header|Wart}}==

 

=={{header|XPL0}}==

 

=={{header|zkl}}==

List(1,2,3).pump(...) // traverse and munge elements, generalized apply/map

List(1,2,3).filter(...)

List(1,2,3).reverse()

List(1,2,3).concat()