Python實(shí)現(xiàn)單項(xiàng)鏈表的最全教程
更新時(shí)間：2023年01月07日 08:53:45 作者：Thank?CAT
單向鏈表也叫單鏈表，是鏈表中最簡(jiǎn)單的一種形式，它的每個(gè)節(jié)點(diǎn)包含兩個(gè)域，一個(gè)信息域（元素域）和一個(gè)鏈接域，這個(gè)鏈接指向鏈表中的下一個(gè)節(jié)點(diǎn)，而最后一個(gè)節(jié)點(diǎn)的鏈接域則指向一個(gè)空值，這篇文章主要介紹了Python實(shí)現(xiàn)單項(xiàng)鏈表,需要的朋友可以參考下
單向鏈表
單向鏈表也叫單鏈表，是鏈表中最簡(jiǎn)單的一種形式，它的每個(gè)節(jié)點(diǎn)包含兩個(gè)域，一個(gè)信息域（元素域）和一個(gè)鏈接域。這個(gè)鏈接指向鏈表中的下一個(gè)節(jié)點(diǎn)，而最后一個(gè)節(jié)點(diǎn)的鏈接域則指向一個(gè)空值。
- 表元素域elem用來(lái)存放具體的數(shù)據(jù)。
- 鏈接域next用來(lái)存放下一個(gè)節(jié)點(diǎn)的位置（python中的標(biāo)識(shí)）
- 變量p指向鏈表的頭節(jié)點(diǎn)（首節(jié)點(diǎn)）的位置，從p出發(fā)能找到表中的任意節(jié)點(diǎn)。
節(jié)點(diǎn)實(shí)現(xiàn)
class Node(object):
"""節(jié)點(diǎn)"""
def __init__(self, elem):
self.elem = elem
self.next = None單鏈表的操作
- is_empty() 鏈表是否為空
- length() 鏈表長(zhǎng)度
- travel() 遍歷整個(gè)鏈表
- add(item) 鏈表頭部添加元素
- append(item) 鏈表尾部添加元素
- insert(pos, item) 指定位置添加元素
- remove(item) 刪除節(jié)點(diǎn)
- search(item) 查找節(jié)點(diǎn)是否存在
單鏈表的實(shí)現(xiàn)
class SingleLinkList(object):
"""單鏈表"""
def __init__(self, node=None):
self.__head = node
單鏈表 判斷鏈表是否為空（is_empty）
def is_empty(self):
"""鏈表是否為空"""
return self.__head == None
單鏈表 鏈表長(zhǎng)度（length）
def length(self):
"""鏈表長(zhǎng)度"""
# cur游標(biāo)，用來(lái)移動(dòng)遍歷節(jié)點(diǎn)
cur = self.__head
# count記錄數(shù)量
count = 0
while cur != None:
count += 1
cur = cur.next
return count
單鏈表 遍歷整個(gè)鏈表（travel）
def travel(self):
"""遍歷整個(gè)鏈表"""
cur = self.__head
while cur != None:
print(cur.elem, end=" ")
cur = cur.next
print("")
單鏈表 鏈表尾部添加元素，尾插法（append）
def append(self, item):
"""鏈表尾部添加元素, 尾插法"""
node = Node(item)
if self.is_empty():
self.__head = node
else:
cur = self.__head
while cur.next != None:
cur = cur.next
cur.next = node
單鏈表 鏈表頭部插入元素，頭插法（add）
def add(self, item):
"""鏈表頭部添加元素，頭插法"""
node = Node(item)
node.next = self.__head
self.__head = node
單鏈表 指定位置插入元素（insert）
def insert(self, pos, item):
"""指定位置添加元素
:param pos 從0開(kāi)始
"""
if pos <= 0:
self.add(item)
elif pos > (self.length()-1):
self.append(item)
else:
pre = self.__head
count = 0
while count < (pos-1):
count += 1
pre = pre.next
# 當(dāng)循環(huán)退出后，pre指向pos-1位置
node = Node(item)
node.next = pre.next
pre.next = node
單鏈表 刪除節(jié)點(diǎn)（remove）
def remove(self, item):
"""刪除節(jié)點(diǎn)"""
cur = self.__head
pre = None
while cur != None:
if cur.elem == item:
# 先判斷此結(jié)點(diǎn)是否是頭節(jié)點(diǎn)
# 頭節(jié)點(diǎn)
if cur == self.__head:
self.__head = cur.next
else:
pre.next = cur.next
break
else:
pre = cur
cur = cur.next
單鏈表 查找節(jié)點(diǎn)是否存在（search）
def search(self, item):
"""查找節(jié)點(diǎn)是否存在"""
cur = self.__head
while cur != None:
if cur.elem == item:
return True
else:
cur = cur.next
return False
單鏈表 完整代碼及測(cè)試
# coding:utf-8
class Node(object):
"""節(jié)點(diǎn)"""
def __init__(self, elem):
self.elem = elem
self.next = None
class SingleLinkList(object):
"""單鏈表"""
def __init__(self, node=None):
self.__head = node
def is_empty(self):
"""鏈表是否為空"""
return self.__head == None
def length(self):
"""鏈表長(zhǎng)度"""
# cur游標(biāo)，用來(lái)移動(dòng)遍歷節(jié)點(diǎn)
cur = self.__head
# count記錄數(shù)量
count = 0
while cur != None:
count += 1
cur = cur.next
return count
def travel(self):
"""遍歷整個(gè)鏈表"""
cur = self.__head
while cur != None:
print(cur.elem, end=" ")
cur = cur.next
print("")
def add(self, item):
"""鏈表頭部添加元素，頭插法"""
node = Node(item)
node.next = self.__head
self.__head = node
def append(self, item):
"""鏈表尾部添加元素, 尾插法"""
node = Node(item)
if self.is_empty():
self.__head = node
else:
cur = self.__head
while cur.next != None:
cur = cur.next
cur.next = node
def insert(self, pos, item):
"""指定位置添加元素
:param pos 從0開(kāi)始
"""
if pos <= 0:
self.add(item)
elif pos > (self.length()-1):
self.append(item)
else:
pre = self.__head
count = 0
while count < (pos-1):
count += 1
pre = pre.next
# 當(dāng)循環(huán)退出后，pre指向pos-1位置
node = Node(item)
node.next = pre.next
pre.next = node
def remove(self, item):
"""刪除節(jié)點(diǎn)"""
cur = self.__head
pre = None
while cur != None:
if cur.elem == item:
# 先判斷此結(jié)點(diǎn)是否是頭節(jié)點(diǎn)
# 頭節(jié)點(diǎn)
if cur == self.__head:
self.__head = cur.next
else:
pre.next = cur.next
break
else:
pre = cur
cur = cur.next
def search(self, item):
"""查找節(jié)點(diǎn)是否存在"""
cur = self.__head
while cur != None:
if cur.elem == item:
return True
else:
cur = cur.next
return False
if __name__ == "__main__":
ll = SingleLinkList()
print(ll.is_empty())
print(ll.length())
ll.append(1)
print(ll.is_empty())
print(ll.length())
ll.append(2)
ll.add(8)
ll.append(3)
ll.append(4)
ll.append(5)
ll.append(6)
# 8 1 2 3 4 5 6
ll.insert(-1, 9) # 9 8 1 23456
ll.travel()
ll.insert(3, 100) # 9 8 1 100 2 3456
ll.travel()
ll.insert(10, 200) # 9 8 1 100 23456 200
ll.travel()
ll.remove(100)
ll.travel()
ll.remove(9)
ll.travel()
ll.remove(200)
ll.travel()
"""
result:
True
0
False
1
9 8 1 2 3 4 5 6
9 8 1 100 2 3 4 5 6
9 8 1 100 2 3 4 5 6 200
9 8 1 2 3 4 5 6 200
8 1 2 3 4 5 6 200
8 1 2 3 4 5 6
"""鏈表與順序表的對(duì)比
鏈表失去了順序表隨機(jī)讀取的優(yōu)點(diǎn)，同時(shí)鏈表由于增加了結(jié)點(diǎn)的指針域，空間開(kāi)銷(xiāo)比較大，但對(duì)存儲(chǔ)空間的使用要相對(duì)靈活。
鏈表與順序表的各種操作復(fù)雜度如下所示：
| 操作 | 鏈表 | 順序表 |
|---|---|---|
| 訪(fǎng)問(wèn)元素 | O(n) | O(1) |
| 在頭部插入/刪除 | O(1) | O(n) |
| 在尾部插入/刪除 | O(n) | O(1) |
| 在中間插入/刪除 | O(n) | O(n) |
注意雖然表面看起來(lái)復(fù)雜度都是 O(n)，但是鏈表和順序表在插入和刪除時(shí)進(jìn)行的是完全不同的操作。鏈表的主要耗時(shí)操作是遍歷查找，刪除和插入操作本身的復(fù)雜度是O(1)。順序表查找很快，主要耗時(shí)的操作是拷貝覆蓋。因?yàn)槌四繕?biāo)元素在尾部的特殊情況，順序表進(jìn)行插入和刪除時(shí)需要對(duì)操作點(diǎn)之后的所有元素進(jìn)行前后移位操作，只能通過(guò)拷貝和覆蓋的方法進(jìn)行。
到此這篇關(guān)于Python實(shí)現(xiàn)單項(xiàng)鏈表的最全教程的文章就介紹到這了,更多相關(guān)Python實(shí)現(xiàn)單項(xiàng)鏈表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了Python接口自動(dòng)化判斷元素原理解析,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-02-02
對(duì)pytorch的函數(shù)中的group參數(shù)的作用介紹
今天小編就為大家分享一篇對(duì)pytorch的函數(shù)中的group參數(shù)的作用介紹，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2020-02-02
python模塊hashlib(加密服務(wù))知識(shí)點(diǎn)講解
在本篇文章里小編給大家分享的是關(guān)于python模塊hashlib(加密服務(wù))知識(shí)點(diǎn)內(nèi)容，有需要的朋友們可以學(xué)習(xí)下。2019-11-11
這篇文章主要給大家介紹了關(guān)于如何利用Python畫(huà)花樣圖的相關(guān)資料,文中通過(guò)示例代碼以及圖文介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2021-10-10
這篇文章主要介紹了Redis之windows下主從復(fù)制案例講解,本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-08-08
python3中的eval和exec的區(qū)別與聯(lián)系
這篇文章主要介紹了python3中的eval和exec的區(qū)別與聯(lián)系，本文給大家介紹的非常詳細(xì)，具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2019-10-10
Python用正則表達(dá)式實(shí)現(xiàn)爬取古詩(shī)文網(wǎng)站信息
這篇文章主要給大家介紹了關(guān)于Python如何利用正則表達(dá)式爬取爬取古詩(shī)文網(wǎng)站信息，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2021-12-12
Tensorflow2.1實(shí)現(xiàn)Fashion圖像分類(lèi)示例詳解
這篇文章主要為大家介紹了Tensorflow2.1實(shí)現(xiàn)Fashion圖像分類(lèi)示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-11-11
這篇文章主要介紹了Python第三方庫(kù)Click的相關(guān)資料,本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì),感興趣的朋友一起看看吧2024-12-12
平常工作生活中，boos可能會(huì)給我們很多網(wǎng)站取提取信息，這些網(wǎng)站有的無(wú)法響應(yīng)，有的404，有的501…真的需要所有網(wǎng)站都訪(fǎng)問(wèn)再提取信息嗎？今天寫(xiě)一個(gè)小工具用于篩選網(wǎng)站中能訪(fǎng)問(wèn)的網(wǎng)站，在此僅舉一例，即狀態(tài)碼為200。2021-01-01