5.双链表
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 反向遍历节点的操作
实现方式：
class Node(object):
def __init__(self, value=None, prev=None, next=None):
self.value, self.prev, self.next = value, prev, next
class CircualDoubleLinkedList(object):
def __init__(self, maxsize=None):
self.maxsize = maxsize
node =Node() #这两行代码，用于构建一个根节点，
node.next, node.prev = node, node #这个根节点是自己指向自己的默认是一个闭环。
self.root = node #把node赋值给根节点
self.length = 0 #长度属性默认是0，root节点是不计算在链表长度里面的
def __len__(self):
return self.length #返回长度值
def headnode(self): #定义头节点
return self.root.next #也就是root节点的下一个节点
def tailnode(self): #定义尾节点
return self.root.prev #也就是root节点的上一个节点
"""
假设有一条几个节点的链表，插入一个新的节点前，要先构造这个新的节点，
然后再让链表原来尾节点的next指向新节点，并且新节点的prev指向原来的
尾节点，root节点的prev也要指向新节点，新节点的next指向root节点，
这样就形成了一个闭环，实现了append新增节点。
"""
def append(self, value):
if self.maxsize is not None \
and len(self) > self.maxsize: #判断是否已经超长，如果是就报异常。
raise Exception("The LinkedList is Full")
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 #最后将长度+1
def appendleft(self, vlaue):
if self.maxsize is not None \
and len(self) > self.maxsize: #判断是否已经超长，如果是就报异常。
raise Exception("The LinkedList is Full")
node = Node(value=vlaue)
if self.root.next is self.root: #判断这个链表是空的情况
node.next = self.root
node.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 #链表长度加1
def remove(self, node): #node是要删除的节点，是O(1)的时间复杂度，注意是node不是value
if node is self.root: #如果只有根节点，啥都不返回
return
else: #否则是非根节点
node.prev.next = node.next #将要删除节点的前一个节点的next指针指向要删除节点的下一个节点
node.next.prev = node.prev #将要删除节点的后一个节点的prev指针指向要删除节点的上一个节点
self.length -= 1 #链表长度-1
return node #返回删除的节点
def iter_node(self): #遍历节点
if self.root.next is self.root: #防止链表是空的
return
curnode = self.root.next #否则，不是空的，从头开始遍历
while curnode.next is not self.root: #当curnode不是尾节点
yield curnode #一直把curnode节点给yield出来
curnode = curnode.next #更新curnode节点，让curnode一直往下一个节点走
yield curnode #最后别忘了把最后一个curnode给yield出来
#因为遍历到最后一个节点，但并没有去yield这个节点
#当while循环终止时，当前curnode已经到达了tailnode节点，
#所以要把它yield出来才完整。
def iter_node_reverse(self):
if self.root.prev is self.root:
return
curnode = self.root.prev #和正向遍历相反，这个是tailnode节点
while curnode.prev is not self.root:
yield curnode
curnode = curnode.prev #前移
yield curnode
#单元测试
def test_double_link_list():
dll = CircualDoubleLinkedList()
assert len(dll) == 0
dll.append(0)
dll.append(1)
dll.append(2)
assert list(dll) == [0, 1, 2]
assert [node.value for node in dll.iter_node_reverse()] == [2, 1, 0]
assert [node.value for node in dll.iter_node()] == [0, 1, 2]
headnode = dll.headnode() #取头节点
assert headnode.value == 0 #断言头节点的值为0，因为0是第一个被添加的
dll.remove(headnode) #O(1)
assert len(dll) == 2
assert [node.value for node in dll.iter_node()] == [1, 2]
dll.appendleft(0)
assert [node.value for node in dll.iter_node()] == [0, 1, 2]执行测试：
# pytest double_link_list.py
平均时间复杂度：
| 循环双端链表操作 | 平均时间复杂度 |
|---|---|
| cdll.append(value) | O(1) |
| cdll.appendleft(value) | O(1) |
| cdll.remove(node)，注意这里参数是 node | O(1) |
| cdll.headnode() | O(1) |
| cdll.tailnode() | O(1) |
本文标题：5.双链表
当前URL：http://cdiso.cn/article/pjspci.html
