Singly-linked list/Traversal: Difference between revisions
(→Common Lisp: new example) |
No edit summary |
||
Line 153: | Line 153: | ||
Testing code: |
Testing code: |
||
A ' emit walk <em>ABC ok</em> |
A ' emit walk <em>ABC ok</em> |
||
=={{header|Haskell}}== |
|||
Lists are ubiquitous in Haskell, simply use Haskell's <em>map</em> 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 <em>traverse</em> function is polymorphic; denoted by <em>traverse :: [a] -> [a]</em> where <em>a</em> can be of any type. |
|||
=={{header|Java}}== |
=={{header|Java}}== |
Revision as of 02:06, 5 August 2009
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.
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
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 REF STRINGLIST(node) ISNT NIL DO print((value OF node, space)); node := next OF node OD; print((newline))
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>
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>
Common Lisp
<lang lisp>(dolist (x list)
(print x))</lang>
Not using builtin list iteration:
<lang lisp>(loop for ref = list then (rest ref)
until (null ref) do (print (first ref)))</lang>
D
Traversal using list defined in Singly-Linked list element - D. <lang D>
// a is a beginning of a list); while (a) { Stdout(a.data) (" -> "); a = a.next; }
</lang>
Or 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>
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>
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
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.
Java
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.
Logo
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>
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>
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):
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
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+")
- then:
head.each {|value| print value, ","} puts
- or
current = head begin
print current.value, ","
end while current = current.succ puts</lang>
a,b,b+,c, a,b,b+,c,
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...
<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>
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