目錄:
1.雙向鏈表的定義
2.雙向鏈表的圖解
3.雙向鏈表定義操作
4.雙向鏈表的實(shí)現(xiàn)
1.雙向鏈表的定義
每個(gè)節(jié)點(diǎn)有兩個(gè)鏈接：一個(gè)指向前一個(gè)節(jié)點(diǎn)，當(dāng)此節(jié)點(diǎn)為第一個(gè)節(jié)點(diǎn)時(shí)，指向空值裙士；而另一個(gè)指向下一個(gè)節(jié)點(diǎn)第股，當(dāng)此節(jié)點(diǎn)為最后一個(gè)節(jié)點(diǎn)時(shí)薪贫，指向空值
2.雙向鏈表的圖解
雙向鏈表.jpg
3.雙向鏈表定義操作
is_empty() 鏈表是否為空
length() 鏈表長度
travel() 遍歷整個(gè)鏈表
add(item) 鏈表頭部添加元素
append(item) 鏈表尾部添加元素
insert(pos, item) 指定位置添加元素
remove(item) 刪除節(jié)點(diǎn)
search(item) 查找節(jié)點(diǎn)是否存在
4.雙向鏈表的實(shí)現(xiàn)
4.1 結(jié)點(diǎn)的實(shí)現(xiàn)
class DoubleNode(object):
"""雙向鏈表節(jié)點(diǎn)"""
def __init__(self, item):
self.item = item
self.next = None
self.prev = None
4.2 雙向鏈表的實(shí)現(xiàn)
鏈表初始化：
class DoubleLinkList(object):
"""雙向鏈表"""
def __init__(self):
self._head = None
插入元素：
# 頭插法
def add(self, item):
node = DoubleNode(item)
if self.is_empty():
# 如果是空鏈表，將_head指向node
self._head = node
else:
# 將node的next指向_head的頭節(jié)點(diǎn)
node.next = self._head
# 將_head的頭節(jié)點(diǎn)的prev指向node
self._head.prev = node
# 將_head 指向node
self._head = node
# 尾插法
def append(self, item):
node = DoubleNode(item)
if self.is_empty():
# 如果是空鏈表，將_head指向node
self._head = node
else:
# 移動到鏈表尾部
cur = self._head
while cur.next != None:
cur = cur.next
# 將尾節(jié)點(diǎn)cur的next指向node
cur.next = node
# 將node的prev指向cur
node.prev = cur
# 任意位置插入
def insert(self, pos, item):
if pos <= 0:
self.add(item)
elif pos > (self.length()-1):
self.append(item)
else:
node = DoubleNode(item)
cur = self._head
count = 0
# 移動到指定位置的前一個(gè)位置
while count < (pos-1):
count += 1
cur = cur.next
# 將node的prev指向cur
node.prev = cur
# 將node的next指向cur的下一個(gè)節(jié)點(diǎn)
node.next = cur.next
# 將cur的下一個(gè)節(jié)點(diǎn)的prev指向node
cur.next.prev = node
# 將cur的next指向node
cur.next = node
鏈表元素的遍歷：
# 判斷鏈表是否為空
def is_empty(self):
return self._head == None
#返回鏈表長度
def length(self):
cur = self._head
count = 0
while cur != None:
count += 1
cur = cur.next
return count
#遍歷整個(gè)鏈表
def travel(self):
cur = self._head
while cur != None:
print(cur.item,end=' ')
cur = cur.next
print("")
結(jié)點(diǎn)刪除和查找
#刪除結(jié)點(diǎn)
def remove(self, item):
if self.is_empty():
return
else:
cur = self._head
if cur.item == item:
# 如果首節(jié)點(diǎn)的元素即是要?jiǎng)h除的元素
if cur.next == None:
# 如果鏈表只有這一個(gè)節(jié)點(diǎn)
self._head = None
else:
# 將第二個(gè)節(jié)點(diǎn)的prev設(shè)置為None
cur.next.prev = None
# 將_head指向第二個(gè)節(jié)點(diǎn)
self._head = cur.next
return
while cur != None:
if cur.item == item:
# 將cur的前一個(gè)節(jié)點(diǎn)的next指向cur的后一個(gè)節(jié)點(diǎn)
cur.prev.next = cur.next
# 將cur的后一個(gè)節(jié)點(diǎn)的prev指向cur的前一個(gè)節(jié)點(diǎn)
cur.next.prev = cur.prev
break
cur = cur.next
#結(jié)點(diǎn)查找，返回bool值
def search(self, item):
cur = self._head
while cur != None:
if cur.item == item:
return True
cur = cur.next
return False
4.3測試
if __name__ == "__main__":
dll = DoubleLinkList()
print(dll.is_empty())
dll.add(1)
print(dll.is_empty())
dll.travel()
dll.add(2)
dll.append(3)
print(dll.is_empty())
dll.travel()
dll.insert(2, 4)
dll.travel()
print("length:{}".format(dll.length()))
print(dll.search(3))
print(dll.search(5))
dll.remove(1)
print("length:{}".format(dll.length()))
dll.travel()
# 運(yùn)行結(jié)果
True
False
1
False
2 1 3
2 1 4 3
length:4
True
False
length:3
2 4 3
