python实现单链表

学过数据结构的都知道，单链表是一种简单的数据结构，很常用。如果学会使用单链表后，在学双向链表，就很容易上手。在高级语言中，集合有的就是用双链表实现的。今天，我先完成单链表的实现，以后在写其他的。 如果有差错，请指正。

# -*- coding: cp936 -*-
#---------------------------------------------
#                                           
#author chile                             
#version 1.0                                
#date 2014-02-12                                     
#desc  单链表集合                        
#                                           
#                                             
#---------------------------------------------

class LinkList:
    def __init__(self):
        self.root = LinkList.Entry()
        self.entry = self.root
        self.list = list()
        self.tally = 0
    
    #新增的数据都是插入在尾部
    def add(self,value):
        temp = self.Entry(value = value)
        self.entry.next = temp 
        self.entry = temp
        self.tally += 1
    
    #在头部添加
    def addFirst(self,value):
        temp = self.Entry(value = value)
        entry = self.root.next #获取头部的第一个节点
        temp.next = entry      #新增节点下一个节点指向当前第一个节点
        self.root.next = temp  #将头部指向新增的节点
        self.tally += 1
        
    def get(self,index):
        if index > self.tally or index < 0:
            return  #其实应该抛出异常
        mid = self.tally / 2
        e = self.root.next
        if index < mid:
            for i in range(index):
                e = e.next  
        else:
            for i in range(self.tally):
                if (i == index):
                    break
                e = e.next  
        return e.value
    
    def getLast(self):
        return self.entry.value
    
    def getFirst(self):
        return self.root.next.value
    
    def remove(self,value):
        _temp = self.root.next
        if _temp.value == value:
            self.root.next = _temp.next
            self.tally -= 1
            
    def removeFirst(self):
        root = self.root
        entry = root.next;
        root.next = entry.next 
        self.tally -= 1
    
    def size(self):
        return self.tally
    
    def all(self):
        self.list = list()
        self.iterator(self.root.next)
        return self.list
    
    def iterator(self,entry):
        if entry != None:
            self.list.append(entry.value)
            self.iterator(entry.next)
            
    #内部类 用于存放节点的值，以及下个点的引用
    class Entry:
        def __init__(self, next = None , value = None):
            self.next = next
            self.value = value
        

link = LinkList()
link.add(1)
link.add(2)
link.addFirst(3)
link.add(5)
link.add(4)
link.add(7)

print link.all()
link.removeFirst()
print link.all()
print link.size()
print link.get(1)
print link.get(4)

print link.all()
print link.getFirst()
print link.getLast()