Python 列表與鏈表的區別詳解

 更新時間:2021年09月10日 10:15:57   作者:Yake1965  
這篇文章主要介紹了Python 列表與鏈表的區別詳解,本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內容,需要的朋友可以參考下

python 列表和鏈表的區別

python 中的 list 并不是我們傳統意義上的列表,傳統列表——通常也叫作鏈表(linked list)是由一系列節點來實現的,其中每個節點都持有一個指向下一節點的引用。

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

接下來,我們就可以將所有的節點構造成一個列表了:

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

這是一個所謂的單向鏈表,雙向鏈表的各節點中還需要持有一個指向前一個節點的引用

但 python 中的 list 則與此有所不同,它不是由若干個獨立的節點相互引用而成的,而是一整塊單一連續的內存區塊,我們通常稱之為“數組”(array),這直接導致了它與鏈表之間的一些重要區別。

例如如果我們要按既定的索引值對某一元素進行直接訪問的話,顯然使用數組會更有效率。因為,在數組中,我們通常可以直接計算出目標元素在內存中的位置,并對其進行直接訪問。而對于鏈表來說,我們必須從頭開始遍歷整個鏈表。

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

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

數組數據是連續的,一般需要預先設定數據長度,不能適應數據動態的增減,當數據增加是可能超過預設值,需要要重新分配內存,當數據減少時,預先申請的內存未使用,造成內存浪費。鏈表的數據因為是隨機存儲的,所以鏈表可以動態的分配內存,適應長度的動態變化

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

列表
關于列表的存儲:

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

列表與鏈表復雜度:

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

鏈表------->列表相對應的數據結構
鏈表是一種線性數據結構(與樹形結構相對),不是進行連續存儲的。
鏈表中每一個元素都是一個對象,每個對象稱為一個節點,包含有數據域key和執行下一個節點的指針next。通過各個節點之間的相互連接,最終串聯成一個鏈表。
1、存儲的過程中,需要先創建節點,然后進行定義。

# 節點定義:
class  Node( object ):     
   def  __init__( self ,item):
	     self .item  =  item  # 數據域
	     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)

只保留頭結點,執行第一個位置,剩下的都是next去指定。

2、鏈表遍歷:(頭節點的變動)

在這里插入圖片描述

# 節點定義:
class  Node( object ):     
   def  __init__( self ,item):
	     self .item  =  item  # 數據域
	     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、鏈表節點的插入和刪除操作(非常方便,時間復雜度低)

插入:

在這里插入圖片描述

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

刪除:

在這里插入圖片描述

curNode 代表當前值
p  =  curNode. next  # 表示要刪除的數
curNode. next  =  p. next  # 重新指定建立鏈表
del  p 刪除數

4、建立鏈表(單鏈表)

在這里插入圖片描述

1)頭插法:是在head頭節點的位置后插入數;得到的鏈表與原先的列表順序是相反的。

在這里插入圖片描述

def  createLinkListF(li):
  l  =  Node()  # 始終指向頭節點
   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指向尾節點
   for  num  in  li:
     s  =  Node(num):
     r. next  =  s
     r  =  s  # 重新指定尾節點

雙鏈表
雙鏈表中每個節點有兩個指針:一個指向后面節點,一個指向前面節點。

在這里插入圖片描述

1、節點定義:

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

2、雙鏈表節點的插入和刪除

在這里插入圖片描述

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

1)插入:

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

2)刪除:

p  =  curNode. next  # 標志位的下一個數,要刪除的數
curNode. next  =  p. next  # 將next指向下一個數
p. next .prior  =  curNode # 將要刪除數的下一個數的前置數改為標志位
del  p  # 刪除當前數

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
 

單鏈表逆置

在這里插入圖片描述

循環反轉單鏈表。在循環的方法中,使用pre指向前一個節點,cur指向當前節點,每次把cur->next指向pre即可。

# 創建節點 
class  Node( object ):
     
     def  __init__( self ,item = None , next = None ):
         self .item  =  item  # 數據域
         self . next  =  next  # 指針域 
 
# 循環逆置方法
def  revLinkList(link):
     
     if  link  is  None  or  link. next  is  None :
         return  link
         
     pre  =  link  # 記錄當前節點的值
     cur  =  link. next  # 記錄下一節點的值
     pre. next  =  None  # 先將當前節點的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,然后交給上邊輸出

列表的實現機制

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

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

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

在 Python 的官方實現中,list 實現采用了如下的策略:在建立空表(或者很小的表)時,系統分配一塊能容納 8 個元素的存儲區;在執行插入操作(insert 或 append)時,如果元素存儲區滿就換一塊 4 倍大的存儲區。但如果此時的表已經很大(目前的閥值為50000),則改變策略,采用加一倍的方法。引入這種改變策略的方式,是為了避免出現過多空閑的存儲位置。

列表的實現可以是數組或者鏈表。列表是一種順序表,順序表一般是數組。列表是一個線性表,它允許用戶在任何位置進行插入、刪除、訪問和替換元素。

列表的實現是基于數組或者基于鏈表結構,當使用列表迭代器的時候,雙向鏈表結構比單鏈表結構更快。
Python 中的列表英文名是 list,因此很容易與 C 語言中的鏈表搞混了,因為在 C 語言中大家經常給鏈表命名為 list。事實上 CPython,也是我們常見的用 C 語言開發的 Python 解釋器,Python 語言底層是 C 語言實現的)中的列表根本不是列表。在 CPython 中列表被實現為長度可變的數組。

從細節上看,Python 中的列表是由其他對象的引用組成的連續數組,指向這個數組的指針及其長度被保存在一個列表頭結構中。這就意味著,每次添加或刪除一個元素時,由引用組成的數組需要改變大小(重新分配)。幸運的是,Python在創建這些數組時采用了指數分配,所以并不是每次操作都要改變數組的大小。但是,也因為這個原因添加或者取出元素是平攤復雜度較低。不幸的是,在普通鏈表上“代價很小”的其他一些操作在 Python 中計算復雜度相對較高。

總的來說,Python中的列表是一個動態的順序表,而順序表大多是由數組實現的。

鏈表

鏈表是由許多相同數據類型的數據項按照特定的順序排列而成的線性表。鏈表中的數據項在計算機的內存中的位置是不連續且隨機的,然而列表是連續的。鏈表數據的插入和刪除是很方便的,但數據的查找效率較低,不能像列表一樣隨機讀取數據。
鏈表由一個一個的結點構成,每個結點由數據域和“指針域”組成,數據域存儲數字,“指針域”指向下一個結點所在的內存地址。(因為Python 中沒有指針這一概念的,這里的指針是一種指向)

class Node(object):
    """節點"""
    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游標,用來移動遍歷節點
        cur = self.__head
        # count記錄數量
        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
            # 當循環退出后,pre指向pos-1位置
            node = Node(item)
            node.next = pre.next
            pre.next = node

    def remove(self, item):
        """刪除節點"""
        cur = self.__head
        pre = None
        while cur != None:
            if cur.elem == item:
                # 先判斷此結點是否是頭節點
                # 頭節點
                if cur == self.__head:
                    self.__head = cur.next
                else:
                    pre.next = cur.next
                break
            else:
                pre = cur
                cur = cur.next

    def search(self, item):
        """查找節點是否存在"""
        cur = self.__head
        while cur != None:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        return False

鏈表與列表的差異

Python 中的 list(列表)并不是傳統意義上的列表,傳統的意義上的列表就是鏈表,不同地方在于鏈表在數據存儲方面更加的自由,其帶有指示下一個結點未知的指向,可以隨意的存儲數據。而列表則只能分配在一段連續的存儲空間里,且是作為一個整體,這就大大限制了數據的變更操作,但其在進行一些基礎簡單的操作時,時間復雜度極低。

list(列表):動態的順序表
鏈表:存儲地址分散的,需要“指針”指向的線性表

鏈表插入刪除效率極高,達到O(1)。對于不需要搜索但變動頻繁且無法預知數量上限的數據,比如內存池、操作系統的進程管理、網絡通信協議棧的 trunk 管理等。甚至就連很多腳本語言都有內置的鏈表、字典等基礎數據結構支持。

列表是一個線性的集合,它允許用戶在任何位置插入、刪除、訪問和替換元素。
列表實現是基于數組或基于鏈表結構的。當使用列表迭代器的時候,雙鏈表結構比單鏈表結構更快。
有序的列表是元素總是按照升序或者降序排列的元素。

實現細節
python中的列表的英文名是list,因此很容易和其它語言(C++, Java等)標準庫中常見的鏈表混淆。事實上CPython的列表根本不是列表(可能換成英文理解起來容易些:python中的list不是list)。在CPython中,列表被實現為長度可變的數組。

可參考《Python高級編程(第2版)》

從細節上看,Python中的列表是由對其它對象的引用組成的連續數組。指向這個數組的指針及其長度被保存在一個列表頭結構中。這意味著,每次添加或刪除一個元素時,由引用組成的數組需要該標大小(重新分配)。幸運的是,Python在創建這些數組時采用了指數分配,所以并不是每次操作都需要改變數組的大小。但是,也因為這個原因添加或取出元素的平攤復雜度較低。

不幸的是,在普通鏈表上“代價很小”的其它一些操作在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 列表與鏈表的區別詳解的文章就介紹到這了,更多相關Python 列表與鏈表區別內容請搜索腳本之家以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持腳本之家!

相關文章

  • Python中字符串的格式化方法小結

    Python中字符串的格式化方法小結

    這篇文章主要介紹了Python中字符串的格式化方法小結,提到了針對Python2.x與3.x版本相異情況下的不同技巧,需要的朋友可以參考下
    2016-05-05
  • python中報錯

    python中報錯"json.decoder.JSONDecodeError: Expecting value:"

    這篇文章主要介紹了python中報錯"json.decoder.JSONDecodeError: Expecting value:"的解決方法 ,需要的朋友可以參考下
    2019-04-04
  • python的移位操作實現詳解

    python的移位操作實現詳解

    這篇文章主要介紹了ppython的移位操作實現詳解,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
    2019-08-08
  • Django集成CAS單點登錄的方法示例

    Django集成CAS單點登錄的方法示例

    這篇文章主要介紹了Django集成CAS單點登錄的方法示例,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2019-06-06
  • python numpy元素的區間查找方法

    python numpy元素的區間查找方法

    今天小編就為大家分享一篇python numpy元素的區間查找方法,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2018-11-11
  • python list 查詢是否存在并且并返回下標的操作

    python list 查詢是否存在并且并返回下標的操作

    這篇文章主要介紹了python list 查詢是否存在并且并返回下標的操作,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2021-05-05
  • Python3 修改默認環境的方法

    Python3 修改默認環境的方法

    今天小編就為大家分享一篇Python3 修改默認環境的方法,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2019-02-02
  • python動態網頁批量爬取

    python動態網頁批量爬取

    這篇文章主要介紹了python動態網頁批量爬取的方法,主要針對四六級成績批量爬取,感興趣的小伙伴們可以參考一下
    2016-02-02
  • selenium3+python3環境搭建教程圖解

    selenium3+python3環境搭建教程圖解

    這篇文章主要介紹了selenium3+python3環境搭建教程圖解,需要的朋友可以參考下
    2018-12-12
  • Python使用LDAP做用戶認證的方法

    Python使用LDAP做用戶認證的方法

    這篇文章主要介紹了Python使用LDAP做用戶認證的方法,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2019-06-06

最新評論

精品国内自产拍在线观看