Python 列表與鏈表的區(qū)別詳解
python 列表和鏈表的區(qū)別
python 中的 list 并不是我們傳統(tǒng)意義上的列表，傳統(tǒng)列表——通常也叫作鏈表(linked list)是由一系列節(jié)點來實現(xiàn)的，其中每個節(jié)點都持有一個指向下一節(jié)點的引用。
class Node: def __init__(self, value, next=None): self.value = value self.next = next
接下來，我們就可以將所有的節(jié)點構(gòu)造成一個列表了：
>>> L = Node("a", Node("b", Node("c", Node("d"))))
>>> L.next.next.value
'c'
這是一個所謂的單向鏈表，雙向鏈表的各節(jié)點中還需要持有一個指向前一個節(jié)點的引用
但 python 中的 list 則與此有所不同，它不是由若干個獨立的節(jié)點相互引用而成的，而是一整塊單一連續(xù)的內(nèi)存區(qū)塊，我們通常稱之為“數(shù)組”(array)，這直接導致了它與鏈表之間的一些重要區(qū)別。
例如如果我們要按既定的索引值對某一元素進行直接訪問的話，顯然使用數(shù)組會更有效率。因為，在數(shù)組中，我們通?？梢灾苯佑嬎愠瞿繕嗽卦趦?nèi)存中的位置，并對其進行直接訪問。而對于鏈表來說，我們必須從頭開始遍歷整個鏈表。
但是具體到 insert 操作上，情況又會有所不同。對于鏈表而言，只要知道了要在哪里執(zhí)行 insert 操作，其操作成本是非常低的，無論該列表中有多少元素，其操作時間大致上是相同的。而數(shù)組就不一樣了，它每次執(zhí)行 insert 操作都需要移動插入點右邊的所有元素，甚至在必要的時候，我們可能還需要將這些列表元素整體搬到一個更大的數(shù)組中去。
也正因如此，append 操作通常會采取一種被稱為動態(tài)數(shù)組或‘向量'的指定解決方案，其主要想法是將內(nèi)存分配的過大一些，并且等到其溢出時，在線性時間內(nèi)再次重新分配內(nèi)存。但這樣做似乎會使 append 變得跟 insert一樣糟糕。其實不然，因為盡管這兩種情況都可能會迫使我們?nèi)グ釀哟罅康脑?，但主要不同點在于，對于 append 操作，發(fā)生這樣的可能性要小得多。事實上，如果我們能確保每次所搬入的數(shù)組都大過原數(shù)組一定的比例(例如大20%甚至100%)，那么該操作的平均成本(或者說得更確切一些，將這些搬運開銷均攤到每次 append 操作中去)通常是常數(shù)!
數(shù)組數(shù)據(jù)是連續(xù)的，一般需要預先設定數(shù)據(jù)長度，不能適應數(shù)據(jù)動態(tài)的增減，當數(shù)據(jù)增加是可能超過預設值，需要要重新分配內(nèi)存，當數(shù)據(jù)減少時，預先申請的內(nèi)存未使用，造成內(nèi)存浪費。鏈表的數(shù)據(jù)因為是隨機存儲的，所以鏈表可以動態(tài)的分配內(nèi)存，適應長度的動態(tài)變化
1.數(shù)組的元素是存放在棧中的，鏈表的元素在堆中
2.讀取操作：數(shù)組時間復雜度為O(1)，鏈表為O(n)
3.插入或刪除操作：數(shù)據(jù)時間復雜度為O(n)，鏈表為O(1)
列表
關于列表的存儲：
列表開辟的內(nèi)存空間是一塊連續(xù)的內(nèi)存，把這個內(nèi)存等分成幾份(單位是字節(jié))，他是連續(xù)存儲的。
如果一個列表長度已滿，再append添加元素的話，會在內(nèi)存中重新開辟一個2倍的內(nèi)存空間以存儲新元素，原列表內(nèi)存會被清除。
列表與鏈表復雜度：
按元素值查找:
按順序查找，復雜度是一樣的。
按二分查找，鏈表沒法查找.
按下標查找:
列表是O( 1 )
鏈表是O(n)
在某元素后插入:
列表是O(n)
鏈表是O( 1 )
刪除某元素:
列表是O(n)
鏈表是O( 1 )
鏈表------->列表相對應的數(shù)據(jù)結(jié)構(gòu)
鏈表是一種線性數(shù)據(jù)結(jié)構(gòu)（與樹形結(jié)構(gòu)相對），不是進行連續(xù)存儲的。
鏈表中每一個元素都是一個對象，每個對象稱為一個節(jié)點，包含有數(shù)據(jù)域key和執(zhí)行下一個節(jié)點的指針next。通過各個節(jié)點之間的相互連接，最終串聯(lián)成一個鏈表。
1、存儲的過程中，需要先創(chuàng)建節(jié)點，然后進行定義。
# 節(jié)點定義： class Node( object ): def __init__( self ,item): self .item = item # 數(shù)據(jù)域 self . next = None # 指針域 n1 = Node( 1 ) n2 = Node( 2 ) n3 = Node( 3 ) n1. next = n2 n2. next = n3 # 通過 n1 找到n3的值 print (n1. next . next .item)
只保留頭結(jié)點，執(zhí)行第一個位置，剩下的都是next去指定。
2、鏈表遍歷：(頭節(jié)點的變動)
# 節(jié)點定義： class Node( object ): def __init__( self ,item): self .item = item # 數(shù)據(jù)域 self . next = None # 指針域 n1 = Node( 1 ) n2 = Node( 2 ) n3 = Node( 3 ) n1. next = n2 n2. next = n3 # 通過 n1 找到n3的值 print (n1. next . next .item)
3、鏈表節(jié)點的插入和刪除操作(非常方便，時間復雜度低)
插入：
p = Node( 5 ) # 要插入的值 curNode = Node( 1 ) # 標志位 # 順序不能亂，否則就找不到原鏈表中的下一個值 p. next = curNode. next # 指定插入值之后的值為標志位之后的值 curNode. next = p # 然后再把原先的鏈next指向改成插入的值
刪除：
curNode 代表當前值 p = curNode. next # 表示要刪除的數(shù) curNode. next = p. next # 重新指定建立鏈表 del p 刪除數(shù)
4、建立鏈表（單鏈表）
1）頭插法：是在head頭節(jié)點的位置后插入數(shù)；得到的鏈表與原先的列表順序是相反的。
def createLinkListF(li):
l = Node() # 始終指向頭節(jié)點
for num in li:
s = Node(num)
s. next = l. next
l. next = s
return l
2）尾插法：在鏈表的尾巴上插入。相當于是追加，必須時刻記住尾巴在哪兒
def createLinkListR(li):
l = Node()
r = l # r指向尾節(jié)點
for num in li:
s = Node(num):
r. next = s
r = s # 重新指定尾節(jié)點
雙鏈表
雙鏈表中每個節(jié)點有兩個指針：一個指向后面節(jié)點，一個指向前面節(jié)點。
1、節(jié)點定義：
class Node( object ):
def __init__( self ,item = None ):
self .item = item # 記錄當前值
self . next = None # 記錄下一個值
self .prior = None # 記錄前置的一個值
2、雙鏈表節(jié)點的插入和刪除
curNode = Node( 1 ) # 取一數(shù)據(jù)作為標志位
1）插入：
p = Node( 2 ) # 要插入的數(shù) p. next = curNode. next # 指定插入數(shù)的next 是 當前數(shù)的next curNode. next .prior = p # 指定插入數(shù)的下一個數(shù)的 前置數(shù)為當前的數(shù)值 p.prior = curNode # 插入數(shù)的前置數(shù)為 標志位 curNode. next = p # 指定，標志位的next數(shù)是當前要插入的數(shù)
2）刪除：
p = curNode. next # 標志位的下一個數(shù)，要刪除的數(shù) curNode. next = p. next # 將next指向下一個數(shù) p. next .prior = curNode # 將要刪除數(shù)的下一個數(shù)的前置數(shù)改為標志位 del p # 刪除當前數(shù)
3、建立雙鏈表
尾插法：
def createLinkListR(li):
l = Node()
r = l
for num in li:
s = Node(num)
r. next = s
s.prior = r
r = s
return l,r
單鏈表逆置
循環(huán)反轉(zhuǎn)單鏈表。在循環(huán)的方法中，使用pre指向前一個節(jié)點，cur指向當前節(jié)點，每次把cur->next指向pre即可。
# 創(chuàng)建節(jié)點
class Node( object ):
def __init__( self ,item = None , next = None ):
self .item = item # 數(shù)據(jù)域
self . next = next # 指針域
# 循環(huán)逆置方法
def revLinkList(link):
if link is None or link. next is None :
return link
pre = link # 記錄當前節(jié)點的值
cur = link. next # 記錄下一節(jié)點的值
pre. next = None # 先將當前節(jié)點的next指向定為None
while cur: # 鏈表中一直有值
tmp = cur. next # 獲取cur的下一個值，臨時賦值給tmp
cur. next = pre # 將cur值指向pre
pre = cur # 重新指定
cur = tmp
return pre # 把當前值返回
#應用
link = Node( 1 , Node( 2 , Node( 3 , Node( 4 , Node( 5 , Node( 6 , Node( 7 , Node( 8 , Node( 9 )))))))))
r = revLinkList(link): # 鏈表逆置之后，得到的head值
while r:
print ( "{0}---->" . format (r.item)) # 輸出逆置后的當前值
r = r. next # 獲取下一個，重新賦給r，然后交給上邊輸出
列表的實現(xiàn)機制
Python 標準類型 list 就是一種元素個數(shù)可變的線性表，可以加入和刪除元素，并在各種操作中維持已有元素的順序（即保序），而且還具有以下行為特征：
基于下標（位置）的高效元素訪問和更新，時間復雜度應該是O(1)；為滿足該特征，應該采用順序表技術，表中元素保存在一塊連續(xù)的存儲區(qū)中。 允許任意加入元素，而且在不斷加入元素的過程中，表對象的標識（函數(shù)id得到的值）不變。為滿足該特征，就必須能更換元素存儲區(qū)，并且為保證更換存儲區(qū)時 list 對象的標識 id 不變，只能采用分離式實現(xiàn)技術。
在 Python 的官方實現(xiàn)中，list 就是一種采用分離式技術實現(xiàn)的動態(tài)順序表。這就是為什么用 list.append(x) （或 list.insert(len(list), x)，即尾部插入）比在指定位置插入元素效率高的原因。
在 Python 的官方實現(xiàn)中，list 實現(xiàn)采用了如下的策略：在建立空表（或者很小的表）時，系統(tǒng)分配一塊能容納 8 個元素的存儲區(qū)；在執(zhí)行插入操作（insert 或 append）時，如果元素存儲區(qū)滿就換一塊 4 倍大的存儲區(qū)。但如果此時的表已經(jīng)很大（目前的閥值為50000），則改變策略，采用加一倍的方法。引入這種改變策略的方式，是為了避免出現(xiàn)過多空閑的存儲位置。
列表的實現(xiàn)可以是數(shù)組或者鏈表。列表是一種順序表，順序表一般是數(shù)組。列表是一個線性表，它允許用戶在任何位置進行插入、刪除、訪問和替換元素。
列表的實現(xiàn)是基于數(shù)組或者基于鏈表結(jié)構(gòu)，當使用列表迭代器的時候，雙向鏈表結(jié)構(gòu)比單鏈表結(jié)構(gòu)更快。
Python 中的列表英文名是 list，因此很容易與 C 語言中的鏈表搞混了，因為在 C 語言中大家經(jīng)常給鏈表命名為 list。事實上 CPython，也是我們常見的用 C 語言開發(fā)的 Python 解釋器，Python 語言底層是 C 語言實現(xiàn)的）中的列表根本不是列表。在 CPython 中列表被實現(xiàn)為長度可變的數(shù)組。
從細節(jié)上看，Python 中的列表是由其他對象的引用組成的連續(xù)數(shù)組，指向這個數(shù)組的指針及其長度被保存在一個列表頭結(jié)構(gòu)中。這就意味著，每次添加或刪除一個元素時，由引用組成的數(shù)組需要改變大?。ㄖ匦路峙洌?。幸運的是，Python在創(chuàng)建這些數(shù)組時采用了指數(shù)分配，所以并不是每次操作都要改變數(shù)組的大小。但是，也因為這個原因添加或者取出元素是平攤復雜度較低。不幸的是，在普通鏈表上“代價很小”的其他一些操作在 Python 中計算復雜度相對較高。
總的來說，Python中的列表是一個動態(tài)的順序表，而順序表大多是由數(shù)組實現(xiàn)的。
鏈表
鏈表是由許多相同數(shù)據(jù)類型的數(shù)據(jù)項按照特定的順序排列而成的線性表。鏈表中的數(shù)據(jù)項在計算機的內(nèi)存中的位置是不連續(xù)且隨機的，然而列表是連續(xù)的。鏈表數(shù)據(jù)的插入和刪除是很方便的，但數(shù)據(jù)的查找效率較低，不能像列表一樣隨機讀取數(shù)據(jù)。
鏈表由一個一個的結(jié)點構(gòu)成，每個結(jié)點由數(shù)據(jù)域和“指針域”組成，數(shù)據(jù)域存儲數(shù)字，“指針域”指向下一個結(jié)點所在的內(nèi)存地址。（因為Python 中沒有指針這一概念的，這里的指針是一種指向）
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é)點
# 頭節(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
鏈表與列表的差異
Python 中的 list（列表）并不是傳統(tǒng)意義上的列表，傳統(tǒng)的意義上的列表就是鏈表，不同地方在于鏈表在數(shù)據(jù)存儲方面更加的自由，其帶有指示下一個結(jié)點未知的指向，可以隨意的存儲數(shù)據(jù)。而列表則只能分配在一段連續(xù)的存儲空間里，且是作為一個整體，這就大大限制了數(shù)據(jù)的變更操作，但其在進行一些基礎簡單的操作時，時間復雜度極低。
list（列表）：動態(tài)的順序表
鏈表：存儲地址分散的，需要“指針”指向的線性表
鏈表插入刪除效率極高，達到O(1)。對于不需要搜索但變動頻繁且無法預知數(shù)量上限的數(shù)據(jù)，比如內(nèi)存池、操作系統(tǒng)的進程管理、網(wǎng)絡通信協(xié)議棧的 trunk 管理等。甚至就連很多腳本語言都有內(nèi)置的鏈表、字典等基礎數(shù)據(jù)結(jié)構(gòu)支持。
列表是一個線性的集合，它允許用戶在任何位置插入、刪除、訪問和替換元素。
列表實現(xiàn)是基于數(shù)組或基于鏈表結(jié)構(gòu)的。當使用列表迭代器的時候，雙鏈表結(jié)構(gòu)比單鏈表結(jié)構(gòu)更快。
有序的列表是元素總是按照升序或者降序排列的元素。
實現(xiàn)細節(jié)
python中的列表的英文名是list，因此很容易和其它語言(C++, Java等)標準庫中常見的鏈表混淆。事實上CPython的列表根本不是列表（可能換成英文理解起來容易些：python中的list不是list）。在CPython中，列表被實現(xiàn)為長度可變的數(shù)組。
可參考《Python高級編程（第2版）》
從細節(jié)上看，Python中的列表是由對其它對象的引用組成的連續(xù)數(shù)組。指向這個數(shù)組的指針及其長度被保存在一個列表頭結(jié)構(gòu)中。這意味著，每次添加或刪除一個元素時，由引用組成的數(shù)組需要該標大?。ㄖ匦路峙洌Ｐ疫\的是，Python在創(chuàng)建這些數(shù)組時采用了指數(shù)分配，所以并不是每次操作都需要改變數(shù)組的大小。但是，也因為這個原因添加或取出元素的平攤復雜度較低。
不幸的是，在普通鏈表上“代價很小”的其它一些操作在Python中計算復雜度相對過高。
利用 list.insert(i,item) 方法在任意位置插入一個元素——復雜度O(N)
利用 list.pop(i) 或 list.remove(value) 刪除一個元素——復雜度O(N)
列表的算法效率
可以采用時間復雜度來衡量：
index() O(1)
append O(1)
pop() O(1)
pop(i) O(n)
insert(i,item) O(n)
del operator O(n)
iteration O(n)
contains(in) O(n)
get slice[x:y] O(k)
del slice O(n)
set slice O(n+k)
reverse O(n)
concatenate O(k)
sort O(nlogn)
multiply O(nk)
O括號里面的值越大代表效率越低
到此這篇關于Python 列表與鏈表的區(qū)別詳解的文章就介紹到這了,更多相關Python 列表與鏈表區(qū)別內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
今天小編就為大家分享一篇python 美化輸出信息的實例，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-10-10
下面小編就為大家分享一篇python刪除不需要的python文件方法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-04-04
這篇文章主要介紹了自己編程中遇到的Python錯誤和解決方法匯總整理,本文收集整理了較多的案例,需要的朋友可以參考下2015-06-06
今天小編就為大家分享一篇關于Tensorflow使用CPU報錯的解決方式，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-02-02
這篇文章主要介紹了python實現(xiàn)ping的方法,以實例形式較為詳細的分析了Python發(fā)送ICMP數(shù)據(jù)包實現(xiàn)ping功能的相關技巧,需要的朋友可以參考下2015-07-07
Anaconda+VSCode配置tensorflow開發(fā)環(huán)境的教程詳解
Anaconda是一個開源的python發(fā)行版本，是現(xiàn)在比較流行的python數(shù)據(jù)科學平臺，可以對python的科學包做到有效管理。這篇文章主要介紹了Anaconda+VSCode配置tensorflow開發(fā)環(huán)境,需要的朋友可以參考下2020-03-03
解決python-docx打包之后找不到default.docx的問題
今天小編就為大家分享一篇解決python-docx打包之后找不到default.docx的問題，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-02-02
今天小編就為大家分享一篇解決Mac下使用python的坑，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-08-08
深入解析Python的Tornado框架中內(nèi)置的模板引擎
模板引擎是Web開發(fā)框架中負責前端展示的關鍵,這里我們就來以實例深入解析Python的Tornado框架中內(nèi)置的模板引擎,來學習如何編寫Tonardo的模板.2016-07-07
Pandas常用的數(shù)據(jù)結(jié)構(gòu)和常用的數(shù)據(jù)分析技術
Pandas是Python中用于數(shù)據(jù)處理和分析的強大庫，其最常用的數(shù)據(jù)結(jié)構(gòu)是Series和DataFrame。Series類似于一維數(shù)組，可以表示一列數(shù)據(jù)；DataFrame類似于二維表格，可以表示多列數(shù)據(jù)2023-04-04