欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

python鏈表的基礎(chǔ)概念和基礎(chǔ)用法詳解

 更新時間:2022年05月05日 10:23:21   作者:一葉知秋的BLOG  
這篇文章主要為大家詳細介紹了python鏈表的基礎(chǔ)概念和基礎(chǔ)用法,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下

本文為大家分享了python鏈表的基礎(chǔ)概念和基礎(chǔ)用法,供大家參考,具體內(nèi)容如下

一、什么是鏈表

鏈表是由多個不同的節(jié)點組成,每個節(jié)點通過指針區(qū)域關(guān)聯(lián)到一起
鏈表的頭指針,指向了頭節(jié)點,通過頭指針可以找到其他節(jié)點信息

二、什么是節(jié)點

鏈表由節(jié)點組成,每個節(jié)點又包含兩個部分,一個是元素區(qū)域,一個是指針區(qū)域。
元素區(qū)域存儲的是,當(dāng)前節(jié)點的數(shù)值,指針區(qū)域指向下一個節(jié)點的對象。在C語言中,指針應(yīng)該是指向下一個元素的的內(nèi)存地址,因python中不研究指針,這里用下一個節(jié)點的對象代替。這樣我們就能通過指針區(qū)域,找到下一個節(jié)點的信息,從而得到下一個節(jié)點的值了。

三、為什么引入鏈表的概念

1.先說說數(shù)組這種數(shù)據(jù)結(jié)構(gòu)吧,數(shù)組是一塊大的連續(xù)內(nèi)存空間。每次初始化需要開辟一大塊內(nèi)存空間,空間利用率比較低。而鏈表則不同,鏈表的節(jié)點可以隨機分布在任何位置,只需通過指針穿引起來即可。
2.在連續(xù)的內(nèi)存空間中,插入一個元素時,所有其他元素的位置也變動了。插入元素、刪除元素時候,效率比較低。
鏈表是非連續(xù)的內(nèi)存空間,每個節(jié)點單獨存在自己的內(nèi)存空間,通過指針指向下一個節(jié)點。
如果在某個地方插入一個節(jié)點,只需要改變指針的指向即可,不用其他元素都變動。

四、鏈表的基本操作

# 實現(xiàn)頭部插入 尾部插入 根據(jù)索引插入 刪除節(jié)點并print 打印
# 定義一個節(jié)點
class Node:
? ? def __init__(self, data):
? ? ? ? self.data = data
? ? ? ? self.next = None


class SingleLinkList:

? ? def __init__(self):
? ? ? ? self.head = None
? ? ? ? self.tail = None

? ? def is_empty(self):
? ? ? ? """鏈表是否為空
? ? ? ? :return:
? ? ? ? """
? ? ? ? return self.head is None

? ? def length(self):
? ? ? ? """求當(dāng)前鏈表的長度
? ? ? ? :return:
? ? ? ? """
? ? ? ? count = 0
? ? ? ? cur = self.head

? ? ? ? while cur is not None:
? ? ? ? ? ? count += 1
? ? ? ? ? ? cur = cur.next

? ? ? ? return count

? ? def insert_head_node(self, data):
? ? ? ? """鏈表頭部添加元素
? ? ? ? :param data: 要保存的數(shù)據(jù)
? ? ? ? :return:
? ? ? ? """
? ? ? ? node = Node(data)
? ? ? ? node.next = self.head
? ? ? ? self.head = node

? ? def append_node(self, data):
? ? ? ? """鏈表尾部添加元素,有多種實現(xiàn)方式
? ? ? ? :param data:
? ? ? ? :return:
? ? ? ? """
? ? ? ? # 第一種方式 ?時間復(fù)雜度為O(n)的處理方式
? ? ? ? node = Node(data)
? ? ? ? # 如果鏈表為空,需要特殊處理
? ? ? ? if self.is_empty():
? ? ? ? ? ? self.head = node
? ? ? ? else:
? ? ? ? ? ? cur = self.head
? ? ? ? ? ? while cur.next is not None:
? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? # 退出循環(huán)時, cur指向尾節(jié)點
? ? ? ? ? ? cur.next = node

? ? ? ? # 第二種 引入一個tail指針 默認(rèn)當(dāng)前鏈表為一個空鏈表,不停的去append節(jié)點

? ? ? ? # node = Node(data)
? ? ? ? # if self.is_empty(): ?# 當(dāng)?shù)谝淮翁砑庸?jié)點到空鏈表中的時候,頭指針和尾指針同時指向新節(jié)點
? ? ? ? # ? ? self.head = node
? ? ? ? # ? ? self.tail = node

? ? ? ? # else:
? ? ? ? # 當(dāng)再次添加節(jié)點到鏈表中的時候, 頭指針始終指向頭節(jié)點,尾指針始終執(zhí)行未節(jié)點,如果一直向未節(jié)點追加節(jié)點,只需移動tail指針即可
? ? ? ? # ? ? self.tail.next = node
? ? ? ? # ? ? self.tail = node

? ? def insert_node(self, pos, data):
? ? ? ? """指定位置添加元素
? ? ? ? :param pos:
? ? ? ? :param data:
? ? ? ? :return:
? ? ? ? """
? ? ? ? # 1, 在頭部添加
? ? ? ? if pos <= 0:
? ? ? ? ? ? self.insert_head_node(data)
? ? ? ? # 2, 在尾部添加
? ? ? ? elif self.length() >= pos:
? ? ? ? ? ? self.append_node(data)
? ? ? ? # 3, 指定位置添加
? ? ? ? else:
? ? ? ? ? ? count = 0
? ? ? ? ? ? while count < (pos - 2):
? ? ? ? ? ? ? ? count += 1
? ? ? ? ? ? ? ? self.head = self.head.next

? ? ? ? ? ? # 這時候self.head 表示當(dāng)前插入前一個節(jié)點
? ? ? ? ? ? # self.head.next 表示當(dāng)前插入的后一個節(jié)點
? ? ? ? ? ? node = Node(data)
? ? ? ? ? ? self.head.next = node
? ? ? ? ? ? node.next = self.head.next

? ? def delete_node(self, data):
? ? ? ? """刪除節(jié)點
? ? ? ? :param data:
? ? ? ? :return:
? ? ? ? """
? ? ? ? cur = self.head ? ? # 記錄當(dāng)前節(jié)點的位置
? ? ? ? pre = None ? ? ? ? ?# 記錄當(dāng)前節(jié)點位置的前置節(jié)點
? ? ? ? while cur is not None:
? ? ? ? ? ? # 找到了要刪除的元素
? ? ? ? ? ? if cur.data == data:
? ? ? ? ? ? ? ? # 在頭部找到了要刪除的元素
? ? ? ? ? ? ? ? if cur == self.head:
? ? ? ? ? ? ? ? ? ? self.head = cur.next
? ? ? ? ? ? ? ? ? ? return True
? ? ? ? ? ? ? ? else:
? ? ? ? ? ? ? ? ? ? pre.next = cur.next
? ? ? ? ? ? ? ? ? ? return True
? ? ? ? ? ? else:
? ? ? ? ? ? ? ? # 不是要找的元素, 移動光標(biāo)
? ? ? ? ? ? ? ? pre = cur
? ? ? ? ? ? ? ? cur = cur.next

? ? def search_node(self, data):
? ? ? ? """查找節(jié)點是否存在
? ? ? ? :return:
? ? ? ? """
? ? ? ? cur = self.head
? ? ? ? while cur is not None:
? ? ? ? ? ? if cur.data == data:
? ? ? ? ? ? ? ? return True
? ? ? ? ? ? cur = cur.next
? ? ? ? return False

? ? def reveres_node(self):
? ? ? ? """鏈表反轉(zhuǎn)
? ? ? ? :return:
? ? ? ? """
? ? ? ? if self.is_empty():
? ? ? ? ? ? return
? ? ? ? j = 0
? ? ? ? while j < self.length() - 1:
? ? ? ? ? ? cur = self.head
? ? ? ? ? ? for i in range(self.length() - 1):
? ? ? ? ? ? ? ? cur = cur.next
? ? ? ? ? ? ? ? if cur.next is None:
? ? ? ? ? ? ? ? ? ? x = cur.data
? ? ? ? ? ? ? ? ? ? self.delete_node(cur.data)
? ? ? ? ? ? ? ? ? ? self.insert_node(j, x)
? ? ? ? ? ? j += 1
? ? ? ? return self.head

以上就是本文的全部內(nèi)容,希望對大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。

相關(guān)文章

最新評論