您好,登錄后才能下訂單哦!
小編給大家分享一下python雙向鏈表的示例分析,相信大部分人都還不怎么了解,因此分享這篇文章給大家參考一下,希望大家閱讀完這篇文章后大有收獲,下面讓我們一起去了解一下吧!
Python是一種跨平臺(tái)的、具有解釋性、編譯性、互動(dòng)性和面向?qū)ο蟮哪_本語(yǔ)言,其最初的設(shè)計(jì)是用于編寫自動(dòng)化腳本,隨著版本的不斷更新和新功能的添加,常用于用于開發(fā)獨(dú)立的項(xiàng)目和大型項(xiàng)目。
1、說(shuō)明
更復(fù)雜的鏈表是“雙向鏈表”或“雙面鏈表”。每個(gè)節(jié)點(diǎn)有兩個(gè)鏈接:一個(gè)指向前一個(gè)節(jié)點(diǎn),這個(gè)節(jié)點(diǎn)是第一個(gè)。
一個(gè)節(jié)點(diǎn)指向空值,另一個(gè)指向下一個(gè)節(jié)點(diǎn),當(dāng)該節(jié)點(diǎn)指向最后一個(gè)節(jié)點(diǎn)時(shí)指向空值。
2、操作方法
is_empty()鏈表是否為空。
length(鏈表長(zhǎng)度。
travel)經(jīng)歷鏈表。
添加add(item)鏈表頭部。
添加到append(item)鏈表的尾部。
添加insert(pos、item)指定位置。
remove刪除節(jié)點(diǎn)。
搜索節(jié)點(diǎn)是否存在。
3、實(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開始 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雙向鏈表的示例分析”這篇文章的所有內(nèi)容,感謝各位的閱讀!相信大家都有了一定的了解,希望分享的內(nèi)容對(duì)大家有所幫助,如果還想學(xué)習(xí)更多知識(shí),歡迎關(guān)注億速云行業(yè)資訊頻道!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。