【轉譯】每個Python開發者都應該掌握的8種資料結構

當解決實際編碼問題時，每個人都在追求執行時和資源消耗方面的高效率，

選擇當前方案中最適合的資料結構，會提升程式性能并且減少執行時間，因此很多大公司在面試的時候都非常注重求職者對資料結構的理解，

本文包含：

• 什么是資料結構
• 陣列/串列 Array/List
• 佇列 Queue
• 堆疊 Stack
• 鏈表 Linked list
• 回圈鏈表 Circular linked list
• 樹 Tree
• 圖 Graph
• 哈希表 Hashable Table

什么是資料結構？

資料結構是一種存盤和組織資料，使它更容易修改、瀏覽和訪問的代碼結構，資料結構決定了資料是如何聚集的、我們能使用的功能和資料之間的關系，

資料結構幾乎應用在所有的計算機科學和編程領域，從作業系統到 Web前后端開發再到機器學習，

資料結構可以幫助我們

• 管理和使用大的資料集
• 從資料庫中快速搜索指定資訊
• 在資料點之間建立清晰的層次或關系連接
• 簡化并加速資料處理

資料結構是高效解決實際問題的至關重要的一部分，是一種經過反復驗證和優化的工具，可以給你提供一種簡易的框架來組織你的程式，這樣你解決問題的時候，不需要每次重新造輪子，

每種資料結構都有一個與之最匹配的任務或使用情境，Python中有四種內置的資料結構，串列、字典、元組和集合，這些內置結構有一些默認方法，并做了些底層的優化，使他們更好用，

大多數 Python 中的資料結構都修正了這些內置結構的格式或使用它們作為它的基礎，

• 串列：類陣列結構，保存一個相同型別的可變物件的集合
• 元組：不可變串列，元素不能更改
• 集合：無序集合，元素內部未索引，且不可重復
• 字典：類似哈希表，key/value 鍵值對集合，鍵值唯一且為不可變物件

下面我們看看這些結構是如何創造一些高級資料結構的，

陣列/串列 Array/List

Python 中沒有內置的 array 型別，但可以使用 List 來實作，陣列是一些值的集合，這些值具有相同型別，并保存在同一名稱下，

串列中的每個值都叫一個元素，同時具有一個索引，代表它的位置，你可以通過使用串列名和索引值來訪問特定的元素，也可以通過 len() 方法獲取串列的長度，

不像 Java等靜態語言，Python中的串列會自動放大或縮小，當元素增加/減少的時候，

比如，我們可以通過 append() 方法在一個已存在的串列末尾增加一個額外的元素而不需要宣告一個新串列，

這使得Python串列更好使用，能動態適應，

cars = ["Toyota", "Tesla", "Hyundai"]
print(len(cars))
cars.append("Honda")
cars.pop(1)
for x in cars:
  print(x)

優點

• 創建和使用資料序列更簡單
• 自動縮放以滿足不斷變化的尺寸要求
• 可以用作創建更復雜的資料結構

缺點

• 沒有針對科學資料方面的優化（不像 NumPy中的串列）
• 只能控制串列的末尾

應用場景

• 分享相關聯值或物件的存盤
• 你將遍歷的資料集
• 資料結構的集合，比如一個元組的串列

佇列 Queue

佇列是一種線性結構，存盤資料時遵循”先進先出”(FIFO)的次序，不像串列，你不能通過索引值訪問元素，只能獲得最先進去的元素，這個非常適合于一些對次序敏感的任務，比如線上訂單處理、語言信箱存盤，

我們可以通過list的 append 和 pop 方法實作一個佇列，但這樣效率不高，因為list在頭部增加一個元素的時候需要移動所有的元素，

使用 collections 模塊的deque類是個更好的選擇，deque優化了append和pop的操作，很容易實作一個雙端佇列（double-ended queue），可以通過popleft和popright方法訪問佇列的頭尾兩端，

from collections import deque
# Initializing a queue
q = deque()
# Adding elements to a queue
q.append('a')
q.append('b')
q.append('c')
print("Initial queue")
print(q)
# Removing elements from a queue
print("\nElements dequeued from the queue")
print(q.popleft())
print(q.popleft())
print(q.popleft())
print("\nQueue after removing elements")
print(q)
# Uncommenting q.popleft()
# will raise an IndexError
# as queue is now empty

優點

• 自動按時間順序排列資料
• 自動縮放以滿足尺寸要求
• 使用deque類在時間上的高效

缺點

• 只能在頭尾訪問資料

應用場景

• 對共享資源（如列印機或CPU內核）的操作
• 作為批處理系統的臨時存盤
• 為同等重要的任務提供簡單的默認順序

堆疊 Stack

堆疊是一種“后進先出”（LIFO）的佇列，最后入堆疊的元素被認為是在堆疊頂，是唯一可以訪問的元素，想訪問中間的元素，必須首先洗掉足夠的元素，以確保指定的元素在堆疊頂，

許多開發者把堆疊想象成一堆碟子，你只能在碟子堆頂部添加或移除碟子，如果想把碟子放在底部則必須移除整個堆疊，

添加元素用 push，洗掉元素用 pop，可以使用Python內置的list來實作堆疊，實作時分別使用 append 和 pop 來實作 push和 pop操作，

stack = []
# append() function to push
# element in the stack
stack.append('a')
stack.append('b')
stack.append('c')
print('Initial stack')
print(stack)
# pop() function to pop
# element from stack in
# LIFO order
print('\nElements popped from stack:')
print(stack.pop())
print(stack.pop())
print(stack.pop())
print('\nStack after elements are popped:')
print(stack)
# uncommenting print(stack.pop())  
# will cause an IndexError
# as the stack is now empty

優點

• 提供了LIFO的資料管理
• 自動縮放和物件清理
• 簡單可靠的資料存盤系統

缺點

• 堆疊記憶體有限
• 堆疊中物件太多會導致堆疊溢位錯誤

應用場景

• 創建高反應性（highly reactive）系統
• 記憶體管理系統使用堆疊處理首先回應最近的請求
• 有助于括號匹配等問題

鏈表 Linked List

鏈表是一個連續的資料集合，它使用每個資料節點上的關系指標鏈接到串列中的下一個節點，

不同于陣列，鏈表中沒有物件所在的位置，而擁有關系位置，根據包圍他們的節點確定，

鏈表中的第一個節點被稱為頭結點，最后一個稱為尾結點，它有一個空指標，

根據節點是只有一個指向下一個節點的指標還是同時也擁有指向上一個節點的第二個指標，鏈表可分為單向鏈表和雙向鏈表，

可以把鏈表想象成一個鏈條?，單個連接都只與相鄰的節點相連，所有的連接一起形成一個更大的結構，
Python沒有一個內置的鏈表實作方式，因此需要你實作一個 Node類來存放節點值和一個或多個指標，

class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None
class SLinkedList:
    def __init__(self):
        self.headval = None
list1 = SLinkedList()
list1.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")
# Link first Node to second node
list1.headval.nextval = e2
# Link second Node to third node
e2.nextval = e3

鏈表主要用于創建高級資料結構，如圖形和樹，或者用于需要在結構中頻繁添加/洗掉元素的任務，

優點

• 高效地添加和洗掉新元素
• 比陣列更易于重組
• 可用作高級資料結構（如圖形或樹）的起點

缺點

• 資料節點存盤的指標增加了記憶體的開銷
• 必須始終從Head節點遍歷鏈表才能找到特定元素

應用場景

• 作為高級資料結構的組成部分
• 用于需要頻繁添加/洗掉元素的方案

回圈鏈表 Circular linked list

標準鏈表的主要缺點是你始終需要從頭節點開始，回圈鏈表通過將尾結點的空指標null替換成頭結點，從而解決了這個問題，鏈表遍歷的時候程式會一直跟蹤指標，直到它回到它開始的節點，

這樣設定的優勢是可以從任何節點開始遍歷整個鏈表，它還允許您通過設定結構中所需的回圈數，將鏈表用作可回圈結構，回圈串列非常適合用于需要長時間回圈的處理中，比如作業系統中的CPU分配，

優點

• 可以從任何節點遍歷鏈表
• 使鏈表更適合回圈結構

缺點

• 沒有null標記，找到頭尾節點更加困難

應用場景

• 定期回圈解決方案，如CPU調度

樹 Tree

樹是另一種基于關系的資料結構，專門用于表示層次關系，同鏈表一樣，樹也存在于包含節點值和一個或多個指標的節點物件中，

每個樹都包含一個根節點，其他所有節點都從中產生，根節點包含直接跟它相連的節點的指標，這些節點被稱為子節點，子節點也可以用于自己的子節點，二叉樹的子節點數量不得超過2個，

同一個等級的節點稱為同級節點，沒有子節點的節點稱為葉子節點，

二叉樹的最常見的應用是二叉搜索樹，二叉搜索樹長于搜索大的資料集，時間復雜度取決于樹的深度而非節點數量，

二叉搜索樹的四個規則

• 左子樹只包含元素小于根節點的節點
• 右子樹只包含元素大于根節點的節點
• 左右子樹必須也是二叉搜索樹
• 沒有重復的節點，也就是每個節點的值都不相同

class Node:
    def __init__(self, data):
        self.left = None
        self.right = None
        self.data = data
    def insert(self, data):
# Compare the new value with the parent node
        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data
# Print the tree
    def PrintTree(self):
        if self.left:
            self.left.PrintTree()
        print( self.data),
        if self.right:
            self.right.PrintTree()
# Use the insert method to add nodes
root = Node(12)
root.insert(6)
root.insert(14)
root.insert(3)
root.PrintTree()

優點

• 適合表示層級關系
• 動態大小
• 快速增加和洗掉
• 在二叉搜索樹中，插入的節點會立即排序
• 二叉搜索樹中搜索非常高效

缺點

• 時間消耗高，O(logn)，在修正或平衡樹，或者從指定位置獲取元素
• 子節點不包含它父節點的資訊，難于逆向遍歷
• 只適用于排好序的串列，未排序的資料會降低到線性搜索

應用場景

• 非常適合于存盤層級結構的資料，比如檔案路徑
• 用于實作頂級搜索和排序演算法，比如二叉搜索樹、二叉堆

Graph 圖

圖是一種資料結構，用于表示資料頂點（圖的節點 vertex）之間可見的關系，而把頂點連接在一起的叫邊(edge)，

邊定義了哪些頂點連接在一起但沒有在他們之間指定一個方向，每個頂點都有一些跟其他頂點的連接，這些資訊以逗號分隔的list 形式保存在頂點中，

有一些特殊的圖稱為有向圖，它定義了關系的方向，類似于鏈表，有向圖在建立單向關系模型或流程圖時非常有用，

它們主要用于用代碼形式來傳遞可視化的web結構網路，這些結構可以模擬不同型別的關系，比如層級結構、分支結構，或者只是一個簡單的無序的關系網，圖的多功能性和直觀性使其成為資料科學的最愛，

書寫時，圖有分別有一個頂點和邊的串列：

V = {a, b, c, d, e}
E = {ab, ac, bd, cd, de}

Python中，圖可以通過一個字典實作，每個頂點作為key，邊的串列作為 value，

# Create the dictionary with graph elements
graph = { "a" : ["b","c"],
                 "b" : ["a", "d"],
                 "c" : ["a", "d"],
                  "d" : ["e"],
                  "e" : ["d"]
         }
# Print the graph          
print(graph)

優點

• 快速通過代碼傳遞可視化的資訊
• 可用于建模廣泛的現實世界問題
• 語法簡單

缺點

• 大圖中，頂點的連接更難理解
• 從圖中決議資料的時間消耗高

應用場景

• 優于模擬網路或 web類似的結構
• 適合模擬社交網路

哈希表 Hash table

哈希表是一種復雜的資料結構，適合存盤大量資料，高效獲取指定元素，

這種結構使用 key/value 對，鍵是元素的名稱而值則是存盤在此名稱下的資料，

每個輸入鍵都經過一個散列函式，它將其從起始形式轉換為一個整數，稱為散列，散列函式必須同一輸入時總是生成相同的值，必須快速計算，并且長度相同，Python引入了一個內置的hash()函式，用于提升速度，

哈希表使用散列來查找所需值的一般位置，稱為存盤桶，程式查找值時只需要搜索這個子組，而不是整個資料池，

超出這個一般框架之外，哈希表還可以根據應用程式的不同而有很大的不同，一些可能允許鍵值是不同的資料型別，另一些可能有不同設定的桶或不同的散列函式，

import pprint
class Hashtable:
    def __init__(self, elements):
        self.bucket_size = len(elements)
        self.buckets = [[] for i in range(self.bucket_size)]
        self._assign_buckets(elements)
    def _assign_buckets(self, elements):
        for key, value in elements: #calculates the hash of each key
            hashed_value = https://www.cnblogs.com/jiaoran/archive/2021/03/05/hash(key)
            index = hashed_value % self.bucket_size # positions the element in the bucket using hash
            self.buckets[index].append((key, value)) #adds a tuple in the bucket
    def get_value(self, input_key):
        hashed_value = hash(input_key)
        index = hashed_value % self.bucket_size
        bucket = self.buckets[index]
        for key, value in bucket:
            if key == input_key:
                return(value)
        return None
    def __str__(self):
        return pprint.pformat(self.buckets) # pformat returns a printable representation of the object
if __name__ =="__main__":
     capitals = [
        ('France', 'Paris'),
        ('United States', 'Washington D.C.'),
        ('Italy', 'Rome'),
        ('Canada', 'Ottawa')
    ]
hashtable = Hashtable(capitals)
print(hashtable)
print(f"The capital of Italy is {hashtable.get_value('Italy')}")

優點

• 轉換任何格式的key到整型索引
• 對大的資料集非常高效
• 非常有效的搜索功能
• 每次搜索的步驟數保持不變，添加或洗掉元素的效率保持不變
• Python3做了些優化

缺點

• 散列值必須唯一，兩個不同鍵轉換成同一個值時會沖突
• 沖突錯誤需要徹底檢查哈希函式
• 對新手來說太難

應用場景

• 適用于大的、經常搜索的資料庫
• 使用輸入鍵的檢索系統

參考鏈接

• 8 Data Structures Every Python Programmer Should Know
  

標籤：其他

上一篇：Dubbo 是如何控制并發數和限流的？

下一篇：Python簡單通俗易懂的貪吃蛇小游戲，兒時童年的味道！