定義
雙向鏈表每個節(jié)點有兩個鏈接：一個指向前一個節(jié)點，當此節(jié)點為第一個節(jié)點時，指向空值；而另一個指向下一個節(jié)點，當此節(jié)點為最后一個節(jié)點時，指向空值。
優(yōu)勢
雙向鏈表可以從任何一個節(jié)點訪問前一個節(jié)點，也可以訪問后一個節(jié)點，以至整個鏈表。雙向查找節(jié)點時很便利，一般是在需要大批量的另外儲存數(shù)據(jù)在鏈表中的位置的時候用。
python 實現(xiàn)雙向鏈表
頭部插入節(jié)點
代碼實現(xiàn)
def add(self, value):
"""
頭部插入節(jié)點
"""
node = Node(value)
if self.is_empty():
self._head = node
else:
# 將node的next指向頭節(jié)點
node.next = self._head
# 頭結點的prev指向新節(jié)點
self._head.prev = node
# 將head指向node
self._head = node
尾部插入節(jié)點
代碼實現(xiàn)
def append(self, value):
"""
尾插
"""
node = Node(value)
if self.is_empty():
self._head = node
else:
# 移動到鏈表的尾端
cur = self._head
while cur.next:
cur = cur.next
# 將尾節(jié)點的next指向node
cur.next = node
# 將node的pre指向尾節(jié)點
node.prev = cur
指定位置插入節(jié)點
代碼實現(xiàn)
def insert(self, value, index):
"""
指定位置插入
"""
if index <= 0:
self.add(value)
elif index > (self.length() - 1):
self.append(value)
else:
node = Node(value)
cur = self._head
count = 0
# 移動到指定位置的前一個節(jié)點
while count < (index - 1):
count += 1
cur = cur.next
# 新節(jié)點pre指向上一個節(jié)點
node.prev = cur
# 新節(jié)點的next指向下一個節(jié)點
node.next = cur.next
# 下一個節(jié)點的prev指向node
cur.next.prev = node
# 上一個節(jié)點next指向新節(jié)點
cur.next = node
刪除節(jié)點
代碼實現(xiàn)
def remove(self, value):
"""
刪除節(jié)點
"""
if self.is_empty():
return
else:
cur = self._head
if cur.item == value:
# 如果第一個節(jié)點就是要刪除的元素
if cur.next is None:
self._head = None
else:
# 將第二個節(jié)點的prev指向none
cur.next.prev = None
# head指向第二個節(jié)點
self._head = cur.next
return
while cur:
if cur.item == value:
# 將cur的前一個節(jié)點的next指向后一個節(jié)點
cur.prev.next = cur.next
# 將后一個節(jié)點的prev指向cur前一個節(jié)點
cur.next.prev = cur.prev
break
cur = cur.next
完整代碼
class Node(object):
"""
雙向鏈表節(jié)點實現(xiàn)
"""
def __init__(self, item):
self.prev = None
self.item = item
self.next = None
class DoubleLinkList(object):
def __init__(self):
self._head = None
def is_empty(self):
"""
判斷雙向鏈表是否為空
"""
return self._head is None
def length(self):
"""
雙向鏈表長度
"""
# cur用來移動遍歷節(jié)點
cur = self._head
# count為計數(shù)
count = 0
while cur is not None:
count += 1
cur = cur.next
return count
def traverse(self):
"""
遍歷雙向鏈表
:return:
"""
cur = self._head
while cur is not None:
print(cur.item, end=" ")
cur = cur.next
print("")
def add(self, value):
"""
頭部插入節(jié)點
"""
node = Node(value)
if self.is_empty():
self._head = node
else:
# 將node的next指向頭節(jié)點
node.next = self._head
# 頭結點的prev指向新節(jié)點
self._head.prev = node
# 將head指向node
self._head = node
def append(self, value):
"""
尾插
"""
node = Node(value)
if self.is_empty():
self._head = node
else:
# 移動到鏈表的尾端
cur = self._head
while cur.next:
cur = cur.next
# 將尾節(jié)點的next指向node
cur.next = node
# 將node的pre指向尾節(jié)點
node.prev = cur
def insert(self, value, index):
"""
指定位置插入
"""
if index <= 0:
self.add(value)
elif index > (self.length() - 1):
self.append(value)
else:
node = Node(value)
cur = self._head
count = 0
# 移動到指定位置的前一個節(jié)點
while count < (index - 1):
count += 1
cur = cur.next
# 新節(jié)點pre指向上一個節(jié)點
node.prev = cur
# 新節(jié)點的next指向下一個節(jié)點
node.next = cur.next
# 下一個節(jié)點的prev指向node
cur.next.prev = node
# 上一個節(jié)點next指向新節(jié)點
cur.next = node
def remove(self, value):
"""
刪除節(jié)點
"""
if self.is_empty():
return
else:
cur = self._head
if cur.item == value:
# 如果第一個節(jié)點就是要刪除的元素
if cur.next is None:
self._head = None
else:
# 將第二個節(jié)點的prev指向none
cur.next.prev = None
# head指向第二個節(jié)點
self._head = cur.next
return
while cur:
if cur.item == value:
# 將cur的前一個節(jié)點的next指向后一個節(jié)點
cur.prev.next = cur.next
# 將后一個節(jié)點的prev指向cur前一個節(jié)點
cur.next.prev = cur.prev
break
cur = cur.next
def search(self, item):
"""
查找元素是否存在
"""
cur = self._head
while cur != None:
if cur.item == item:
return True
cur = cur.next
return False
if __name__ == '__main__':
double_link_list = DoubleLinkList()
print("當前鏈表是否為空：", double_link_list.is_empty())
print("當前鏈表長度為：", double_link_list.length())
double_link_list.append(99)
print("當前鏈表是否為空：", double_link_list.is_empty())
print("當前鏈表長度為：", double_link_list.length())
double_link_list.append(23)
double_link_list.append(89)
double_link_list.append("python")
double_link_list.append(12.66)
double_link_list.add(27)
double_link_list.insert(4, 0)
double_link_list.remove(27)
double_link_list.traverse()
print(double_link_list.search(23))
結果
當前鏈表是否為空： True
當前鏈表長度為： 0
當前鏈表是否為空： False
當前鏈表長度為： 1
4 99 23 89 python 12.66
4
True
