雙向鏈表是在單向鏈表的基礎(chǔ)上更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)匾浪，其中一個節(jié)點(diǎn)除了含有自身信息外酿雪，還應(yīng)該含有下連接一下個節(jié)點(diǎn)和上一個節(jié)點(diǎn)的信息绒净。
雙向鏈表適用于需要雙向查找節(jié)點(diǎn)值的場景中，在數(shù)據(jù)量難以估計并且數(shù)據(jù)增刪操作頻繁的場景中现使，雙向鏈表有一定優(yōu)勢；鏈表在內(nèi)存中呈現(xiàn)的狀態(tài)是離散的地址塊旷痕，不需要像列表一樣預(yù)先分配內(nèi)存空間碳锈，在內(nèi)存的充分利用上更勝一籌，不過增加了一些額外開銷欺抗。
雙向鏈表結(jié)構(gòu)如圖：
image
定義基本的節(jié)點(diǎn)類和鏈表類：
class Node:
"""節(jié)點(diǎn)類"""
def __init__(self, item):
self.item = item
self.next = None
self.prev = None
class DLinkList:
"""
雙向列表類
"""
def __init__(self):
self.head = None
時間雙向鏈表類的基本屬性：是否為空售碳，鏈表長度、鏈表遍歷绞呈；判斷鏈表是否為空只需要看頭部head是否指向空贸人，鏈表遍歷只需要從頭部到最后一個節(jié)點(diǎn)的下一個節(jié)點(diǎn)指向?yàn)榭盏那闆r，同時鏈表長度也是根據(jù)最后一個節(jié)點(diǎn)的下一個節(jié)點(diǎn)是否指向空來判斷佃声，基本實(shí)現(xiàn)如下：
class Node:
"""節(jié)點(diǎn)類"""
def __init__(self, item):
self.item = item
self.next = None
self.prev = None
class DLinkList:
"""
雙向列表類
"""
def __init__(self):
self._head = None
@property
def is_empty(self):
return None == self._head
@property
def length(self):
if self.is_empty:
return 0
n = 1
cur = self._head
while None != cur.next:
cur = cur.next
n += 1
return n
@property
def ergodic(self):
if self.is_empty:
raise ValueError('ERROR NULL')
cur = self._head
print(cur.item)
while None != cur.next:
cur = cur.next
print(cur.item)
return True
接下來實(shí)現(xiàn)添加節(jié)點(diǎn)相關(guān)的操作艺智，在頭部添加、任意位置添加圾亏、尾部添加十拣，注意在任意插入節(jié)點(diǎn)的時候，需要對節(jié)點(diǎn)進(jìn)行遍歷并計數(shù)志鹃，注意計數(shù)起始是1夭问，而不是0，對應(yīng)的節(jié)點(diǎn)是從第二個節(jié)點(diǎn)開始曹铃。
class Node:
"""節(jié)點(diǎn)類"""
def __init__(self, item):
self.item = item
self.next = None
self.prev = None
class DLinkList:
"""
雙向列表類
"""
def __init__(self):
self._head = None
@property
def is_empty(self):
"""
是否為空
:return:
"""
return None == self._head
@property
def length(self):
"""
鏈表長度
:return:
"""
if self.is_empty:
return 0
n = 1
cur = self._head
while None != cur.next:
cur = cur.next
n += 1
return n
@property
def ergodic(self):
"""
遍歷鏈表
:return:
"""
if self.is_empty:
raise ValueError('ERROR NULL')
cur = self._head
print(cur.item)
while None != cur.next:
cur = cur.next
print(cur.item)
return True
def add(self, item):
"""
在頭部添加節(jié)點(diǎn)
:param item:
:return:
"""
node = Node(item)
if self.is_empty:
self._head = node
else:
node.next = self._head
self._head.prev = node
self._head = node
def append(self, item):
"""
在尾部添加節(jié)點(diǎn)
:return:
"""
if self.is_empty:
self.add(item)
else:
node = Node(item)
cur = self._head
while None != cur.next:
cur = cur.next
cur.next = node
node.prev = cur
def insert(self, index, item):
"""
在任意位置插入節(jié)點(diǎn)
:param index:
:param item:
:return:
"""
if index == 0:
self.add(item)
elif index+1 >= self.length:
self.append(item)
else:
n = 1
node = Node(item)
cur = self._head
while Node != cur.next:
pre = cur
cur = cur.next
if n == index:
break
pre.next = node
node.prev = pre
node.next = cur
cur.prev = node
在實(shí)現(xiàn)較為復(fù)雜的刪除節(jié)點(diǎn)操作和判斷節(jié)點(diǎn)是否存在的方法缰趋。
class Node:
"""節(jié)點(diǎn)類"""
def __init__(self, item):
self.item = item
self.next = None
self.prev = None
class DLinkList:
"""
雙向列表類
"""
def __init__(self):
self._head = None
@property
def is_empty(self):
"""
是否為空
:return:
"""
return None == self._head
@property
def length(self):
"""
鏈表長度
:return:
"""
if self.is_empty:
return 0
n = 1
cur = self._head
while None != cur.next:
cur = cur.next
n += 1
return n
@property
def ergodic(self):
"""
遍歷鏈表
:return:
"""
if self.is_empty:
raise ValueError('ERROR NULL')
cur = self._head
print(cur.item)
while None != cur.next:
cur = cur.next
print(cur.item)
return True
def add(self, item):
"""
在頭部添加節(jié)點(diǎn)
:param item:
:return:
"""
node = Node(item)
if self.is_empty:
self._head = node
else:
node.next = self._head
self._head.prev = node
self._head = node
def append(self, item):
"""
在尾部添加節(jié)點(diǎn)
:return:
"""
if self.is_empty:
self.add(item)
else:
node = Node(item)
cur = self._head
while None != cur.next:
cur = cur.next
cur.next = node
node.prev = cur
def insert(self, index, item):
"""
在任意位置插入節(jié)點(diǎn)
:param index:
:param item:
:return:
"""
if index == 0:
self.add(item)
elif index+1 >= self.length:
self.append(item)
else:
n = 1
node = Node(item)
cur = self._head
while Node != cur:
pre = cur
cur = cur.next
if n == index:
break
pre.next = node
node.prev = pre
node.next = cur
cur.prev = node
def search(self, item):
"""
查找節(jié)點(diǎn)是否存在
:param item:
:return:
"""
if self.is_empty:
raise ValueError("ERROR NULL")
cur = self._head
while None != cur:
if cur.item == item:
return True
cur = cur.next
return False
def deltel(self, item):
"""刪除節(jié)點(diǎn)元素"""
if self.is_empty:
raise ValueError('ERROR NULL')
else:
cur = self._head
while None != cur:
if cur.item == item:
if not cur.prev: # 第一個節(jié)點(diǎn)
if None != cur.next: # 不止一個節(jié)點(diǎn)
self._head = cur.next
cur.next.prev = None
else: # 只有一個節(jié)點(diǎn)
self._head = None
else: # 不是第一個節(jié)點(diǎn)
if cur.next == None: # 最后一個節(jié)點(diǎn)
cur.prev.next = None
else: # 中間節(jié)點(diǎn)
cur.prev.next = cur.next
cur.next.prev = cur.prev
cur = cur.next
注意在刪除節(jié)點(diǎn)的時候要考慮幾種特殊情況:刪除節(jié)點(diǎn)為第一個節(jié)點(diǎn)，并且鏈表只有一個節(jié)點(diǎn)陕见；刪除節(jié)點(diǎn)為第一個節(jié)點(diǎn)并且鏈表長度大于1秘血；刪除節(jié)點(diǎn)是中間節(jié)點(diǎn)；刪除節(jié)點(diǎn)是最后一個節(jié)點(diǎn)淳玩；
image
編輯于 22:23
