您好,登錄后才能下訂單哦!
本篇內(nèi)容介紹了“python如何實(shí)現(xiàn)雙鏈表”的有關(guān)知識,在實(shí)際案例的操作過程中,不少人都會遇到這樣的困境,接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧!希望大家仔細(xì)閱讀,能夠?qū)W有所成!
實(shí)現(xiàn)雙鏈表需要注意的地方
1、如何插入元素,考慮特殊情況:頭節(jié)點(diǎn)位置,尾節(jié)點(diǎn)位置;一般情況:中間位置
2、如何刪除元素,考慮特殊情況:頭結(jié)點(diǎn)位置,尾節(jié)點(diǎn)位置;一般情況:中間位置
1.構(gòu)造節(jié)點(diǎn)的類和鏈表類
class Node: def __init__(self, data): self.data = data self.next = None self.previous = None class DoubleLinkList: '''雙鏈表''' def __init__(self, node=None): self._head = node
以下方法均在鏈表類中實(shí)現(xiàn)
2. 判斷鏈表是否為空
def is_empty(self): return self._head is None
3. 輸出鏈表的長度
def length(self): count = 0 if self.is_empty(): return count else: current = self._head while current is not None: count += 1 current = current.next return count
4. 遍歷鏈表
def travel(self): current = self._head while current is not None: print("{0}".format(current.data), end=" ") current = current.next print("")
5.頭插法增加新元素
def add(self, item): node = Node(item) # 如果鏈表為空,讓頭指針指向當(dāng)前節(jié)點(diǎn) if self.is_empty(): self._head = node # 注意插入的順序, else: node.next = self._head self._head.previous = node self._head = node
6. 尾插法增加新元素
def append(self, item): node = Node(item) # 如果鏈表為空,則直接讓頭指針指向該節(jié)點(diǎn) if self.is_empty(): self._head = node # 需要找到尾節(jié)點(diǎn),然后讓尾節(jié)點(diǎn)的與新的節(jié)點(diǎn)進(jìn)行連接 else: current = self._head while current.next is not None: current = current.next current.next = node node.previous = current
7. 查找元素是否存在鏈表中
def search(self, item): current = self._head found = False while current is not None and not found: if current.data == item: found = True else: current = current.next return found
8. 在某個(gè)位置中插入元素
def insert(self, item, pos): # 特殊位置,在第一個(gè)位置的時(shí)候,頭插法 if pos <= 0: self.add(item) # 在尾部的時(shí)候,使用尾插法 elif pos > self.length() - 1: self.append(item) # 中間位置 else: node = Node(item) current = self._head count = 0 while count < pos - 1: current = current.next count += 1 # 找到了要插入位置的前驅(qū)之后,進(jìn)行如下操作 node.previous = current node.next = current.next current.next.previous = node current.next = node
# 換一個(gè)順序也可以進(jìn)行 def insert2(self, item, pos): if pos <= 0: self.add(item) elif pos > self.length() - 1: self.append(item) else: node = Node(item) current = self._head count = 0 while count < pos: current = current.next count += 1 node.next = current node.previous = current.previous current.previous.next = node current.previous = node
9. 刪除元素
def remove(self, item): current = self._head if self.is_empty(): return elif current.data == item: # 第一個(gè)節(jié)點(diǎn)就是目標(biāo)節(jié)點(diǎn),那么需要將下一個(gè)節(jié)點(diǎn)的前驅(qū)改為None 然后再將head指向下一個(gè)節(jié)點(diǎn) current.next.previous = None self._head = current.next else: # 找到要?jiǎng)h除的元素節(jié)點(diǎn) while current is not None and current.data != item: current = current.next if current is None: print("not found {0}".format(item)) # 如果尾節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn),讓前驅(qū)節(jié)點(diǎn)指向None elif current.next is None: current.previous.next = None # 中間位置,因?yàn)槭请p鏈表,可以用前驅(qū)指針操作 else: current.previous.next = current.next current.next.previous = current.previous
# 第二種寫法 def remove2(self, item): """刪除元素""" if self.is_empty(): return else: cur = self._head if cur.data == item: # 如果首節(jié)點(diǎn)的元素即是要?jiǎng)h除的元素 if cur.next is 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 is not None: if cur.data == 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
10. 演示
my_list = DoubleLinkList() print("add操作") my_list.add(98) my_list.add(99) my_list.add(100) my_list.travel() print("{:#^50}".format("")) print("append操作") my_list.append(86) my_list.append(85) my_list.append(88) my_list.travel() print("{:#^50}".format("")) print("insert2操作") my_list.insert2(66, 3) my_list.insert2(77, 0) my_list.insert2(55, 10) my_list.travel() print("{:#^50}".format("")) print("insert操作") my_list.insert(90, 4) my_list.insert(123, 5) my_list.travel() print("{:#^50}".format("")) print("search操作") print(my_list.search(100)) print(my_list.search(1998)) print("{:#^50}".format("")) print("remove操作") my_list.remove(56) my_list.remove(123) my_list.remove(77) my_list.remove(55) my_list.travel() print("{:#^50}".format("")) print("remove2操作") my_list.travel() my_list.remove2(100) my_list.remove2(99) my_list.remove2(98) my_list.travel()
“python如何實(shí)現(xiàn)雙鏈表”的內(nèi)容就介紹到這里了,感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注億速云網(wǎng)站,小編將為大家輸出更多高質(zhì)量的實(shí)用文章!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。