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