1.单链表的缺点：

（1）remove操作要从头到尾遍历，时间复杂度是O（n）

（2）只能单向遍历，不能反向遍历

2.使用双链表可以克服以上两个缺点

双链表相对于单链表来说，双链表的节点（Node）多了一个指针：

这样一来就能指向前一个节点，而且也可以指向后一个节点。

同样root节点也有一个prev和next，root节点的next指向head节点，head节点的prev指向root节点，这样就能实现一个双端链表。

循环双端链表：

比如要反向遍历的时候，都是从root节点作为一个入口，把root节点的prev反过来指向tail节点，这样就能实现从头向尾节点遍历，然后从root节点的prev反过来指向上一个节点，对比正向遍历从next指向下一个节点，这样就实现循环双端链表。

双链表的属性：

data { root 有个根节点

maxsize控制它的最大长度

length 记录长度的属性

双链表

method {headnode获取头节点的方法

tailnode 获取尾节点的方法

append最后添加新节点

appendleft 在头节点前面，根节点后面添加新节点

remove删除节点，时间复杂度为O(1)；

比如，有3个节点，要删除中间节点，就可以让前面和后面节点互指，最后再del掉中间的节点。

iter_node 遍历节点的操作

iter_node_reverse反向遍历节点的操作

实现方式：

classNode(object):def__init__(self,value=None,prev=None,next=None):self.value,self.prev,self.next=value,prev,nextclassCircualDoubleLinkedList(object):def__init__(self,maxsize=None):self.maxsize=maxsizenode=Node()#这两行代码，用于构建一个根节点，node.next,node.prev=node,node#这个根节点是自己指向自己的默认是一个闭环。self.root=node#把node赋值给根节点self.length=0#长度属性默认是0，root节点是不计算在链表长度里面的def__len__(self):returnself.length#返回长度值defheadnode(self):#定义头节点returnself.root.next#也就是root节点的下一个节点deftailnode(self):#定义尾节点returnself.root.prev#也就是root节点的上一个节点"""假设有一条几个节点的链表，插入一个新的节点前，要先构造这个新的节点，然后再让链表原来尾节点的next指向新节点，并且新节点的prev指向原来的尾节点，root节点的prev也要指向新节点，新节点的next指向root节点，这样就形成了一个闭环，实现了append新增节点。"""defappend(self,value):ifself.maxsizeisnotNone\andlen(self)>self.maxsize:#判断是否已经超长，如果是就报异常。raiseException("TheLinkedListisFull")node=Node(value=value)#构造新节点tailnode=self.tailnode()#尾节点tailnode.next=node#尾节点的next指向新节点node.prev=tailnode#新节点的prev指向尾节点node.next=self.root#新节点的next指向root节点self.root.prev=node#root节点的prev指向新节点self.length+=1#最后将长度+1defappendleft(self,vlaue):ifself.maxsizeisnotNone\andlen(self)>self.maxsize:#判断是否已经超长，如果是就报异常。raiseException("TheLinkedListisFull")node=Node(value=vlaue)ifself.root.nextisself.root:#判断这个链表是空的情况node.next=self.rootnode.prev=self.root#新节点的next和prev都指向root节点，形成一个闭环。self.root.next=node#同理，将root节点的next指向新节点self.root.prev=node#将root节点的prev指向新节点else:#否则，如果链表不是空的话headnode=self.root.next#定义root节点的next节点是链表的头节点node.prev=self.root#将新节点的prev指向root节点node.next=headnode#将新节点的next指向原头节点headnode.prev=node#最后将头节点的prev指向新节点self.length+=1#链表长度加1defremove(self,node):#node是要删除的节点，是O(1)的时间复杂度，注意是node不是valueifnodeisself.root:#如果只有根节点，啥都不返回returnelse:#否则是非根节点node.prev.next=node.next#将要删除节点的前一个节点的next指针指向要删除节点的下一个节点node.next.prev=node.prev#将要删除节点的后一个节点的prev指针指向要删除节点的上一个节点self.length-=1#链表长度-1returnnode#返回删除的节点defiter_node(self):#遍历节点ifself.root.nextisself.root:#防止链表是空的returncurnode=self.root.next#否则，不是空的，从头开始遍历whilecurnode.nextisnotself.root:#当curnode不是尾节点yieldcurnode#一直把curnode节点给yield出来curnode=curnode.next#更新curnode节点，让curnode一直往下一个节点走yieldcurnode#最后别忘了把最后一个curnode给yield出来#因为遍历到最后一个节点，但并没有去yield这个节点#当while循环终止时，当前curnode已经到达了tailnode节点，#所以要把它yield出来才完整。defiter_node_reverse(self):ifself.root.previsself.root:returncurnode=self.root.prev#和正向遍历相反，这个是tailnode节点whilecurnode.previsnotself.root:yieldcurnodecurnode=curnode.prev#前移yieldcurnode#单元测试deftest_double_link_list():dll=CircualDoubleLinkedList()assertlen(dll)==0dll.append(0)dll.append(1)dll.append(2)assertlist(dll)==[0,1,2]assert[node.valuefornodeindll.iter_node_reverse()]==[2,1,0]assert[node.valuefornodeindll.iter_node()]==[0,1,2]headnode=dll.headnode()#取头节点assertheadnode.value==0#断言头节点的值为0，因为0是第一个被添加的dll.remove(headnode)#O(1)assertlen(dll)==2assert[node.valuefornodeindll.iter_node()]==[1,2]dll.appendleft(0)assert[node.valuefornodeindll.iter_node()]==[0,1,2]

执行测试：

#pytestdouble_link_list.py

平均时间复杂度：