Singly-linked list/Traversal

From Rosetta Code
< Singly-linked list
Revision as of 03:59, 2 July 2015 by rosettacode>Ajcord (→‎{{header|Axe}}: Using new constructor and helper functions)
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

The standard list data type is a singly linked list. <lang Lisp>(defun traverse (xs) 

  (if (endp xs)
      (cw "End.~%")
      (prog2$ (cw "~x0~%" (first xs))
              (traverse (rest xs)))))</lang>

ActionScript

See Singly-Linked List (element) in ActionScript <lang ActionScript>var A:Node; //... for(var i:Node = A; i != null; i = i.link) { doStuff(i); }</lang>

Ada

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

<lang ada>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;</lang>

ALGOL 68

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: <lang algol68>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)</lang>

Output:
Big fjords vex quick waltz nymph

AutoHotkey

<lang AutoHotkey>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"
 }

}</lang>

Axe

<lang axe>LINK(L₁,1)→A LINK(L₁+10,1)→B LINK(L₁+50,1)→C

INSERT(A,B) INSERT(A,C)

A→I While I≠0 

Disp VALUE(I)▶Dec,i
NEXT(I)→I

End</lang>

BBC BASIC

Works with: BBC BASIC for Windows

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

</lang>

Output:
Traverse list:
       123
       456
       789

C

See Singly-Linked List (element) in C. <lang c>struct link *first; // ... struct link *iter; for(iter = first; iter != NULL; iter = iter->next) { 

 // access data, e.g. with iter->data

}</lang>

C#

Simple iteration with a while loop. <lang csharp>//current is the first Link in the list while(current != null){ 

   System.Console.WriteLine(current.item);
   current = current.next;

}</lang>

Clojure

<lang lisp>(doseq [x xs] (println x))</lang>

Common Lisp

<lang lisp>(dolist (x list) 

 (print x))</lang>

Using LOOP:

<lang lisp>(loop for x in list do (print x))</lang>

Using MAPC

<lang lisp>(mapc #'print list)</lang>

Using MAP

<lang lisp>(map nil #'print list)</lang>


Not using builtin list iteration:

<lang lisp>(loop for ref = list then (rest ref) 

     until (null ref)
     do (print (first ref)))</lang>

D

<lang d>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();

}</lang>

Output:
1 2 3 4

Alternative Version

Using tango's collections (written by Doug Lea, ported to D): <lang 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;

}</lang>

Delphi

<lang delphi>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;</lang>

E

Using a list made from tuples: <lang e>var linkedList := [1, [2, [3, [4, [5, [6, [7, null]]]]]]]

while (linkedList =~ [value, next]) { 

   println(value)
   linkedList := next

}</lang>

Using a list made from the structure defined at Singly-Linked List (element): <lang e>var linkedList := makeLink(1, makeLink(2, makeLink(3, empty)))

while (!(linkedList.null())) { 

   println(linkedList.value())
   linkedList := linkedList.next()

}</lang>

Ela

<lang ela>traverse [] = [] traverse (x::xs) = x :: traverse xs</lang>

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:

<lang ela>xs = [& x \\ x <- [1..1000]]//lazy list

traverse xs</lang>

Erlang

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

<lang factor>: 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</lang>

Output:
A
B
C

Fantom

Using the definitions from Singly-Linked_List_(element_insertion): <lang fantom> // traverse the linked list 

   Node? current := a
   while (current != null)
   {
     echo (current.value)
     current = current.successor
   }</lang>

Forth

<lang forth>: last ( list -- end ) 

 begin dup @ while @ repeat ;</lang>

And here is a function to walk a list, calling an XT on each data cell: <lang forth>: walk ( a xt -- ) 

  >r begin ?dup while
    dup cell+ @ r@ execute
  @ repeat r> drop ;</lang>

Testing code: 

A ' emit walk ABC ok

Fortran

Fortran 95. See Singly-Linked List (element) in Fortran. <lang 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</lang> Print data from all nodes of a singly-linked list: <lang fortran>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</lang>

Go

See Singly-Linked List (element) in Go. <lang 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)

}</lang>

Haskell

Lists are ubiquitous in Haskell, simply use Haskell's map library function: <lang haskell>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</lang>

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

Icon and Unicon

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

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

end</lang> Prints the numbers 1, 2, 3 in turn.

J

Using the implementation mentioned at Singly-Linked List (element) in J, we can apply a function foo to each node the following way: <lang J>foo"0 {:"1 list</lang>

Java

Works with: Java version 1.5+

For Java.util.LinkedList<T>, use a for each loop (from Loop Structures): <lang java>LinkedList<Type> list = new LinkedList<Type>();

for(Type i: list){ 

 //each element will be in variable "i"
 System.out.println(i);

}</lang> Note that java.util.LinkedList can also perform as a stack, queue, or doubly-linked list.

JavaScript

Extending Singly-Linked_List_(element)#JavaScript <lang 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();</lang> Uses the print() function from Rhino

jq

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: <lang jq>def test_list: 

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

</lang>

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.

LAST is already a Logo built-in, but it could be defined this way: <lang logo>to last :list 

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

end</lang>

Logtalk

The built-in list type can be viewed as a singly linked list. Traversing can be trivially done using a tail-recursive predicate: <lang logtalk>

- object(singly_linked_list).
   :- public(show/0).

   show :-
       traverse([1,2,3]).

   traverse([]).
   traverse([Head| Tail]) :-
       write(Head), nl,
       traverse(Tail).
- end_object.

</lang>

Output:

<lang text> | ?- singly_linked_list::show. 1 2 3 yes </lang>

Mathematica

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

MATLAB / Octave

Matlab and Octave do not have pointers. Linked lists are implemented as vectors (i.e. arrays of size 1xN) <lang Matlab>list = 1:10; 

   for k=1:length(list)
       printf('%i\n',list(k))	
   end; </lang>

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

<lang Matlab> printf('%d\n', list(:)); </lang>

NewLISP

<lang NewLISP>(dolist (x '(a b c d e)) 

 (println x))</lang>

Nim

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

Objeck

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

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

}; </lang>

Objective-C

(See Singly-Linked List (element)) <lang objc>RCListElement *current; for(current=first_of_the_list; current != nil; current = [current next] ) { 

 // to get the "datum":
 // id dat_obj = [current datum];

}</lang>

OCaml

<lang ocaml># let li = ["big"; "fjords"; "vex"; "quick"; "waltz"; "nymph"] in 

 List.iter print_endline li ;;

big fjords vex quick waltz nymph - : unit = ()</lang>

Oforth

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

<lang Oforth>func: testLink { LinkedList new($A, null) dup add($B) dup add($C) } testLink apply(#println)</lang>

Output:
A
C
B

ooRexx

See Singly-Linked List/Element Definition in ooRexx for the full class definition. <lang ooRexx> 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

</lang>

Pascal

See Delphi

Perl 6

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: <lang perl6>my $list = 1 => 2 => 3 => 4 => 5 => 6 => Mu;

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

   say $l.key;

}</lang>

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.) <lang perl6>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;</lang>

Output:
Ⅰ Ⅱ Ⅲ Ⅳ Ⅴ Ⅵ Ⅶ Ⅷ Ⅸ Ⅹ Ⅺ Ⅻ

PicoLisp

We might use map functions <lang PicoLisp>(mapc println '(a "cde" (X Y Z) 999))</lang> or flow control functions <lang PicoLisp>(for X '(a "cde" (X Y Z) 999) 

  (println X) )</lang>
Output:

for both cases 

a
"cde"
(X Y Z)
999

PL/I

<lang pli>*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;</lang>
Output:
  1 Walter
  2 Pachl
  3 wrote
  4 this

Protium

This makes a list of the Chinese Public Holiday and lists them first till last and then last till first. <lang html><@ 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>...</@> </@></lang> This variable length Simplified Chinese rendition of the same code is <lang html><# 指定构造列表字串>public holidays|開國紀念日^和平紀念日^婦女節、兒童節合併假期^清明節^國慶日^春節^端午節^中秋節^農曆除夕</#> <# 忽略>From First to Last</#> <# 迭代迭代次数结构大小列表字串>public holidays| <# 显示列表>...</#><# 运行移位指针向前列表>...</#> </#> <# 忽略>From Last to First (pointer is still at end of list)</#> <# 迭代迭代次数结构大小列表字串>public holidays| <# 显示列表>...</#><# 运行移位指针向后列表>...</#> </#></lang>

PureBasic

<lang PureBasic>Procedure traverse(*node.MyData) 

 While *node
   ;access data, i.e. PrintN(Str(*node\Value)) 
   *node = *node\next
 Wend

EndProcedure

called using

traverse(*firstnode.MyData)</lang>

Python

<lang python>for node in lst: 

   print node.value</lang>

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. <lang python>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</lang>

Output:
big fjords vex quick waltz nymph

Racket

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>

  1. 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)) </lang>

Retro

<lang Retro>: traverse ( l- ) repeat @ 0; again ;</lang> Or, using combinators: <lang Retro>last [ drop ] ^types'LIST each@</lang> With combinators you can also perform an operation on each element in a linked list: <lang Retro>last [ @d->name puts space ] ^types'LIST each@</lang>

REXX

<lang rexx>/*********************************************************************

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

Ruby

referring to Singly-Linked List (element)#Ruby and Singly-Linked List (element insertion)#Ruby <lang ruby>head = ListNode.new("a", ListNode.new("b", ListNode.new("c"))) head.insertAfter("b", "b+")

  1. then:

head.each {|node| print node.value, ","} puts

  1. or

current = head begin 

 print current.value, ","

end while current = current.succ puts</lang>

Output:
a,b,b+,c,
a,b,b+,c,

Run BASIC

<lang runbasic>list$ = "now is the time for all good men" for lnk = 1 to 8 

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

next lnk</lang>

Output:
1->now
2->is
3->the
4->time
5->for
6->all
7->good
8->men

Scala

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. <lang scala>def traverse1[T](xs: Seq[T]): Unit = xs match { 

 case s if s.isEmpty => ()                    
 case _ => { Console.println(xs.head);        
             traverse1(xs.tail)
 }

}</lang>

<lang scala>def traverse2[T](xs: Seq[T]) = for (x <- xs) Console.println(x)</lang>

Scheme

<lang scheme>(define (traverse seq func) 

 (if (null? seq)
     '()
     (begin
       (func (car seq))
       (traverse (cdr seq) func))))</lang>

Tcl

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

<lang tcl>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]
       }
   }

}</lang> Now, a demonstration... <lang tcl>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"

}</lang>

Trith

<lang trith>[1 2 3 4 5] [print] each</lang>

Visual Basic .NET

<lang vbnet>Private Sub Iterate(ByVal list As LinkedList(Of Integer)) 

   Dim node = list.First
   Do Until node Is Nothing
       node = node.Next
   Loop
   End Sub</lang>

Wart

<lang wart>each x '(1 2 3) 

 prn x</lang>

XPL0

<lang XPL0>repeat Node:= Node(0) until Node=0</lang>

zkl

<lang zkl>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()</lang>

Retrieved from "https://rosettacode.org/wiki/Singly-linked_list/Traversal?oldid=40136"