Singly-linked list/Traversal: Difference between revisions
(→Java) |
No edit summary |
||
Line 12: | Line 12: | ||
System.out.println(i); |
System.out.println(i); |
||
} |
} |
||
==[[Python]]== |
|||
[[Category: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 implement 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 the code could have seletively passed any node yielded by the iteration to an "Insert" method to selectively insert new values into the list, for example). |
Revision as of 00:18, 31 October 2007
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.
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); }
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 implement 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 the code could have seletively passed any node yielded by the iteration to an "Insert" method to selectively insert new values into the list, for example).