建站
咨詢
售后
建站咨詢
新聞中心
這里有您想知道的互聯(lián)網(wǎng)營(yíng)銷解決方案
創(chuàng)新互聯(lián)Python教程：python雙向鏈表的概念介紹
說(shuō)明
1、更復(fù)雜的鏈表是雙向鏈表或雙面鏈表。每個(gè)節(jié)點(diǎn)有兩個(gè)鏈接:一個(gè)指向前一個(gè)節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)是第一個(gè)。
2、一個(gè)節(jié)點(diǎn)指向空值，另一個(gè)指向下一個(gè)節(jié)點(diǎn)，當(dāng)該節(jié)點(diǎn)指向最后一個(gè)節(jié)點(diǎn)時(shí)指向空值。
操作方法
is_empty()鏈表是否為空。
length(鏈表長(zhǎng)度。
travel)經(jīng)歷鏈表。
添加add(item)鏈表頭部。
添加到append(item)鏈表的尾部。
添加insert(pos、item)指定位置。
remove刪除節(jié)點(diǎn)。
搜索節(jié)點(diǎn)是否存在。
實(shí)例
class Node(object): def __init__(self, elem): """ :param elem: 表元素域 next：下一結(jié)點(diǎn)鏈接域 cursor(cur)：游標(biāo) """ self.elem = elem # 定義next指向空 self.next = None # 定義next指向空 self.prev = None class DoubleLinkList(object): """ 一種更復(fù)雜的鏈表是“雙向鏈表"或“雙面鏈表"。每個(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í)，指向空值。 """ def __init__(self, node=None): self._head = node # node.elem node.next def is_empty(self): """鏈表是否為空 """ return self._head is None def length(self): """鏈表長(zhǎng)度""" # cur游標(biāo)，用來(lái)移動(dòng)遍歷節(jié)點(diǎn) cur = self._head count = 0 while cur is not None: count += 1 cur = cur.next # count 記錄數(shù)量 return count def travel(self): """遍歷整個(gè)鏈表""" cur = self._head while cur is not None: print(cur.elem, end=' ') cur = cur.next def add(self, item): """鏈表頭部添加元素：頭插法""" node = Node(item) # node的next指向_head node.next = self._head # _head指向新節(jié)點(diǎn) self._head = node node.next.prev = node def append(self, item): """鏈表尾部添加元素:尾插法""" node = Node(item) # 下一結(jié)點(diǎn)鏈接域不為空 if self.is_empty(): self._head = node else: cur = self._head while cur.next is not None: cur = cur.next cur.next = node node.prev = cur def insert(self, pos, item): """ pos: pos從0開(kāi)始 pre:指定節(jié)點(diǎn)前一節(jié)點(diǎn)，相當(dāng)于游標(biāo) node：插入的指定節(jié)點(diǎn) 指定位置添加元素 """ # if pos<=0 頭插法 if pos <= 0: self.add(item) # elif pos>(self.length()-1) 尾插法 elif pos > (self.length() - 1): self.append(item) # else 插入法 else: cur = self._head count = 0 # 當(dāng)循環(huán)退出后，cur指向pos while count < pos: count += 1 cur = cur.next # 當(dāng)循環(huán)退出后，cur指向pos位置 node = Node(item) # 方式1： node.next = cur node.prev = cur.prev cur.prev.next = node cur.prev = node # 方式2： # node.next = cur # node.prev = cur.prev # cur.prev = node # node.prev.next = node def remove(self, item): """刪除元素""" # 考慮刪除頭部、尾部、中間節(jié)點(diǎn) cur = self._head while cur is not None: if cur.elem == item: # 先判斷是否是頭節(jié)點(diǎn) if cur == self._head: self._head = cur.next if cur.next: # 判斷鏈表表是否只有一個(gè)節(jié)點(diǎn) cur.next.prev = None else: cur.prev.next = cur.next if cur.next: # 判斷鏈表是否是最后一個(gè)節(jié)點(diǎn) cur.next.prev = cur.prev break else: cur = cur.next def search(self, item): """查找節(jié)點(diǎn)是否存在""" # 1. 創(chuàng)建游標(biāo) cur = self._head # 2. 遍歷游標(biāo) while cur is not None: # 3. cur.elem = item if cur.elem == item: return True else: cur = cur.next return False if __name__ == '__main__': DLL = DoubleLinkList() DLL.is_empty() l1 = DLL.length() print(l1) DLL.append(55) DLL.is_empty() l2 = DLL.length() print(l2) DLL.append(2) DLL.add(8) DLL.append(3) DLL.append(4) DLL.append(5) # 55 1 8 2 3 4 DLL.insert(-1, 9) # 9 8 55 2 1 8 2345 DLL.insert(2, 100) # 9 8 100 55 2 1 8 2345 DLL.travel()
以上就是python雙向鏈表的概念介紹，希望對(duì)大家有所幫助。更多Python學(xué)習(xí)指路：創(chuàng)新互聯(lián)Python教程
本文教程操作環(huán)境：windows7系統(tǒng)、Python 3.9.1，DELL G3電腦。
網(wǎng)站欄目：創(chuàng)新互聯(lián)Python教程：python雙向鏈表的概念介紹
本文路徑：http://www.dlmjj.cn/article/cdjspcs.html
