27.雙向鏈表及添加元素

雙向鏈表

一種更復雜的鏈表是“雙向鏈表”或“雙面鏈表”。每個節(jié)點有兩個鏈接：一個指向前一個節(jié)點，當此節(jié)點為第一個節(jié)點時，指向空值；而另一個指向下一個節(jié)點，當此節(jié)點為最后一個節(jié)點時，指向空值。

操作

• is_empty() 鏈表是否為空
• length() 鏈表長度
• travel() 遍歷鏈表
• add(item) 鏈表頭部添加
• append(item) 鏈表尾部添加
• insert(pos, item) 指定位置添加
• remove(item) 刪除節(jié)點
• search(item) 查找節(jié)點是否存在

class Node(object):"""雙向鏈表節(jié)點"""def __init__(self, item):self.item = itemself.next = Noneself.prev = None class DLinkList(object):"""雙向鏈表"""def __init__(self):self._head = None def is_empty(self):"""判斷鏈表是否為空"""return self._head == Nonedef length(self):"""返回鏈表的長度"""cur = self._headcount = 0while cur != None:count += 1cur = cur.nextreturn countdef travel(self):"""遍歷鏈表"""cur = self._headwhile cur != None:print cur.item,cur = cur.nextprint "" def add(self, item):"""頭部插入元素"""node = Node(item)if self.is_empty():# 如果是空鏈表，將_head指向nodeself._head = nodeelse:# 將node的next指向_head的頭節(jié)點node.next = self._head# 將_head的頭節(jié)點的prev指向nodeself._head.prev = node# 將_head 指向nodeself._head = nodedef append(self, item):"""尾部插入元素"""node = Node(item)if self.is_empty():# 如果是空鏈表，將_head指向nodeself._head = nodeelse:# 移動到鏈表尾部cur = self._headwhile cur.next != None:cur = cur.next# 將尾節(jié)點cur的next指向nodecur.next = node# 將node的prev指向curnode.prev = cur def insert(self, pos, item):"""在指定位置添加節(jié)點"""if pos <= 0:self.add(item)elif pos > (self.length()-1):self.append(item)else:node = Node(item)cur = self._headcount = 0# 移動到指定位置的前一個位置while count < (pos-1):count += 1cur = cur.nextnode.next = curnode.prev = cur.prevcur.prev.next = nodecur.prev = node

28.雙向鏈表刪除元素

def remove(self, item):"""刪除一個節(jié)點"""cur = self.__headwhile cur != None:if cur.elem == item:#先判斷此結(jié)點是否是頭節(jié)點#頭節(jié)點if cur == self.__head:self.__head = cur.nextif cur.next:#判斷鏈表是否只有一個結(jié)點cur.next.prev = Noneelse:cur.prev.next = cur.nextif cur.next:cur.next.prev = cur.prevbreakelse:cur = cur.next

29.單向循環(huán)鏈表遍歷和求長度

單向循環(huán)鏈表

單鏈表的一個變形是單向循環(huán)鏈表，鏈表中最后一個節(jié)點的next域不再為None，而是指向鏈表的頭節(jié)點。

?

操作

• is_empty() 判斷鏈表是否為空
• length() 返回鏈表的長度
• travel() 遍歷
• add(item) 在頭部添加一個節(jié)點
• append(item) 在尾部添加一個節(jié)點
• insert(pos, item) 在指定位置pos添加節(jié)點
• remove(item) 刪除一個節(jié)點
• search(item) 查找節(jié)點是否存在?

class SingLeLinkList(object):def __init__(self, node=None):self.__head = nodeif node:node.next=node def is_empty(self):"""判斷鏈表是否為空"""return self.__head == Nonedef length(self):"""返回鏈表的長度"""# 如果鏈表為空，返回長度0if self.is_empty():return 0count = 1cur = self._headwhile cur.next != self.__head:count += 1cur = cur.nextreturn countdef travel(self):"""遍歷鏈表"""if self.is_empty():returncur = self.__headprint cur.itemwhile cur.next != self.__head:print(cur.item, end=" ")cur = cur.nextprint(cur.item)

30.單向循環(huán)鏈表添加元素

def add(self, item):"""頭部添加節(jié)點"""node = Node(item)if self.is_empty():self.__head = nodenode.next = nodeelse:cur = self.__headwhile cur.next != self.__head:cur = cur.nextnode.next = self.__headself.__head = nodecur.next = self.__head def append(self, item):"""尾部添加節(jié)點"""node = Node(item)if self.is_empty():self.__head = nodenode.next = self.__headelse:# 移到鏈表尾部cur = self.__headwhile cur.next != self._head:cur = cur.next# 將尾節(jié)點指向nodecur.next = node# 將node指向頭節(jié)點_headnode.next = self.__head def insert(self, pos, item):"""在指定位置添加節(jié)點"""if pos <= 0:self.add(item)elif pos > (self.length()-1):self.append(item)else:node = Node(item)cur = self.__headcount = 0# 移動到指定位置的前一個位置while count < (pos-1):count += 1cur = cur.nextnode.next = cur.nextcur.next = node

31.單向循環(huán)鏈表刪除元素

def search(self, item):"""查找節(jié)點是否存在"""if self.is_empty():return Falsecur = self._headif cur.item == item:return Truewhile cur.next != self._head:cur = cur.nextif cur.item == item:return Truereturn False def remove(self, item):"""刪除一個節(jié)點"""if self.is_empty():returncur = self.__headpre = Nonewhile cur.next != self.__head:if cur.item == item:if cur == self.__head:rear = self.__headwhile rear.next != self.__head:rear = rear.nextself.__head = cur.nextrear.next =self.__headelse:pre.next = cur.nextreturnelse:pre = curcur = cur.nextif cur.item = item:if cur == self.__head:self.__head = Noneelse:pre.next = cur.next if __name__ =="__main__":ll =SingLeLinkList()print(ll.is_empty())print(ll.length())ll.append(2)ll.add(8)

32.單向循環(huán)鏈表刪除元素復習及鏈表擴展

回顧

總結(jié)

以上是生活随笔為你收集整理的Python数据结构与算法（第四天）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。