Singly-linked list/Traversal: Difference between revisions

{{Template:See also lists}}

<br><br>

 

=={{header|AArch64 Assembly}}==

{{works with|as|Raspberry Pi 3B version Buster 64 bits}}

/* ARM assembly AARCH64 Raspberry PI 3B */

/* program afficheList64.s */

.include "../includeARM64.inc"

 

 

=={{header|ACL2}}==

The standard list data type is a singly linked list.

(if (endp xs)

(cw "End.~%")

(prog2$ (cw "~x0~%" (first 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!

 

Clear()

{{out}}

[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Singly-linked_list_traversal.png Screenshot from Atari 8-bit computer]

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

=={{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|C++}}==

{{works with|C++11}}

For each traversal version.

#include <forward_list>

 

for (int e : list)

std::cout << e << std::endl;

 

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

for i in (len-1)^-1..0 {

}

var xs = this

do {

}

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

next i

 

 

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

 

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.

# Produce a stream of the items in the input SLL.

def items:

# If f evaluates to empty at any item, that item is removed;

# if f evaluates to more than one item, all are added separately.

'''Examples'''

"item": 1,

"next": {

}

| reduce items as $item (null; .+$item),

{{out}}

<pre>

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

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

 

=={{header|Mathematica}}/{{header|Wolfram Language}}==

{{out}}

<pre>rosettacode

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

{{out}}

<pre>

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

 

=={{header|NewLISP}}==

 

=={{header|Nim}}==

next: Node[T]

data: T

 

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

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

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:

 

loop (my $l = $list; $l; $l.=value) {

say $l.key;

{{out}}

<pre>1

Note how the <tt>[=>]</tt> reduction is also right associative,

just like the base operator.)

augment class Pair {

method traverse () {

 

my $list = [=>] 'Ⅰ' .. 'Ⅻ', Mu;

 

{{out}}

Extending <tt>class Cell</tt> from [[Singly-linked_list/Element_definition#Raku]]:

 

self, *.next ...^ !*

 

Usage:

 

 

for $list.Seq -> $cell {

say $cell.value;

{{out}}

<pre>10

 

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

{{libheader|Wren-llist}}

{{libheader|Wren-fmt}}

 

//create a new linked list and add the first 50 positive integers to it

Fmt.write("$4d ", i)

if (i % 10 == 0) System.print()

 

{{out}}

 

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

 

print

traverseList()

{{out}}

<pre>1000

2000

---Program done, press RETURN---</pre>

 

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