双链表

上次单链表中有个问题，就是remove 方法有误，在这里已经修正了，下面是双链表的实现。其实，双链表已比较简单，就是在存储节点中加上一个指向上个节点的引用（呵呵，这好像是java的术语） 具体代码如下:

# -*- coding: cp936 -*-
#---------------------------------------------
#                                             
#author  chile                                  
#version  1.0                                
#since                                       
#date                                         
#desc  双链表                                 
#                                             
#                                             
#                                             
#---------------------------------------------
class DoubleLinkList:
    def __init__(self):
        self.root = DoubleLinkList.Entry()
        self.entry = self.root
        self.list = list()
        self.tally = 0
    
    #新增的数据都是插入在尾部
    def add(self,value):
        temp = self.Entry(pre = self.entry,value = value)
        self.entry.next = temp 
        self.entry = temp
        self.tally += 1
    
    #在头部添加
    def addFirst(self,value):
        entry = self.root.next  
        temp = self.Entry(pre = self.root , next = entry,value = value)
        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):
        e = self.root.next
        self.removeEntry(self.root,e, value)
        if self.isRemove:
            self.tally -= 1
                
    def removeEntry(self,pre,current,value):
        self.isRemove = False
        if current == None:
            self.isRemove = False
            return
        if current.value == value:
            pre.next = current.next
            self.isRemove = True
        else:
            self.removeEntry(current,current.next, value)    
            
    def removeFirst(self):
        root = self.root
        entry = root.next;
        root.next = entry.next
        entry.next.pre = root
        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, pre = None , next = None , value = None):
            self.next = next #下一个节点
            self.pre = pre   #上一个节点
            self.value = value #节点存储的值
            
            

link = DoubleLinkList()
link.add(1)
link.add(2)
link.addFirst(3)
link.add(5)
link.add(4)
link.add(7)
link.remove(5)
print link.all(), link.size()
link.addFirst(5)
print link.all(), link.size()
link.removeFirst()
print link.all(), link.size()
print link.getFirst() , link.getLast() , link.get(3)

    水平有限哈，写的比较简单。如果有什么问题，请指正。希望和有兴趣的共同交流。