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)文章
pytorch之torch.nn.Identity()的作用及解釋
這篇文章主要介紹了pytorch之torch.nn.Identity()的作用及解釋,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-08-08將tensorflow.Variable中的某些元素取出組成一個新的矩陣示例
今天小編就為大家分享一篇將tensorflow.Variable中的某些元素取出組成一個新的矩陣示例,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧2020-01-01