Singly-linked list/Traversal: Difference between revisions
Content added Content deleted
(→{{header|Java}}: Added extra note about the capabilities of the LinkedList class.) |
(Replace article on iteration with simple transversal code) |
||
Line 40: | Line 40: | ||
==[[Python]]== |
==[[Python]]== |
||
[[Category:Python]] |
[[Category:Python]] |
||
Traversal of any sequence in Python can be done using the same generic code: |
|||
lst is either None (the empty list) or Node connected to the next node. |
|||
for i in someList: |
|||
⚫ | |||
<pre> |
|||
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: |
|||
while lst is not None: |
|||
⚫ | |||
⚫ | |||
</pre> |
|||
For more Pythonic iteration, you can use a genertor function: |
|||
def fib(n): |
|||
<pre> |
|||
""" Fibonacci '''generator''' function""" |
|||
def iternode(lst): |
|||
x,y = 0,1 |
|||
while lst is not None: |
|||
yield lst |
|||
lst = lst.next |
|||
</pre> |
|||
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.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. |
Revision as of 15:47, 4 November 2007
Singly-linked list/Traversal
You are encouraged to solve this task according to the task description, using any language you may know.
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
lst is either None (the empty list) or Node connected to the next node.
while lst is not None: print lst.value lst = lst.next
For more Pythonic iteration, you can use a genertor function:
def iternode(lst): while lst is not None: yield lst lst = lst.next