Singly-linked list/Traversal
From Rosetta Code
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.
Contents |
[edit] ActionScript
See Singly-Linked List (element) in ActionScript
var A:Node;
//...
for(var i:Node = A; i != null; i = i.link)
{
doStuff(i);
}
[edit] Ada
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;
[edit] 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:
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
[edit] 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"
}
}
[edit] C
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
}
[edit] C#
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;
}
[edit] Clojure
(doseq [x xs] (println x)
[edit] Common Lisp
(dolist (x list)
(print x))
Not using builtin list iteration:
(loop for ref = list then (rest ref)
until (null ref)
do (print (first ref)))
[edit] D
Traversal using list defined in Singly-Linked list element - D.
// a is a beginning of a list);
while (a) {
Stdout(a.data) (" -> ");
a = a.next;
}
Or 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;
}
[edit] E
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()
}
[edit] 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
Output:
A B C
[edit] Forth
: 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
[edit] Haskell
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.
[edit] J
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
[edit] Java
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.
[edit] JavaScript
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
[edit] Logo
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
[edit] Objective-C
(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];
}
[edit] OCaml
# let li = ["big"; "fjords"; "vex"; "quick"; "waltz"; "nymph"] in
List.iter print_endline li ;;
big
fjords
vex
quick
waltz
nymph
- : unit = ()
[edit] PicoLisp
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 in both cases:
a "cde" (X Y Z) 999
[edit] Protium
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|
<# 显示列表>...</#><# 运行移位指针向后列表>...</#>
</#>
[edit] 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)
[edit] Python
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,;
Output:
big fjords vex quick waltz nymph
[edit] Ruby
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
a,b,b+,c, a,b,b+,c,
[edit] 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.
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)
[edit] Scheme
(define (traverse seq)
(if (null? seq)
'okay
(traverse (cdr seq))))
[edit] 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
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"
}
[edit] Trith
[1 2 3 4 5] [print] each
[edit] Visual Basic .NET
Private Sub Iterate(ByVal list As LinkedList(Of Integer))
Dim node = list.First
Do Until node Is Nothing
node = node.Next
Loop
End Sub
