雙向鏈表

雙向鏈表的實現(xiàn)

一、往鏈表的頭部增加一個節(jié)點

# 新建一個節(jié)點node = Node(data)# 判斷鏈表是否為空if self.is_empty():self.head = nodeelse:# 讓鏈表中原本的頭節(jié)點的prev指向新的節(jié)點self.head.prev = node# 先讓node指向當(dāng)前鏈表中的頭節(jié)點node.next = self.head# 再讓鏈表的head指向當(dāng)前node節(jié)點self.head = node# 添加節(jié)點之后，鏈表的長度加1self._length += 1

二、鏈表尾部添加一個節(jié)點

node = Node(data)if self.head:cur = self.head # 將頭節(jié)點的地址賦給了變量curwhile cur.next:cur = cur.nextnode.prev = cur # 讓node的prev指針域去指向原本的尾節(jié)點cur.next = node # 讓原本的尾節(jié)點的next指向新建的節(jié)點else:self.head = node# 讓當(dāng)前的尾節(jié)點的指針指向新建的節(jié)點node# 鏈表的長度加1self._length += 1

三、往鏈表指定位置插入一個節(jié)點，值為data

1新建一個節(jié)點node = Node(data)# 2找到鏈表中索引為pos-1的節(jié)點cur = self.headwhile pos - 1:cur = cur.nextpos -= 1# 到這里之后，cur指向的是索引為pos-1的節(jié)點# 讓node的prev指向索引為pos-1的節(jié)點node.prev = cur# 讓node的next指向索引為pos的節(jié)點cur.next.prev = node# 讓索引為pos的節(jié)點指向新建的節(jié)點node.next = cur.next# 4讓索引為pos-1的節(jié)點的next指向nodecur.next = node# 5鏈表的長度加1self._length += 1

四、刪除鏈表中第一個值為data的節(jié)點

cur = self.headwhile cur:if cur.data == data:if cur == self.head:self.head = cur.nextelse:cur.prev.next = cur.nextif cur.next:cur.next.prev=cur.prevself._length -= 1return 0cur = cur.nextreturn -1

五、修改鏈表中指定位置節(jié)點的值

if 0 < pos < self._length:cur = self.headwhile pos:cur = cur.nextpos -= 1cur.data = dataelse:print('輸入的范圍不符合要求')

六、查找鏈表中是否有節(jié)點的值為data

cur=self.head while cur:if cur.data==data:return 1else:cur=cur.next return -1

代碼塊：

class Node:def __init__(self, data, _prev=None, _next=None):self.prev = _prev # 指針域，指向當(dāng)前節(jié)點的前一個節(jié)點self.data = data # 數(shù)據(jù)域self.next = _next # 指針域 指向當(dāng)前節(jié)點的后一個節(jié)點class DoubleLinkList:def __init__(self):self.head = None # 鏈表的的頭節(jié)點self._length = 0 # 鏈表的長度，鏈表的元素個數(shù)def is_empty(self):# 判斷鏈表的是否為空return self._length == 0def length(self):# 返回鏈表的長度return self._lengthdef nodes_list(self):# 返回鏈表中的所有節(jié)點的值組成的列表res = []cur = self.headwhile cur:res.append(cur.data)cur = cur.nextreturn resdef add(self, data):# 往鏈表的頭部添加一個節(jié)點，值為data# 新建一個節(jié)點node = Node(data)# 判斷鏈表是否為空if self.is_empty():self.head = nodeelse:# 讓鏈表中原本的頭節(jié)點的prev指向新的節(jié)點self.head.prev = node# 先讓node指向當(dāng)前鏈表中的頭節(jié)點node.next = self.head# 再讓鏈表的head指向當(dāng)前node節(jié)點self.head = node# 添加節(jié)點之后，鏈表的長度加1self._length += 1def append(self, data):# 往鏈表的尾部添加一個節(jié)點，值為data# 新建一個節(jié)點node，值為datanode = Node(data)if self.head:cur = self.head # 將頭節(jié)點的地址賦給了變量curwhile cur.next:cur = cur.nextnode.prev = cur # 讓node的prev指針域去指向原本的尾節(jié)點cur.next = node # 讓原本的尾節(jié)點的next指向新建的節(jié)點else:self.head = node# 讓當(dāng)前的尾節(jié)點的指針指向新建的節(jié)點node# 鏈表的長度加1self._length += 1def insert(self, pos, data):# 往鏈表的指定位置插入一個節(jié)點，值為dataif pos <= 0:self.add(data)elif pos > self._length:self.append(data)else:# 1新建一個節(jié)點node = Node(data)# 2找到鏈表中索引為pos-1的節(jié)點cur = self.headwhile pos - 1:cur = cur.nextpos -= 1# 到這里之后，cur指向的是索引為pos-1的節(jié)點# 讓node的prev指向索引為pos-1的節(jié)點node.prev = cur# 讓node的next指向索引為pos的節(jié)點cur.next.prev = node# 讓索引為pos的節(jié)點指向新建的節(jié)點node.next = cur.next# 4讓索引為pos-1的節(jié)點的next指向nodecur.next = node# 5鏈表的長度加1self._length += 1def remove(self, data):# 刪除鏈表中第一個值為data的節(jié)點cur = self.headwhile cur:if cur.data == data:if cur == self.head:self.head = cur.nextelse:cur.prev.next = cur.nextif cur.next:cur.next.prev=cur.prevself._length -= 1return 0cur = cur.nextreturn -1def modify(self, pos, data):# 修改鏈表中指定位置節(jié)點的值if 0 < pos < self._length:cur = self.headwhile pos:cur = cur.nextpos -= 1cur.data = dataelse:print('輸入的范圍不符合要求')def search(self, data):# 查找鏈表中是否有節(jié)點的值為datacur = self.headwhile cur:if cur.data == data:return Truecur = cur.nextreturn Falseif __name__ == '__main__':l1 = DoubleLinkList() # 新建一個鏈表類print(l1.head, l1.length())l1.add(1)print(l1.nodes_list())l1.append(2)print(l1.nodes_list())l1.append(3)print(l1.nodes_list())l1.insert(1, 8)print(l1.nodes_list())l1.remove(2)print(l1.nodes_list())l1.remove(1)print(l1.nodes_list())l1.modify(1,7)print(l1.nodes_list())print(l1.search(7))

總結(jié)

以上是生活随笔為你收集整理的算法—详细讲解双向链表的实现（python）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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