#! /usr/bin/env python
# DataStructure Linkedlist

class Node:
    """
    Member Variable:
        1. next
        2. data
    """
    def __init__(self, data):
        self.data = data
        self.next = None

    def __str__(self):
        return "NodeInfo: data=%d, next_id=%d" % (self.data, id(self.next))

class LinkedList:
    """
    Member Variable:
        1.head
        2.cur
    """
    def __init__(self):
        self.head = Node(0)
        self.cur = self.head;

    def __init__(self, data=None):
        if data is not None:
            self.head = Node(1)
            newNode = Node(data)
            self.head.next = newNode
            self.cur = self.head.next
        else :
            self.head = Node(0)        
            self.cur = self.head;

    def __str__(self):
        tmp = "The List has %d nodes.\n" % self.head.data
        Nodetmp = self.head.next
        while Nodetmp is not None:
            tmp += "->%d" % Nodetmp.data
            Nodetmp = Nodetmp.next
        return tmp
        

    def Insert(self, data, pos=-1):
        if pos > self.head.data :
            print "Out of range"
            return
        newNode = Node(data)
        if pos >= 0:
            Nodetmp = self.head.ext
            while pos :
                Nodetmp = Nodetmp.Next
                pos -= 1
            newNode.next = Nodetmp.next
            Nodetmp.next = newNode
        else:
            self.cur.next = newNode
            self.cur = self.cur.next
        self.head.data += 1
            
    def Remove(self, data, pos=0):
        if pos >= self.head.data :
            print "Out of range"
            return
        Nodetmp = self.head    
        beg = pos
        while pos >= 1:
            Nodetmp = Nodetmp.next
            pos -= 1
        while Nodetmp.next is not None:
            if Nodetmp.next.data == data :
                break
            Nodetmp = Nodetmp.next
        Nodetmp.next = Nodetmp.next.next
        self.head.data -= 1
        if beg == self.head.data :
            self.cur = Nodetmp.next
        

    def Find(self, data, pos=0):
        if pos > self.head.data:
            print "Out of range"
            return
        Nodetmp = self.head
        while pos :
            Nodetmp = Nodetmp.next
            pos -= 1
        while Nodetmp.next is not None:
            if Nodetmp.data == data :
                break
            Nodetmp = Nodetmp.next
        return Nodetmp

    def GetLinkSize(self):
        return self.head.data


if __name__ == "__main__" :
    Lst = LinkedList()
    for i in range(10) :
        Lst.Insert(i)
    for i in range(1,10,2) :
        Lst.Insert(i)
    print Lst
    tmp = Lst.Find(3, 10)
    print tmp.next
    Lst.Remove(1, 10)
    print Lst
    Lst.Insert(4)
    print Lst