reverse-travel-linked-list.py

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


class LinkedList:
    def __init__(self):
        self.root = None
        self.first = None

    def add(self, data):
        node = Node(data)
        if self.root is None:
            self.root = node
        else:
            node.next = self.root
            node.next.prev = node
            if not self.first:
                self.first = node.next
            self.root = node
    
    def reset(self):
        self.root = self.first
        return self.root

    def iterate(self, travel, method='next'):
        for i in range(1, int(travel)):
            getattr(self, '_%s' % method)()
        return self.root
    
    def _next(self):
        del self.root.prev, self.root.data
        self.root = self.root.next
    
    def _prev(self):
        del self.root.next, self.root.data
        self.root = self.root.prev


def main():
    travel = int(raw_input())
    list_items = raw_input().split(' ')

    if travel > len(list_items):
        return 'NIL'
    elif travel == len(list_items):
        return list_items[0]
    elif travel == 1:
        return list_items[-1]

    l = LinkedList()
    
    # attempt traversing the list from the other direction to speed up iteration
    if travel > (len(list_items)/2):
        for i in list_items[:travel]:
            l.add(i)
        l.reset()
        travel = len(list_items) - travel + 1
        return l.iterate(travel, method="prev").data
    
    # uses reverse order
    travel = (len(list_items) - travel)
    for i in list_items[travel:]:
        l.add(i)
    return l.reset().data
    #return l.iterate(travel, method="next").data

    
print main()