链表是一种比较基础的数据结构，通过顺序连接的方式存储数据。链表有单链表，双向链表，循环链表等。
对于单链表，其每个节点存储了节点元素值和下一个邻接节点的指针，通过交替指向下一个节点可以遍历整个链表。
class IList: __metaclass__=ABCMeta @abstractmethod def Insert(self,index,element):pass @abstractmethod def Update(self,index,element):pass @abstractmethod def Delete(self,element):pass @abstractmethod def GetData(self,index):pass @abstractproperty def Length(self):pass @abstractmethod def Find(self,element):pass @abstractproperty def IsEmpty(self):pass @abstractmethod def Sort(self):pass @abstractmethod def Display(self):pass
IList定义了链表的基本操作
from IList import IList from Node import Node ''' 单链表 ''' class SingleLinkList(IList): def __init__(self): self.__current=None self.__end=None self.__head=None self.__size=0 ''' location index node ''' def __locationNode(self,index): if(index==None): self.__current=self.__end return self.__current=self.__head while(self.__current and index>0): self.__current=self.__current.Next index-=1 def Insert(self,index=None,element=None): self.__locationNode(index) node=Node(element) #list have no node if(self.__size==0): self.__current=self.__end=self.__head=node else: #new node's next node is current's next node.Next=self.__current.Next #new node's previous node is current node self.__current.Next=node #insert at end of list,End need move on if(self.__current==self.__end): self.__end=self.__end.Next #increases size self.__size+=1 def Update(self,index,element): self.__locationNode(index) self.__current.Element=element def Delete(self,element): if(self.IsEmpty()): return True #only one node if(self.__head==self.__end and self.__head.Element==element): self.__head=self.__end=None return True #more than two nodes node = self.__head lnode = node.Next while(lnode): if(lnode.Element==element): node.Next=node.Next.Next lnode = node.Next self.__size-=1 else: node=lnode lnode=node.Next self.__end=node #check first node if(self.__head.Element==element): if(self.__head.Next): self.__head=self.__head.Next else: self.__head=self.__end=self.__current=None self.__size-=1 def GetData(self,index): self.__locationNode(index) return self.__current.Element def Length(self): return self.__size def Find(self,element): node=self.__head index=0 while(node): if(node.Element==element):return index index+=1 node=node.Next return -1 def IsEmpty(self): if(self.__size==0):return True else:return False def Sort(self): temp=self.Display() from Algorithm.Sort import quicksort quicksort(temp,0,len(temp)-1) node=self.__head i=0 while(node): node.Element=temp[i] node=node.Next i+=1 def Display(self): node=self.__head temp=[] while(node): temp.append(node.Element) node=node.Next return temp
调用
from LinkList import SingleLinkList if __name__ == "__main__": #single linknode sinLList=SingleLinkList() sinLList.Insert(element=6) sinLList.Insert(element=13) sinLList.Insert(element=6) sinLList.Insert(element=0) print sinLList.Display() print '%s position %s in linklist'%(sinLList.Find(element=13),13) sinLList.Update(1, 15) print '%s position %s in linklist'%(1,sinLList.GetData(1)) sinLList.Sort() print 'after sort:%s'%sinLList.Display() sinLList.Delete(6) print sinLList.Display() output：[6, 13, 6, 0] 1 position 13 in linklist 1 position 15 in linklist after sort:[0, 6, 6, 15] [0, 15]
对于单链表的遍历的时间复杂度在O(N)，最坏的情况是需要操作的节点刚好位End指向的节点上，必须用head循环到尾部进行操作。所以，基于这样的情况，双向链表可以很好的解决这个问题，双向链表中的每个节点包含了元素值，邻接节点的上一个节点指针、下一个节点指针，这样遍历即可前向，也可后向。
...