一、什么是鏈表

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

二、什么是節(jié)點(diǎn)

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

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

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

四、鏈表的基本操作

# 實(shí)現(xiàn)頭部插入 尾部插入 根據(jù)索引插入 刪除節(jié)點(diǎn)并print 打印 # 定義一個節(jié)點(diǎn) class Node:def __init__(self, data):self.data = dataself.next = Noneclass SingleLinkList:def __init__(self):self.head = Noneself.tail = Nonedef is_empty(self):"""鏈表是否為空:return:"""return self.head is Nonedef length(self):"""求當(dāng)前鏈表的長度:return:"""count = 0cur = self.headwhile cur is not None:count += 1cur = cur.nextreturn countdef insert_head_node(self, data):"""鏈表頭部添加元素:param data: 要保存的數(shù)據(jù):return:"""node = Node(data)node.next = self.headself.head = nodedef append_node(self, data):"""鏈表尾部添加元素,有多種實(shí)現(xiàn)方式:param data::return:"""# 第一種方式 時間復(fù)雜度為O(n)的處理方式node = Node(data)# 如果鏈表為空,需要特殊處理if self.is_empty():self.head = nodeelse:cur = self.headwhile cur.next is not None:cur = cur.next# 退出循環(huán)時, cur指向尾節(jié)點(diǎn)cur.next = node# 第二種 引入一個tail指針 默認(rèn)當(dāng)前鏈表為一個空鏈表,不停的去append節(jié)點(diǎn)# node = Node(data)# if self.is_empty(): # 當(dāng)?shù)谝淮翁砑庸?jié)點(diǎn)到空鏈表中的時候，頭指針和尾指針同時指向新節(jié)點(diǎn)# self.head = node# self.tail = node# else:# 當(dāng)再次添加節(jié)點(diǎn)到鏈表中的時候, 頭指針始終指向頭節(jié)點(diǎn)，尾指針始終執(zhí)行未節(jié)點(diǎn)，如果一直向未節(jié)點(diǎn)追加節(jié)點(diǎn)，只需移動tail指針即可# self.tail.next = node# self.tail = nodedef 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 = 0while count < (pos - 2):count += 1self.head = self.head.next# 這時候self.head 表示當(dāng)前插入前一個節(jié)點(diǎn)# self.head.next 表示當(dāng)前插入的后一個節(jié)點(diǎn)node = Node(data)self.head.next = nodenode.next = self.head.nextdef delete_node(self, data):"""刪除節(jié)點(diǎn):param data::return:"""cur = self.head # 記錄當(dāng)前節(jié)點(diǎn)的位置pre = None # 記錄當(dāng)前節(jié)點(diǎn)位置的前置節(jié)點(diǎn)while cur is not None:# 找到了要刪除的元素if cur.data == data:# 在頭部找到了要刪除的元素if cur == self.head:self.head = cur.nextreturn Trueelse:pre.next = cur.nextreturn Trueelse:# 不是要找的元素, 移動光標(biāo)pre = curcur = cur.nextdef search_node(self, data):"""查找節(jié)點(diǎn)是否存在:return:"""cur = self.headwhile cur is not None:if cur.data == data:return Truecur = cur.nextreturn Falsedef reveres_node(self):"""鏈表反轉(zhuǎn):return:"""if self.is_empty():returnj = 0while j < self.length() - 1:cur = self.headfor i in range(self.length() - 1):cur = cur.nextif cur.next is None:x = cur.dataself.delete_node(cur.data)self.insert_node(j, x)j += 1return self.head

總結(jié)

以上是生活随笔為你收集整理的python 链表的基础概念和基础用法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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