1.單鏈表的缺點：
公司專注于為企業(yè)提供成都網(wǎng)站設(shè)計、成都網(wǎng)站建設(shè)、微信公眾號開發(fā)、商城網(wǎng)站制作，重慶小程序開發(fā)，軟件按需定制等一站式互聯(lián)網(wǎng)企業(yè)服務(wù)。憑借多年豐富的經(jīng)驗，我們會仔細(xì)了解各客戶的需求而做出多方面的分析、設(shè)計、整合，為客戶設(shè)計出具風(fēng)格及創(chuàng)意性的商業(yè)解決方案，創(chuàng)新互聯(lián)公司更提供一系列網(wǎng)站制作和網(wǎng)站推廣的服務(wù)。
（1）remove操作要從頭到尾遍歷，時間復(fù)雜度是O（n）
（2）只能單向遍歷，不能反向遍歷
2.使用雙鏈表可以克服以上兩個缺點
雙鏈表相對于單鏈表來說，雙鏈表的節(jié)點（Node）多了一個指針：
這樣一來就能指向前一個節(jié)點，而且也可以指向后一個節(jié)點。
同樣root節(jié)點也有一個prev和next，root節(jié)點的next指向head節(jié)點，head節(jié)點的prev指向root節(jié)點，這樣就能實現(xiàn)一個雙端鏈表。
循環(huán)雙端鏈表：
比如要反向遍歷的時候，都是從root節(jié)點作為一個入口，把root節(jié)點的prev反過來指向tail節(jié)點，這樣就能實現(xiàn)從頭向尾節(jié)點遍歷，然后從root節(jié)點的prev反過來指向上一個節(jié)點，對比正向遍歷從next指向下一個節(jié)點，這樣就實現(xiàn)循環(huán)雙端鏈表。
雙鏈表的屬性：
data { root 有個根節(jié)點
maxsize 控制它的最大長度
length 記錄長度的屬性
雙鏈表
method { headnode 獲取頭節(jié)點的方法
tailnode 獲取尾節(jié)點的方法
append 最后添加新節(jié)點
appendleft 在頭節(jié)點前面，根節(jié)點后面添加新節(jié)點
remove 刪除節(jié)點，時間復(fù)雜度為O(1)；
比如，有3個節(jié)點，要刪除中間節(jié)點，就可以讓前面和后面節(jié)點互指，最后再del掉中間的節(jié)點。
iter_node 遍歷節(jié)點的操作
iter_node_reverse 反向遍歷節(jié)點的操作
實現(xiàn)方式：
重慶分公司
重慶分公司
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() #這兩行代碼，用于構(gòu)建一個根節(jié)點，
node.next, node.prev = node, node #這個根節(jié)點是自己指向自己的默認(rèn)是一個閉環(huán)。
self.root = node #把node賦值給根節(jié)點
self.length = 0 #長度屬性默認(rèn)是0，root節(jié)點是不計算在鏈表長度里面的
def __len__(self):
return self.length #返回長度值
def headnode(self): #定義頭節(jié)點
return self.root.next #也就是root節(jié)點的下一個節(jié)點
def tailnode(self): #定義尾節(jié)點
return self.root.prev #也就是root節(jié)點的上一個節(jié)點
"""
假設(shè)有一條幾個節(jié)點的鏈表，插入一個新的節(jié)點前，要先構(gòu)造這個新的節(jié)點，
然后再讓鏈表原來尾節(jié)點的next指向新節(jié)點，并且新節(jié)點的prev指向原來的
尾節(jié)點，root節(jié)點的prev也要指向新節(jié)點，新節(jié)點的next指向root節(jié)點，
這樣就形成了一個閉環(huán)，實現(xiàn)了append新增節(jié)點。
"""
def append(self, value):
if self.maxsize is not None \
and len(self) > self.maxsize: #判斷是否已經(jīng)超長，如果是就報異常。
raise Exception("The LinkedList is Full")
node = Node(value=value) #構(gòu)造新節(jié)點
tailnode = self.tailnode() #尾節(jié)點
tailnode.next = node #尾節(jié)點的next指向新節(jié)點
node.prev = tailnode #新節(jié)點的prev指向尾節(jié)點
node.next = self.root #新節(jié)點的next指向root節(jié)點
self.root.prev = node #root節(jié)點的prev指向新節(jié)點
self.length += 1 #最后將長度+1
def appendleft(self, vlaue):
if self.maxsize is not None \
and len(self) > self.maxsize: #判斷是否已經(jīng)超長，如果是就報異常。
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 #新節(jié)點的next和prev都指向root節(jié)點，形成一個閉環(huán)。
self.root.next = node #同理，將root節(jié)點的next指向新節(jié)點
self.root.prev = node #將root節(jié)點的prev指向新節(jié)點
else: #否則，如果鏈表不是空的話
headnode = self.root.next #定義root節(jié)點的next節(jié)點是鏈表的頭節(jié)點
node.prev = self.root #將新節(jié)點的prev指向root節(jié)點
node.next = headnode #將新節(jié)點的next指向原頭節(jié)點
headnode.prev = node #最后將頭節(jié)點的prev指向新節(jié)點
self.length += 1 #鏈表長度加1
def remove(self, node): #node是要刪除的節(jié)點，是O(1)的時間復(fù)雜度，注意是node不是value
if node is self.root: #如果只有根節(jié)點，啥都不返回
return
else: #否則是非根節(jié)點
node.prev.next = node.next #將要刪除節(jié)點的前一個節(jié)點的next指針指向要刪除節(jié)點的下一個節(jié)點
node.next.prev = node.prev #將要刪除節(jié)點的后一個節(jié)點的prev指針指向要刪除節(jié)點的上一個節(jié)點
self.length -= 1 #鏈表長度-1
return node #返回刪除的節(jié)點
def iter_node(self): #遍歷節(jié)點
if self.root.next is self.root: #防止鏈表是空的
return
curnode = self.root.next #否則，不是空的，從頭開始遍歷
while curnode.next is not self.root: #當(dāng)curnode不是尾節(jié)點
yield curnode #一直把curnode節(jié)點給yield出來
curnode = curnode.next #更新curnode節(jié)點，讓curnode一直往下一個節(jié)點走
yield curnode #最后別忘了把最后一個curnode給yield出來
#因為遍歷到最后一個節(jié)點，但并沒有去yield這個節(jié)點
#當(dāng)while循環(huán)終止時，當(dāng)前curnode已經(jīng)到達(dá)了tailnode節(jié)點，
#所以要把它yield出來才完整。
def iter_node_reverse(self):
if self.root.prev is self.root:
return
curnode = self.root.prev #和正向遍歷相反，這個是tailnode節(jié)點
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() #取頭節(jié)點
assert headnode.value == 0 #斷言頭節(jié)點的值為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]執(zhí)行測試：
# pytest double_link_list.py
平均時間復(fù)雜度：
| 循環(huán)雙端鏈表操作 | 平均時間復(fù)雜度 |
|---|---|
| cdll.append(value) | O(1) |
| cdll.appendleft(value) | O(1) |
| cdll.remove(node)，注意這里參數(shù)是 node | O(1) |
| cdll.headnode() | O(1) |
| cdll.tailnode() | O(1) |
