Singly-linked list/Traversal

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.

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;

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.

Python

Traversal of any sequence in Python can be done using the same generic code:

for i in someList:
   print i

This also works for generators (functions which yield values rather than using return) and for any class that implements an iterator interface (defining a next() method and returning themselves via the special __iter__() method or defining __iter__() as a generator). Examples:

def fib(n):
    """ Fibonacci generator function"""
    x,y = 0,1
    while x < n:
        yield(x)
        x,y = y,x+y

That can be called as:

 for i in fib(20):
    print i

A simple class implementing a linked list and supporting addition, insertion and traversal (via normal Python interation):

class SinglyLinkedList(object):
  class Node(object):
     def __init__(self, item):
        self.value = item
        self.next = None
     def __str__(self):
        return str(self.value)
  def __init__(self):
     self.next = None
  def Add(self, item):
     x = self
     while x.next:
        x = x.next
     x.next = self.Node(item)
  def Insert(self, item, node=None):
     """insert an item into the list after node; or at the head of the list by default"""
     new = self.Node(item)
     if node is None:
        node = self
     if node.next:
         new.next = node.next
     node.next = new
  def __iter__(self):
     x = self
     while x.next:
        yield x.next
        x = x.next

Can be called with code like:

if __name__ == "__main__":
   myList = SinglyLinkedList()
   myList.Add('b')
   myList.Add('c')
   myList.Add('d')
   myList.Insert('a')
   for i in myList:
       # Implicitly calls __iter__ returning a generator
       # object, which supports a .next() method
       print i         # Implicitly calls the __str__ method on each Node

Note that implementing a linked list class such as this is an almost useless programming exercise in Python given that the built-in list and dictionary containers are far more powerful, far faster, and capable of containing arbitrary objects as values (and any hashable object as keys for dictionaries). This implementation lacks slicing, and many list methods such as: .__len__(), .sort(), .reverse(), .pop() etc.

So the only value in this example is for students of other programming languages to get a glimpse into how they could simulate linked lists and similar data structures using Python objects. In practically all conceivable real-world code one would use a normal Python list, create a subclass of the Python list, or write a wrapper class around a list or dictionary. In some cases one might model trees and graphs as objects with link members to other node objects. This code gives a rough approximation of how that can work. For example a binary tree can be modeled as node objects each of which contain, left and right references to other nodes.