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)，這直接導(dǎo)致了它與鏈表之間的一些重要區(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ù)的，一般需要預(yù)先設(shè)定數(shù)據(jù)長度，不能適應(yīng)數(shù)據(jù)動態(tài)的增減，當(dāng)數(shù)據(jù)增加是可能超過預(yù)設(shè)值，需要要重新分配內(nèi)存，當(dāng)數(shù)據(jù)減少時，預(yù)先申請的內(nèi)存未使用，造成內(nèi)存浪費。鏈表的數(shù)據(jù)因為是隨機存儲的，所以鏈表可以動態(tài)的分配內(nèi)存，適應(yīng)長度的動態(tài)變化

1.數(shù)組的元素是存放在棧中的，鏈表的元素在堆中
2.讀取操作：數(shù)組時間復(fù)雜度為O(1)，鏈表為O(n)
3.插入或刪除操作：數(shù)據(jù)時間復(fù)雜度為O(n)，鏈表為O(1)

列表
關(guān)于列表的存儲：

列表開辟的內(nèi)存空間是一塊連續(xù)的內(nèi)存，把這個內(nèi)存等分成幾份(單位是字節(jié))，他是連續(xù)存儲的。
如果一個列表長度已滿，再append添加元素的話，會在內(nèi)存中重新開辟一個2倍的內(nèi)存空間以存儲新元素，原列表內(nèi)存會被清除。

列表與鏈表復(fù)雜度：

按元素值查找:
  按順序查找，復(fù)雜度是一樣的。
  按二分查找，鏈表沒法查找.
按下標查找:
  列表是O( 1 )
  鏈表是O(n)
在某元素后插入:
  列表是O(n)
  鏈表是O( 1 )
刪除某元素:
  列表是O(n)
  鏈表是O( 1 )

鏈表------->列表相對應(yīng)的數(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é)點的插入和刪除操作(非常方便，時間復(fù)雜度低)

插入：

p  =  Node( 5 )  # 要插入的值
curNode  =  Node( 1 )  # 標志位
# 順序不能亂，否則就找不到原鏈表中的下一個值
p. next  =  curNode. next  # 指定插入值之后的值為標志位之后的值
curNode. next  =  p# 然后再把原先的鏈next指向改成插入的值

刪除：

curNode 代表當(dāng)前值
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）尾插法：在鏈表的尾巴上插入。相當(dāng)于是追加，必須時刻記住尾巴在哪兒

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 # 記錄當(dāng)前值
  self . next  =  None # 記錄下一個值
  self .prior  =  None# 記錄前置的一個值

2、雙鏈表節(jié)點的插入和刪除

curNode  =  Node( 1 )  # 取一數(shù)據(jù)作為標志位

1）插入：

p  =  Node( 2 )  # 要插入的數(shù)
p. next  =  curNode. next  # 指定插入數(shù)的next 是 當(dāng)前數(shù)的next
curNode. next .prior  =  p  # 指定插入數(shù)的下一個數(shù)的 前置數(shù)為當(dāng)前的數(shù)值
p.prior  =  curNode  # 插入數(shù)的前置數(shù)為 標志位
curNode. next  =  p  # 指定，標志位的next數(shù)是當(dāng)前要插入的數(shù)

2）刪除：

p  =  curNode. next  # 標志位的下一個數(shù)，要刪除的數(shù)
curNode. next  =  p. next  # 將next指向下一個數(shù)
p. next .prior  =  curNode # 將要刪除數(shù)的下一個數(shù)的前置數(shù)改為標志位
del  p  # 刪除當(dāng)前數(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指向當(dāng)前節(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  # 記錄當(dāng)前節(jié)點的值
  cur  =  link. next  # 記錄下一節(jié)點的值
  pre. next  =  None  # 先將當(dāng)前節(jié)點的next指向定為None
  
  while  cur:  # 鏈表中一直有值
tmp  =  cur. next  # 獲取cur的下一個值，臨時賦值給tmp
cur. next  =  pre  # 將cur值指向pre
pre  =  cur  # 重新指定
cur  =  tmp
  
  return  pre  # 把當(dāng)前值返回
 
#應(yīng)用
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))  # 輸出逆置后的當(dāng)前值
  r  =  r. next  # 獲取下一個，重新賦給r，然后交給上邊輸出

列表的實現(xiàn)機制

Python 標準類型 list 就是一種元素個數(shù)可變的線性表，可以加入和刪除元素，并在各種操作中維持已有元素的順序（即保序），而且還具有以下行為特征：

基于下標（位置）的高效元素訪問和更新，時間復(fù)雜度應(yīng)該是O(1)；為滿足該特征，應(yīng)該采用順序表技術(shù)，表中元素保存在一塊連續(xù)的存儲區(qū)中。
允許任意加入元素，而且在不斷加入元素的過程中，表對象的標識（函數(shù)id得到的值）不變。為滿足該特征，就必須能更換元素存儲區(qū)，并且為保證更換存儲區(qū)時 list 對象的標識 id 不變，只能采用分離式實現(xiàn)技術(shù)。

在 Python 的官方實現(xiàn)中，list 就是一種采用分離式技術(shù)實現(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)，當(dāng)使用列表迭代器的時候，雙向鏈表結(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ù)組的大小。但是，也因為這個原因添加或者取出元素是平攤復(fù)雜度較低。不幸的是，在普通鏈表上“代價很小”的其他一些操作在 Python 中計算復(fù)雜度相對較高。

總的來說，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
# 當(dāng)循環(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ù)的變更操作，但其在進行一些基礎(chǔ)簡單的操作時，時間復(fù)雜度極低。

list（列表）：動態(tài)的順序表
鏈表：存儲地址分散的，需要“指針”指向的線性表

鏈表插入刪除效率極高，達到O(1)。對于不需要搜索但變動頻繁且無法預(yù)知數(shù)量上限的數(shù)據(jù)，比如內(nèi)存池、操作系統(tǒng)的進程管理、網(wǎng)絡(luò)通信協(xié)議棧的 trunk 管理等。甚至就連很多腳本語言都有內(nèi)置的鏈表、字典等基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)支持。

列表是一個線性的集合，它允許用戶在任何位置插入、刪除、訪問和替換元素。
列表實現(xiàn)是基于數(shù)組或基于鏈表結(jié)構(gòu)的。當(dāng)使用列表迭代器的時候，雙鏈表結(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ù)組的大小。但是，也因為這個原因添加或取出元素的平攤復(fù)雜度較低。

不幸的是，在普通鏈表上“代價很小”的其它一些操作在Python中計算復(fù)雜度相對過高。

利用 list.insert(i,item) 方法在任意位置插入一個元素——復(fù)雜度O(N)
利用 list.pop(i) 或 list.remove(value) 刪除一個元素——復(fù)雜度O(N)

列表的算法效率
可以采用時間復(fù)雜度來衡量：

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括號里面的值越大代表效率越低

到此這篇關(guān)于Python 列表與鏈表的區(qū)別詳解的文章就介紹到這了,更多相關(guān)Python 列表與鏈表區(qū)別內(nèi)容請搜索本站以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持本站！

版權(quán)聲明：本站文章來源標注為YINGSOO的內(nèi)容版權(quán)均為本站所有，歡迎引用、轉(zhuǎn)載，請保持原文完整并注明來源及原文鏈接。禁止復(fù)制或仿造本網(wǎng)站，禁止在非www.sddonglingsh.com所屬的服務(wù)器上建立鏡像，否則將依法追究法律責(zé)任。本站部分內(nèi)容來源于網(wǎng)友推薦、互聯(lián)網(wǎng)收集整理而來，僅供學(xué)習(xí)參考，不代表本站立場，如有內(nèi)容涉嫌侵權(quán)，請聯(lián)系alex-e#qq.com處理。