python 列表和鏈表的區(qū)別

python 中的 list 并不是我們傳統(tǒng)意義上的列表，傳統(tǒng)列表——通常也叫作鏈表(linked list)是由一系列節(jié)點(diǎn)來(lái)實(shí)現(xiàn)的，其中每個(gè)節(jié)點(diǎn)都持有一個(gè)指向下一節(jié)點(diǎn)的引用。

class Node:
	def __init__(self, value, next=None):	
		self.value = value		
		self.next = next

接下來(lái)，我們就可以將所有的節(jié)點(diǎn)構(gòu)造成一個(gè)列表了：

>>> L = Node("a", Node("b", Node("c", Node("d"))))
>>> L.next.next.value
'c'

這是一個(gè)所謂的單向鏈表，雙向鏈表的各節(jié)點(diǎn)中還需要持有一個(gè)指向前一個(gè)節(jié)點(diǎn)的引用

但 python 中的 list 則與此有所不同，它不是由若干個(gè)獨(dú)立的節(jié)點(diǎn)相互引用而成的，而是一整塊單一連續(xù)的內(nèi)存區(qū)塊，我們通常稱之為“數(shù)組”(array)，這直接導(dǎo)致了它與鏈表之間的一些重要區(qū)別。

例如如果我們要按既定的索引值對(duì)某一元素進(jìn)行直接訪問的話，顯然使用數(shù)組會(huì)更有效率。因?yàn)?，在?shù)組中，我們通?？梢灾苯佑?jì)算出目標(biāo)元素在內(nèi)存中的位置，并對(duì)其進(jìn)行直接訪問。而對(duì)于鏈表來(lái)說(shuō)，我們必須從頭開始遍歷整個(gè)鏈表。

但是具體到 insert 操作上，情況又會(huì)有所不同。對(duì)于鏈表而言，只要知道了要在哪里執(zhí)行 insert 操作，其操作成本是非常低的，無(wú)論該列表中有多少元素，其操作時(shí)間大致上是相同的。而數(shù)組就不一樣了，它每次執(zhí)行 insert 操作都需要移動(dòng)插入點(diǎn)右邊的所有元素，甚至在必要的時(shí)候，我們可能還需要將這些列表元素整體搬到一個(gè)更大的數(shù)組中去。

也正因如此，append 操作通常會(huì)采取一種被稱為動(dòng)態(tài)數(shù)組或‘向量'的指定解決方案，其主要想法是將內(nèi)存分配的過(guò)大一些，并且等到其溢出時(shí)，在線性時(shí)間內(nèi)再次重新分配內(nèi)存。但這樣做似乎會(huì)使 append 變得跟 insert一樣糟糕。其實(shí)不然，因?yàn)楸M管這兩種情況都可能會(huì)迫使我們?nèi)グ釀?dòng)大量的元素，但主要不同點(diǎn)在于，對(duì)于 append 操作，發(fā)生這樣的可能性要小得多。事實(shí)上，如果我們能確保每次所搬入的數(shù)組都大過(guò)原數(shù)組一定的比例(例如大20%甚至100%)，那么該操作的平均成本(或者說(shuō)得更確切一些，將這些搬運(yùn)開銷均攤到每次 append 操作中去)通常是常數(shù)!

數(shù)組數(shù)據(jù)是連續(xù)的，一般需要預(yù)先設(shè)定數(shù)據(jù)長(zhǎng)度，不能適應(yīng)數(shù)據(jù)動(dòng)態(tài)的增減，當(dāng)數(shù)據(jù)增加是可能超過(guò)預(yù)設(shè)值，需要要重新分配內(nèi)存，當(dāng)數(shù)據(jù)減少時(shí)，預(yù)先申請(qǐng)的內(nèi)存未使用，造成內(nèi)存浪費(fèi)。鏈表的數(shù)據(jù)因?yàn)槭请S機(jī)存儲(chǔ)的，所以鏈表可以動(dòng)態(tài)的分配內(nèi)存，適應(yīng)長(zhǎng)度的動(dòng)態(tài)變化

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

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

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

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

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

鏈表------->列表相對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)
鏈表是一種線性數(shù)據(jù)結(jié)構(gòu)（與樹形結(jié)構(gòu)相對(duì)），不是進(jìn)行連續(xù)存儲(chǔ)的。
鏈表中每一個(gè)元素都是一個(gè)對(duì)象，每個(gè)對(duì)象稱為一個(gè)節(jié)點(diǎn)，包含有數(shù)據(jù)域key和執(zhí)行下一個(gè)節(jié)點(diǎn)的指針next。通過(guò)各個(gè)節(jié)點(diǎn)之間的相互連接，最終串聯(lián)成一個(gè)鏈表。
1、存儲(chǔ)的過(guò)程中，需要先創(chuàng)建節(jié)點(diǎn)，然后進(jìn)行定義。

# 節(jié)點(diǎn)定義：
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
# 通過(guò) n1 找到n3的值
print (n1. next . next .item)

只保留頭結(jié)點(diǎn)，執(zhí)行第一個(gè)位置，剩下的都是next去指定。

2、鏈表遍歷：(頭節(jié)點(diǎn)的變動(dòng))

# 節(jié)點(diǎn)定義：
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
# 通過(guò) n1 找到n3的值
print (n1. next . next .item)

3、鏈表節(jié)點(diǎn)的插入和刪除操作(非常方便，時(shí)間復(fù)雜度低)

插入：

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

刪除：

curNode 代表當(dāng)前值
p  =  curNode. next  # 表示要?jiǎng)h除的數(shù)
curNode. next  =  p. next  # 重新指定建立鏈表
del  p 刪除數(shù)

4、建立鏈表（單鏈表）

1）頭插法：是在head頭節(jié)點(diǎn)的位置后插入數(shù)；得到的鏈表與原先的列表順序是相反的。

def  createLinkListF(li):
　　l  =  Node()  # 始終指向頭節(jié)點(diǎn)
　　 for  num  in  li:
  s  =  Node(num)
  s. next  =  l. next
  l. next  =  s
　　 return  l

2）尾插法：在鏈表的尾巴上插入。相當(dāng)于是追加，必須時(shí)刻記住尾巴在哪兒

def  createLinkListR(li):
　　l  =  Node()
　　r  =  l  # r指向尾節(jié)點(diǎn)
　　 for  num  in  li:
  s  =  Node(num):
  r. next  =  s
  r  =  s  # 重新指定尾節(jié)點(diǎn)

雙鏈表
雙鏈表中每個(gè)節(jié)點(diǎn)有兩個(gè)指針：一個(gè)指向后面節(jié)點(diǎn)，一個(gè)指向前面節(jié)點(diǎn)。

1、節(jié)點(diǎn)定義：

class  Node( object ):
　　 def  __init__( self ,item = None ):
  self .item  =  item # 記錄當(dāng)前值
  self . next  =  None # 記錄下一個(gè)值
  self .prior  =  None# 記錄前置的一個(gè)值

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

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

1）插入：

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

2）刪除：

p  =  curNode. next  # 標(biāo)志位的下一個(gè)數(shù)，要?jiǎng)h除的數(shù)
curNode. next  =  p. next  # 將next指向下一個(gè)數(shù)
p. next .prior  =  curNode # 將要?jiǎng)h除數(shù)的下一個(gè)數(shù)的前置數(shù)改為標(biāo)志位
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指向前一個(gè)節(jié)點(diǎn)，cur指向當(dāng)前節(jié)點(diǎn)，每次把cur->next指向pre即可。

# 創(chuàng)建節(jié)點(diǎn) 
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é)點(diǎn)的值
  cur  =  link. next  # 記錄下一節(jié)點(diǎn)的值
  pre. next  =  None  # 先將當(dāng)前節(jié)點(diǎn)的next指向定為None
  
  while  cur:  # 鏈表中一直有值
tmp  =  cur. next  # 獲取cur的下一個(gè)值，臨時(shí)賦值給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  # 獲取下一個(gè)，重新賦給r，然后交給上邊輸出

列表的實(shí)現(xiàn)機(jī)制

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

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

在 Python 的官方實(shí)現(xiàn)中，list 就是一種采用分離式技術(shù)實(shí)現(xiàn)的動(dòng)態(tài)順序表。這就是為什么用 list.append(x) （或 list.insert(len(list), x)，即尾部插入）比在指定位置插入元素效率高的原因。

在 Python 的官方實(shí)現(xiàn)中，list 實(shí)現(xiàn)采用了如下的策略：在建立空表（或者很小的表）時(shí)，系統(tǒng)分配一塊能容納 8 個(gè)元素的存儲(chǔ)區(qū)；在執(zhí)行插入操作（insert 或 append）時(shí)，如果元素存儲(chǔ)區(qū)滿就換一塊 4 倍大的存儲(chǔ)區(qū)。但如果此時(shí)的表已經(jīng)很大（目前的閥值為50000），則改變策略，采用加一倍的方法。引入這種改變策略的方式，是為了避免出現(xiàn)過(guò)多空閑的存儲(chǔ)位置。

列表的實(shí)現(xiàn)可以是數(shù)組或者鏈表。列表是一種順序表，順序表一般是數(shù)組。列表是一個(gè)線性表，它允許用戶在任何位置進(jìn)行插入、刪除、訪問和替換元素。

列表的實(shí)現(xiàn)是基于數(shù)組或者基于鏈表結(jié)構(gòu)，當(dāng)使用列表迭代器的時(shí)候，雙向鏈表結(jié)構(gòu)比單鏈表結(jié)構(gòu)更快。
Python 中的列表英文名是 list，因此很容易與 C 語(yǔ)言中的鏈表搞混了，因?yàn)樵?C 語(yǔ)言中大家經(jīng)常給鏈表命名為 list。事實(shí)上 CPython，也是我們常見的用 C 語(yǔ)言開發(fā)的 Python 解釋器，Python 語(yǔ)言底層是 C 語(yǔ)言實(shí)現(xiàn)的）中的列表根本不是列表。在 CPython 中列表被實(shí)現(xiàn)為長(zhǎng)度可變的數(shù)組。

從細(xì)節(jié)上看，Python 中的列表是由其他對(duì)象的引用組成的連續(xù)數(shù)組，指向這個(gè)數(shù)組的指針及其長(zhǎng)度被保存在一個(gè)列表頭結(jié)構(gòu)中。這就意味著，每次添加或刪除一個(gè)元素時(shí)，由引用組成的數(shù)組需要改變大?。ㄖ匦路峙洌?。幸運(yùn)的是，Python在創(chuàng)建這些數(shù)組時(shí)采用了指數(shù)分配，所以并不是每次操作都要改變數(shù)組的大小。但是，也因?yàn)檫@個(gè)原因添加或者取出元素是平攤復(fù)雜度較低。不幸的是，在普通鏈表上“代價(jià)很小”的其他一些操作在 Python 中計(jì)算復(fù)雜度相對(duì)較高。

總的來(lái)說(shuō)，Python中的列表是一個(gè)動(dòng)態(tài)的順序表，而順序表大多是由數(shù)組實(shí)現(xiàn)的。

鏈表

鏈表是由許多相同數(shù)據(jù)類型的數(shù)據(jù)項(xiàng)按照特定的順序排列而成的線性表。鏈表中的數(shù)據(jù)項(xiàng)在計(jì)算機(jī)的內(nèi)存中的位置是不連續(xù)且隨機(jī)的，然而列表是連續(xù)的。鏈表數(shù)據(jù)的插入和刪除是很方便的，但數(shù)據(jù)的查找效率較低，不能像列表一樣隨機(jī)讀取數(shù)據(jù)。
鏈表由一個(gè)一個(gè)的結(jié)點(diǎn)構(gòu)成，每個(gè)結(jié)點(diǎn)由數(shù)據(jù)域和“指針域”組成，數(shù)據(jù)域存儲(chǔ)數(shù)字，“指針域”指向下一個(gè)結(jié)點(diǎn)所在的內(nèi)存地址。（因?yàn)镻ython 中沒有指針這一概念的，這里的指針是一種指向）

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開始
  """
  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

鏈表與列表的差異

Python 中的 list（列表）并不是傳統(tǒng)意義上的列表，傳統(tǒng)的意義上的列表就是鏈表，不同地方在于鏈表在數(shù)據(jù)存儲(chǔ)方面更加的自由，其帶有指示下一個(gè)結(jié)點(diǎn)未知的指向，可以隨意的存儲(chǔ)數(shù)據(jù)。而列表則只能分配在一段連續(xù)的存儲(chǔ)空間里，且是作為一個(gè)整體，這就大大限制了數(shù)據(jù)的變更操作，但其在進(jìn)行一些基礎(chǔ)簡(jiǎn)單的操作時(shí)，時(shí)間復(fù)雜度極低。

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

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

列表是一個(gè)線性的集合，它允許用戶在任何位置插入、刪除、訪問和替換元素。
列表實(shí)現(xiàn)是基于數(shù)組或基于鏈表結(jié)構(gòu)的。當(dāng)使用列表迭代器的時(shí)候，雙鏈表結(jié)構(gòu)比單鏈表結(jié)構(gòu)更快。
有序的列表是元素總是按照升序或者降序排列的元素。

實(shí)現(xiàn)細(xì)節(jié)
python中的列表的英文名是list，因此很容易和其它語(yǔ)言(C++, Java等)標(biāo)準(zhǔn)庫(kù)中常見的鏈表混淆。事實(shí)上CPython的列表根本不是列表（可能換成英文理解起來(lái)容易些：python中的list不是list）。在CPython中，列表被實(shí)現(xiàn)為長(zhǎng)度可變的數(shù)組。

可參考《Python高級(jí)編程（第2版）》

從細(xì)節(jié)上看，Python中的列表是由對(duì)其它對(duì)象的引用組成的連續(xù)數(shù)組。指向這個(gè)數(shù)組的指針及其長(zhǎng)度被保存在一個(gè)列表頭結(jié)構(gòu)中。這意味著，每次添加或刪除一個(gè)元素時(shí)，由引用組成的數(shù)組需要該標(biāo)大小（重新分配）。幸運(yùn)的是，Python在創(chuàng)建這些數(shù)組時(shí)采用了指數(shù)分配，所以并不是每次操作都需要改變數(shù)組的大小。但是，也因?yàn)檫@個(gè)原因添加或取出元素的平攤復(fù)雜度較低。

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

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

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

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

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

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