網(wǎng)站首頁(yè) 編程語(yǔ)言 正文
一、鏈表簡(jiǎn)介
鏈表是一種在存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)。鏈表是由一系列的結(jié)點(diǎn)組成，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成。每個(gè)結(jié)點(diǎn)包含兩部分：數(shù)據(jù)域與指針域。數(shù)據(jù)域存儲(chǔ)數(shù)據(jù)元素，指針域存儲(chǔ)下一結(jié)點(diǎn)的指針。
二、單向鏈表
單向鏈表也叫單鏈表，是鏈表中最簡(jiǎn)單的形式，它的每個(gè)節(jié)點(diǎn)包含兩個(gè)域，一個(gè)信息域（元素域）和一個(gè)鏈接域。這個(gè)鏈接指向鏈表中的下一個(gè)節(jié)點(diǎn)，而最后一個(gè)節(jié)點(diǎn)的鏈接域則指向一個(gè)空值。
head 保存首地址，item 存儲(chǔ)數(shù)據(jù)，next 指向下一結(jié)點(diǎn)地址。
鏈表失去了序列的隨機(jī)讀取優(yōu)點(diǎn)，同時(shí)鏈表增加了指針域，空間開(kāi)銷(xiāo)也較大，但它對(duì)存儲(chǔ)空間的使用要相對(duì)靈活。
列如：有一堆數(shù)據(jù)[1,2,3,5,6,7]，要在3和5之間插入4, 如果用數(shù)組，需要將5之后的數(shù)據(jù)都往后退一位，然后再插入4，這樣非常麻煩，但是如果用鏈表，我就直接在3和5之間插入4就行。
1. 定義結(jié)點(diǎn)
結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)為數(shù)據(jù)元素(item)與 指針(next)
class Node(object):
"""單鏈表的結(jié)點(diǎn)"""
def __init__(self, item):
# item存放數(shù)據(jù)元素
self.item = item
# next是下一個(gè)節(jié)點(diǎn)的標(biāo)識(shí)
self.next = None
2. 定義鏈表
鏈表需要具有首地址指針head。
class SingleLinkList(object):
"""單鏈表"""
def __init__(self):
self._head = None
示例：創(chuàng)建鏈表
if __name__ == '__main__':
# 創(chuàng)建鏈表
link_list = SingleLinkList()
# 創(chuàng)建結(jié)點(diǎn)
node1 = Node(1)
node2 = Node(2)
# 將結(jié)點(diǎn)添加到鏈表
link_list._head = node1
# 將第一個(gè)結(jié)點(diǎn)的next指針指向下一結(jié)點(diǎn)
node1.next = node2
# 訪問(wèn)鏈表
print(link_list._head.item) # 訪問(wèn)第一個(gè)結(jié)點(diǎn)數(shù)據(jù)
print(link_list._head.next.item) # 訪問(wèn)第二個(gè)結(jié)點(diǎn)數(shù)據(jù)
是不是感覺(jué)很麻煩，所以我們要在鏈表中增加操作方法。
- is_empty() 鏈表是否為空
- length() 鏈表長(zhǎng)度
- items() 獲取鏈表數(shù)據(jù)迭代器
- add(item) 鏈表頭部添加元素
- append(item) 鏈表尾部添加元素
- insert(pos, item) 指定位置添加元素
- remove(item) 刪除節(jié)點(diǎn)
- find(item) 查找節(jié)點(diǎn)是否存在
代碼如下：
class SingleLinkList(object):
"""單鏈表"""
def __init__(self):
self._head = None
def is_empty(self):
"""判斷鏈表是否為空"""
return self._head is None
def length(self):
"""鏈表長(zhǎng)度"""
# 初始指針指向head
cur = self._head
count = 0
# 指針指向None 表示到達(dá)尾部
while cur is not None:
count += 1
# 指針下移
cur = cur.next
return count
def items(self):
"""遍歷鏈表"""
# 獲取head指針
cur = self._head
# 循環(huán)遍歷
while cur is not None:
# 返回生成器
yield cur.item
# 指針下移
cur = cur.next
def add(self, item):
"""向鏈表頭部添加元素"""
node = Node(item)
# 新結(jié)點(diǎn)指針指向原頭部結(jié)點(diǎn)
node.next = self._head
# 頭部結(jié)點(diǎn)指針修改為新結(jié)點(diǎn)
self._head = node
def append(self, item):
"""尾部添加元素"""
node = Node(item)
# 先判斷是否為空鏈表
if self.is_empty():
# 空鏈表，_head 指向新結(jié)點(diǎn)
self._head = node
else:
# 不是空鏈表，則找到尾部，將尾部next結(jié)點(diǎn)指向新結(jié)點(diǎn)
cur = self._head
while cur.next is not None:
cur = cur.next
cur.next = node
def insert(self, index, item):
"""指定位置插入元素"""
# 指定位置在第一個(gè)元素之前，在頭部插入
if index <= 0:
self.add(item)
# 指定位置超過(guò)尾部，在尾部插入
elif index > (self.length() - 1):
self.append(item)
else:
# 創(chuàng)建元素結(jié)點(diǎn)
node = Node(item)
cur = self._head
# 循環(huán)到需要插入的位置
for i in range(index - 1):
cur = cur.next
node.next = cur.next
cur.next = node
def remove(self, item):
"""刪除節(jié)點(diǎn)"""
cur = self._head
pre = None
while cur is not None:
# 找到指定元素
if cur.item == item:
# 如果第一個(gè)就是刪除的節(jié)點(diǎn)
if not pre:
# 將頭指針指向頭節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)
self._head = cur.next
else:
# 將刪除位置前一個(gè)節(jié)點(diǎn)的next指向刪除位置的后一個(gè)節(jié)點(diǎn)
pre.next = cur.next
return True
else:
# 繼續(xù)按鏈表后移節(jié)點(diǎn)
pre = cur
cur = cur.next
def find(self, item):
"""查找元素是否存在"""
return item in self.items()
示例：操作鏈表
if __name__ == '__main__':
link_list = SingleLinkList()
# 向鏈表尾部添加數(shù)據(jù)
for i in range(5):
link_list.append(i)
# 向頭部添加數(shù)據(jù)
link_list.add(6)
# 遍歷鏈表數(shù)據(jù)
for i in link_list.items():
print(i, end='\t')
# 鏈表數(shù)據(jù)插入數(shù)據(jù)
link_list.insert(3, 9)
print('\n', list(link_list.items()))
# 刪除鏈表數(shù)據(jù)
link_list.remove(0)
# 查找鏈表數(shù)據(jù)
print(link_list.find(4))
三、循環(huán)鏈表
單向循環(huán)鏈表為單向鏈表的變種，鏈表的最后一個(gè)next指向鏈表頭，新增一個(gè)循環(huán)。
1. 循環(huán)鏈表結(jié)點(diǎn)
class Node(object):
"""鏈表的結(jié)點(diǎn)"""
def __init__(self, item):
# item存放數(shù)據(jù)元素
self.item = item
# next是下一個(gè)節(jié)點(diǎn)的標(biāo)識(shí)
self.next = None
2. 定義循環(huán)鏈表
class SingleCycleLinkList(object):
def __init__(self):
self._head = None
def is_empty(self):
"""判斷鏈表是否為空"""
return self._head is None
def length(self):
"""鏈表長(zhǎng)度"""
# 鏈表為空
if self.is_empty():
return 0
# 鏈表不為空
count = 1
cur = self._head
while cur.next != self._head:
count += 1
# 指針下移
cur = cur.next
return count
def items(self):
""" 遍歷鏈表 """
# 鏈表為空
if self.is_empty():
return
# 鏈表不為空
cur = self._head
while cur.next != self._head:
yield cur.item
cur = cur.next
yield cur.item
def add(self, item):
""" 頭部添加結(jié)點(diǎn)"""
node = Node(item)
if self.is_empty(): # 為空
self._head = node
node.next = self._head
else:
# 添加結(jié)點(diǎn)指向head
node.next = self._head
cur = self._head
# 移動(dòng)結(jié)點(diǎn)，將末尾的結(jié)點(diǎn)指向node
while cur.next != self._head:
cur = cur.next
cur.next = node
# 修改 head 指向新結(jié)點(diǎn)
self._head = node
def append(self, item):
"""尾部添加結(jié)點(diǎn)"""
node = Node(item)
if self.is_empty(): # 為空
self._head = node
node.next = self._head
else:
# 尋找尾部
cur = self._head
while cur.next != self._head:
cur = cur.next
# 尾部指針指向新結(jié)點(diǎn)
cur.next = node
# 新結(jié)點(diǎn)指針指向head
node.next = self._head
def insert(self, index, item):
""" 指定位置添加結(jié)點(diǎn)"""
if index <= 0: # 指定位置小于等于0，頭部添加
self.add(item)
# 指定位置大于鏈表長(zhǎng)度，尾部添加
elif index > self.length() - 1:
self.append(item)
else:
node = Node(item)
cur = self._head
# 移動(dòng)到添加結(jié)點(diǎn)位置
for i in range(index - 1):
cur = cur.next
# 新結(jié)點(diǎn)指針指向舊結(jié)點(diǎn)
node.next = cur.next
# 舊結(jié)點(diǎn)指針 指向 新結(jié)點(diǎn)
cur.next = node
def remove(self, item):
""" 刪除一個(gè)結(jié)點(diǎn) """
if self.is_empty():
return
cur = self._head
pre = Node
# 第一個(gè)元素為需要?jiǎng)h除的元素
if cur.item == item:
# 鏈表不止一個(gè)元素
if cur.next != self._head:
while cur.next != self._head:
cur = cur.next
# 尾結(jié)點(diǎn)指向 頭部結(jié)點(diǎn)的下一結(jié)點(diǎn)
cur.next = self._head.next
# 調(diào)整頭部結(jié)點(diǎn)
self._head = self._head.next
else:
# 只有一個(gè)元素
self._head = None
else:
# 不是第一個(gè)元素
pre = self._head
while cur.next != self._head:
if cur.item == item:
# 刪除
pre.next = cur.next
return True
else:
pre = cur # 記錄前一個(gè)指針
cur = cur.next # 調(diào)整指針位置
# 當(dāng)刪除元素在末尾
if cur.item == item:
pre.next = self._head
return True
def find(self, item):
""" 查找元素是否存在"""
return item in self.items()
if __name__ == '__main__':
link_list = SingleCycleLinkList()
print(link_list.is_empty())
# 頭部添加元素
for i in range(5):
link_list.add(i)
print(list(link_list.items()))
# 尾部添加元素
for i in range(6):
link_list.append(i)
print(list(link_list.items()))
# 添加元素
link_list.insert(3, 45)
print(list(link_list.items()))
# 刪除元素
link_list.remove(5)
print(list(link_list.items()))
# 元素是否存在
print(4 in link_list.items())
四、雙向鏈表
雙向鏈表比單向鏈表更加復(fù)雜，它每個(gè)節(jié)點(diǎn)有兩個(gè)鏈接：一個(gè)指向前一個(gè)節(jié)點(diǎn)，當(dāng)此節(jié)點(diǎn)為第一個(gè)節(jié)點(diǎn)時(shí)，指向空值；而另一個(gè)鏈接指向下一個(gè)節(jié)點(diǎn)，當(dāng)此節(jié)點(diǎn)為最后一個(gè)節(jié)點(diǎn)時(shí)，指向空值。
head 保存首地址，item 存儲(chǔ)數(shù)據(jù)，next 指向下一結(jié)點(diǎn)地址，prev 指向上一結(jié)點(diǎn)地址。
1. 定義雙向鏈表結(jié)點(diǎn)
class Node(object):
"""雙向鏈表的結(jié)點(diǎn)"""
def __init__(self, item):
# item存放數(shù)據(jù)元素
self.item = item
# next 指向下一個(gè)節(jié)點(diǎn)的標(biāo)識(shí)
self.next = None
# prev 指向上一結(jié)點(diǎn)
self.prev = None
2. 定義雙向鏈表
class BilateralLinkList(object):
"""雙向鏈表"""
def __init__(self):
self._head = None
def is_empty(self):
"""判斷鏈表是否為空"""
return self._head is None
def length(self):
"""鏈表長(zhǎng)度"""
# 初始指針指向head
cur = self._head
count = 0
# 指針指向None 表示到達(dá)尾部
while cur is not None:
count += 1
# 指針下移
cur = cur.next
return count
def items(self):
"""遍歷鏈表"""
# 獲取head指針
cur = self._head
# 循環(huán)遍歷
while cur is not None:
# 返回生成器
yield cur.item
# 指針下移
cur = cur.next
def add(self, item):
"""向鏈表頭部添加元素"""
node = Node(item)
if self.is_empty():
# 頭部結(jié)點(diǎn)指針修改為新結(jié)點(diǎn)
self._head = node
else:
# 新結(jié)點(diǎn)指針指向原頭部結(jié)點(diǎn)
node.next = self._head
# 原頭部 prev 指向 新結(jié)點(diǎn)
self._head.prev = node
# head 指向新結(jié)點(diǎn)
self._head = node
def append(self, item):
"""尾部添加元素"""
node = Node(item)
if self.is_empty(): # 鏈表無(wú)元素
# 頭部結(jié)點(diǎn)指針修改為新結(jié)點(diǎn)
self._head = node
else: # 鏈表有元素
# 移動(dòng)到尾部
cur = self._head
while cur.next is not None:
cur = cur.next
# 新結(jié)點(diǎn)上一級(jí)指針指向舊尾部
node.prev = cur
# 舊尾部指向新結(jié)點(diǎn)
cur.next = node
def insert(self, index, item):
""" 指定位置插入元素"""
if index <= 0:
self.add(item)
elif index > self.length() - 1:
self.append(item)
else:
node = Node(item)
cur = self._head
for i in range(index):
cur = cur.next
# 新結(jié)點(diǎn)的向下指針指向當(dāng)前結(jié)點(diǎn)
node.next = cur
# 新結(jié)點(diǎn)的向上指針指向當(dāng)前結(jié)點(diǎn)的上一結(jié)點(diǎn)
node.prev = cur.prev
# 當(dāng)前上一結(jié)點(diǎn)的向下指針指向node
cur.prev.next = node
# 當(dāng)前結(jié)點(diǎn)的向上指針指向新結(jié)點(diǎn)
cur.prev = node
def remove(self, item):
""" 刪除結(jié)點(diǎn) """
if self.is_empty():
return
cur = self._head
# 刪除元素在第一個(gè)結(jié)點(diǎn)
if cur.item == item:
# 只有一個(gè)元素
if cur.next is None:
self._head = None
return True
else:
# head 指向下一結(jié)點(diǎn)
self._head = cur.next
# 下一結(jié)點(diǎn)的向上指針指向None
cur.next.prev = None
return True
# 移動(dòng)指針查找元素
while cur.next is not None:
if cur.item == item:
# 上一結(jié)點(diǎn)向下指針指向下一結(jié)點(diǎn)
cur.prev.next = cur.next
# 下一結(jié)點(diǎn)向上指針指向上一結(jié)點(diǎn)
cur.next.prev = cur.prev
return True
cur = cur.next
# 刪除元素在最后一個(gè)
if cur.item == item:
# 上一結(jié)點(diǎn)向下指針指向None
cur.prev.next = None
return True
def find(self, item):
"""查找元素是否存在"""
return item in self.items()
原文鏈接：https://blog.csdn.net/weixin_39589455/article/details/130504551
- 上一篇：沒(méi)有了
- 下一篇：沒(méi)有了
相關(guān)推薦
- 2022-10-12 pandas學(xué)習(xí)之df.set_index的具體使用_python
- 2022-04-05 一篇文章帶你了解Python的進(jìn)程,線(xiàn)程和協(xié)程_python
- 2022-09-04 Python?numpy和matlab的幾點(diǎn)差異介紹_python
- 2022-03-03 iview 在 Table 組件中，文字過(guò)長(zhǎng)用省略號(hào)代替，鼠標(biāo)放上去 Tooltip 文字提示
- 2021-11-21 關(guān)于.NET6?Minimal?API的使用方式詳解_實(shí)用技巧
- 2022-12-24 C#如何優(yōu)雅的對(duì)WinForm窗體應(yīng)用程序進(jìn)行權(quán)限控制_C#教程
- 2022-10-09 玩轉(zhuǎn)Go命令行工具Cobra_Golang
- 2022-05-13 分布式架構(gòu)Redis中有哪些數(shù)據(jù)結(jié)構(gòu)及底層實(shí)現(xiàn)原理_Redis
- 欄目分類(lèi)
-
- 最近更新
-
- window11 系統(tǒng)安裝 yarn
- 超詳細(xì)win安裝深度學(xué)習(xí)環(huán)境2025年最新版（
- Linux 中運(yùn)行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲(chǔ)小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎(chǔ)操作-- 運(yùn)算符，流程控制 Flo
- 1. Int 和Integer 的區(qū)別，Jav
- spring @retryable不生效的一種
- Spring Security之認(rèn)證信息的處理
- Spring Security之認(rèn)證過(guò)濾器
- Spring Security概述快速入門(mén)
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權(quán)
- redisson分布式鎖中waittime的設(shè)
- maven:解決release錯(cuò)誤：Artif
- restTemplate使用總結(jié)
- Spring Security之安全異常處理
- MybatisPlus優(yōu)雅實(shí)現(xiàn)加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務(wù)發(fā)現(xiàn)-Nac
- Spring Security之基于HttpR
- Redis 底層數(shù)據(jù)結(jié)構(gòu)-簡(jiǎn)單動(dòng)態(tài)字符串（SD
- arthas操作spring被代理目標(biāo)對(duì)象命令
- Spring中的單例模式應(yīng)用詳解
- 聊聊消息隊(duì)列，發(fā)送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠(yuǎn)程分支
提供CDN加速