引言
筆者以及介紹了單向鏈表、單向回圈鏈表的基本操作，單鏈表解決了順序表中存在的空間不自由問題，單向回圈鏈表解決了單向鏈表尾插法效率低的問題，但有心的讀者還會發現，在洗掉結點時，我們往往會找待洗掉結點的前繼結點，這為操作細節上增加了一些難度，并且在單向鏈表中只能高效地執行一端的插入，如果希望在兩端都能完成高效插入/洗掉操作，那么則必須改良之前的鏈表設計，本文會著重介紹如何改良單向鏈表，
雙向回圈鏈表
基本操作：
- 判斷鏈表是否為空：同單鏈表
- 獲取鏈表長度：同單鏈表
- 頭部/尾部增加結點：由于增加了前驅/后繼結點，因此在這一步中要注意首尾結點的后繼/前驅結點的設定
- 頭部/尾部彈出結點：根據前驅和后繼結點的特性，可以輕松的完成這個操作（見代碼）
- 指定位置插入元素：在保證position滿足范圍的條件下，當position <= l/2時，利用頭節點向后移動尋找插入位置；當position > l/2時，利用尾節點前移尋找插入位置
- 洗掉指定元素：頭部/尾部結點要單獨判定，同時還要保證指定的元素在鏈表內，其余操作和單鏈表類似
Python實作：
class DoublyListNode():
def __init__(self, val, prev_=None, next_=None):
self.val = val
self.next_ = next_
self.prev_ = prev_
class DoublyLinkedList():
def __init__(self):
self.head = None
self.rear = None
# 判空
def is_empty(self):
return self.head is None
# 向鏈表頭部插入元素
def prepend(self, element):
p = DoublyListNode(element, None, self.head)
if self.is_empty():
self.rear = p
else:
p.next_.prev_ = p
self.head = p
# 向鏈表尾部插入元素
def append(self, element):
p = DoublyListNode(element, self.rear, None)
if self.is_empty():
self.head = p
else:
p.prev_.next_ = p
self.rear = p
# 獲取鏈表長度
def get_length(self):
if self.is_empty():
return 0
cur = self.head
length = 0
while cur:
length += 1
cur = cur.next_
return length
# 彈出頭部結點
def pop_first(self):
if self.is_empty():
raise ValueError('鏈表為空，無法進行操作！')
output = self.head.val
self.head = self.head.next_
if self.head: # 鏈表為空時沒有前繼結點
self.head.prev_ = None
return output
# 彈出尾部結點
def pop_last(self):
if self.is_empty():
raise ValueError('鏈表為空，無法進行操作！')
output = self.rear.val
self.rear = self.rear.prev_
if self.rear:
self.rear.next_ = None
return output
# 在任意位置插入結點
def insert(self, position, element):
l = self.get_length()
if position == 0:
self.prepend(element)
elif position == l-1:
self.append(element)
elif 0 < position < l-1:
if self.is_empty():
raise IndexError('下標越界！')
if position <= l / 2:
cur = self.head
while position > 0:
cur = cur.next_
position -= 1
p = DoublyListNode(element, None, cur)
cur.prev_.next_ = p
else:
cur = self.rear
while position < l-1:
cur = cur.prev_
position += 1
p = DoublyListNode(element, None, cur)
cur.prev_.next_ = p
else:
raise IndexError('下標越界！')
# 洗掉指定元素
def remove(self, element):
if self.is_empty():
raise IndexError('下標越界！')
if self.head.val == element:
self.head = self.head.next_
if self.head:
self.head.prev_ = None
elif self.rear.val == element:
self.rear = self.rear.prev_
if self.rear:
self.rear.next_ = None
else:
cur = self.head
flag = False
while cur and cur.val != element:
cur = cur.next_
if cur and cur.val == element:
flag = True
if flag:
cur.prev_.next_ = cur.next_
else:
raise ValueError('鏈表中不存在該元素！')
if __name__ == '__main__':
def testfunction(node):
nums = []
cur = node
while cur:
nums.append(cur.val)
cur = cur.next_
return nums
sample = DoublyLinkedList()
sample.is_empty()
for i in range(8):
sample.prepend(i)
print(testfunction(sample.head))
sample.pop_first()
print(testfunction(sample.head))
sample.pop_last()
print(testfunction(sample.head))
sample.insert(3, 8)
print(testfunction(sample.head))
sample.remove(4)
print(testfunction(sample.head))
print(sample.get_length())
總結
雙向鏈表的插入/洗掉操作較單向鏈表效率更高，但遺憾地是占用了更多空間以存放指標，
參考資料
- 裘宗燕.資料結構與演算法——Python語言描述[M].北京：機械工業出版社，2015: 92-95，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/168241.html
標籤：其他