gistfile1.py

#! /usr/bin/env python3
# Released under MIT License.
# Linked list implementation after reading this
# http://www.rethinkdb.com/blog/2010/06/will-the-real-programmers-please-stand-up/

import sys

class Node:
    def __init__(self, value):
        self.next = None
        self.value = value

class LinkedList:
    def __init__(self):
        self.root = None
        self.last = None
    def add(self, n):
        if self.last is None:
            self.root = n
            self.last = n
        else:
            self.last.next = n
            self.last = n
    def walk(self):
        root = self.root
        while root:
            yield root.value
            root = root.next
    def reverse(self):
        curr = self.root
        next = None
        prev = None
        while curr:
            next = curr.next
            curr.next = prev
            prev = curr
            curr = next
        self.root = prev
    @staticmethod
    def make(it):
        ll = LinkedList()
        for elt in it:
            ll.add(Node(elt))
        return ll            

def test(s='Hello World'):
    ll = LinkedList.make(s)
    t = ''.join(ll.walk())
    assert s == t
    ll.reverse()
    t = ''.join(ll.walk())
    assert ''.join(reversed(s)) == t

test()