在 Python 中用鍊錶模仿字典列表

我將以我的思考過程和視覺化來開始這篇文章。一個實驗（你可以選擇這樣稱呼它）讓我大開眼界，更清楚地了解鍊錶是什麼。這讓我不再將其視為抽象的，而是以陳詞濫調的方式（數據和下一個）來解釋它。

思維過程和可視化

最近我開始從更物理的角度（通常稱為 OOP）來看待程式碼。然而，我的超越了類別和屬性；我開始在每次 while 和 for 迴圈之前寫下步驟和演算法。厭倦了僅僅為了目的而陷入抽象。這讓我嘗試了更多的事情，這進一步教會了我更多的事情，我將在本文中分享這些事情。

在我們深入研究之前三個關鍵問題和答案：

• 鍊錶由什麼組成？
• 節點是什麼樣的？
• 鍊錶一開始是什麼樣子的？

回答第一個；節點組成一個鍊錶。

對於第二個問題；將鍊錶中的節點想像成一輛汽車牽引另一輛汽車。在這種情況下，假設兩輛車都裝有貨物。第二輛車用鏈條固定在第一輛車的後方。節點透過保存資料（例如汽車中的貨物或乘客）在連結清單中執行此操作。這種資料類型可以很簡單，如整數或字串，也可以是更複雜的資料結構。同時，每輛車都有一個連接器（鏈條）將其與道路上的下一輛車連接起來。在鍊錶中，這是下一個屬性，它指向下一個節點或先前節點（在雙向鍊錶中）的記憶體位址。沒有 next 屬性的清單不是鍊錶。

每輛車只知道它前面或後面的汽車（取決於鍊錶的類型）。最後一輛車沒有鏈條，這意味著它指向任何東西。在連結列表中，這通常由 None 表示。

回答第三個問題；頭節點啟動一個鍊錶，就像第一輛車開始拖車一樣。

到目前為止，我們已經了解了鍊錶的基礎知識。現在我們將探討我寫這篇文章的主要原因。

介紹

Python 內建的資料結構（如列表和字典）提供了靈活的方式來儲存和管理資料。列表允許我們儲存有序序列，而字典讓我們將鍵與值配對以便於存取。

在本文中，我們將探討如何使用組合來建立類似字典的鍊錶。我們將看到類似字典的鍊錶和字典列表之間的記憶體使用差異。我們還將看到我們的節點如何從 dict 獲得繼承以使節點實例成為實際的字典。所有這些都是為了給我們理解鍊錶提供更多的視角。

建立我們的連結列表

如前所述，鍊錶由節點組成。這些節點每個都有一個資料段和一個下一個段。資料可以是簡單的（如字串或整數），也可以是複雜的。

簡單：

Node 類別（由 My_Int 表示）具有 data 和 next 作為屬性。

本文將處理一個複雜的案例：

複雜：

節點類別（由 My_Dict 表示）包含多個屬性：使用者名稱、膚色和下一個。 **kwargs 作為參數，允許方法接受任意數量的關鍵字參數，而無需明確定義每個參數。

每個節點不僅僅儲存單個數據，而是將多個數據（用戶名和膚色）組合成一個，使其比整數或字串等基本數據結構更複雜。

我們現在將建立一個 My_List 類，它將管理 My_Dict 實例的連結清單。它需要一個 head 屬性。這個頭通常是初始化鍊錶的第一個節點。

該類別還提供了一個插入方法，用於在末尾添加新的節點條目。
我們也在這裡創建了 My_Dict 的實例（它是一個節點）。 My_List 將充當鍊錶結構中 My_Dict 物件的容器。每個 My_Dict 實例都透過下一個引用連接，這使得 My_List 能夠動態管理 My_Dict 實例的遍歷和插入。這基本上體現了構圖。

建立 My_Dict 實例後，我們透過檢查頭部是否存在來確保清單不為空。如果頭不存在，則表示列表為空，因此我們將 self.head 初始化為新節點（即 my_dict）。然後 return 立即退出函數。無需進一步執行。

當清單中先前存在一個節點並且我們想要插入一個新節點時，return 之後的行將會運行。我們將該節點 last_dict 初始化為 head，這將用於查找最後一個節點（列表的末尾），以便可以將新節點附加到那裡。 while 迴圈迭代列表，直到到達最後一個節點。只要last_dict.next不等於None，就會透過設定last_dict = lastdict.next移到下一個節點。

最後last_dict.next = my_dict將my_dict追加到清單末端完成插入。一旦我們知道last_dict.next是None（即，我們位於最後一個節點），我們就將my_dict附加到那裡。

我們現在處理遍歷函數：

遍歷函數迭代鍊錶中的每個節點，並對每個節點從頭到尾執行一個操作（在本例中為列印）。此方法提供了清單中所有節點的順序視圖。

看下面的完整程式碼：

我們上面的實作可以被認為是類似字典的物件的自訂連結列表，但它的結構與標準 Python 典型字典列表不同。 以下是注意事項：

• My_Dict 類別：每個實例充當一個類似字典的對象，具有屬性（使用者名稱和膚色）和下一個指針，允許它連結到另一個 My_Dict 實例。
• My_List 類別：此類管理 My_Dict 實例的連結列表，維護頭部並提供插入方法以在末尾新增條目。每個節點透過next指標連接到下一個節點，模擬鍊錶結構。

演算法

編寫程式碼時擁有演算法總是好的。這稱為所採取的步驟。也許我應該在上面的程式碼之前編寫它們。但我只是想先展示日常陳腔濫調的鍊錶和更複雜的類型之間的差異。話不多說，以下是步驟。

1. 使用節點結構的屬性來建立一個類別。
2. 建立另一個類，將其命名為 LinkedList（或其他名稱）。添加頭部作為唯一屬性。做頭=無。
3. 建立並插入節點：
   • 建立 Node 的實例。
   • 如果清單為空，則讓節點實例為 head 的值。
   • 如果清單不為空，則將前一個節點的值為頭。
   • 條件檢查為；如果前一個節點的下一個屬性不是 None，則循環遍歷列表。
   • 最後設定前一個節點的下一個指向新節點。
4. 遍歷列表：
   • 建立一個臨時節點，並將 head 設定為其起始值。
   • 以臨時節點不為 None 為條件進行循環。
   • 列印臨時節點中的資料。
   • 將臨時節點移到下一個
   • 最後到了最後，接下來是 None，所以印 None。
5. 根據需要建立類別實例。

與字典列表的比較

我們現在將透過查看以下幾點來將上面的內容與 Python 字典列表進行比較：

• 結構與儲存：

字典列表：在Python中，字典列表將每個字典儲存為連續列表結構中的元素，使每個字典都可以透過索引存取。

字典鍊錶：我們的程式碼使用鍊錶結構，其中每個節點（類似字典的 My_Dict 實例）保存對下一個節點的引用，而不是使用連續的記憶體儲存。如果元素經常更改，這對於大型列表來說會更節省內存，但按位置訪問會更慢。

• 存取與插入： 字典列表：在標準 Python 列表中，透過索引存取元素的時間複雜度為 O(1)（常數時間），因為 Python 列表本質上是數組。在末尾添加新字典通常是 O(1)，但如果需要調整大小，則變為 O(n)。

字典鍊錶：在我們的鍊錶中，存取一個元素需要遍歷（O(n) 時間），因為我們必須逐個節點迭代。最後插入也是 O(n)，因為我們每次都要找到最後一個節點。然而，在開始處插入可以是 O(1)，因為我們可以將新節點設為頭。

• 記憶體使用情況：

字典清單：Python 清單使用更多內存在連續區塊中儲存字典，因為每個項目都是依序儲存的。記憶體是為 Python 列表動態分配的，有時會在列表增長時調整大小並複製列表。我們可以使用 sys 模組在程式碼中證明這一點：

字典鍊錶：鍊錶為每個節點有效地使用內存，因為它只根據需要分配內存。然而，它需要額外的空間來容納每個節點中的下一個引用。

從上面我們可以看出位元組的差異； 776和192。

技術上不是字典

在我們的程式碼中，My_Dict 實例是類似字典的對象，而不是真正的字典。

以下是一些原因：

• 下一個屬性將 My_Dict 實例連結在一起，使它們更像連結列表中的節點而不是獨立字典。下一個屬性不是我們在普通字典中找到的功能。

  • 方法與行為： 類似字典的物件（例如 My_Dict 實例）可以具有類似於字典的方法和行為，但從技術上講它們不是字典。它們缺少 .keys()、.values()、.items() 等方法以及哈希等特定於字典的操作。 如果我們希望 My_Dict 物件的行為更像字典，我們可以繼承 Python 的內建 dict 來實作賦予它們字典功能的方法。但就目前情況而言，這些物件類似於字典，因為它們以鍵值樣式儲存數據，但不繼承 Python 字典，也不完全相同。

以下是我們如何繼承 dict 類別：

第一行從Python的打字模組導入Dict。這顯示My_Dict是一個專門的字典。

My_Dict 類別繼承自 dict，這意味著它將具有字典的屬性，但可以自訂。

讓我們來看看建構子：

__init__ 使用使用者名稱和膚色屬性初始化 My_Dict 的實例。 super().__init_() 呼叫父 Dict 類別建構子。 self['username'] = 使用者名稱和 self['complexion'] = 膚色 將使用者名稱和膚色儲存為字典條目，允許像字典一樣存取 My_Dict 實例（例如，new_dict['username']）。還有一個
next 屬性初始化為 None，透過允許每個 My_Dict 實例連結到另一個實例來設定鍊錶結構。

上面的方法重寫了 dict 中的 keys 方法，允許它傳回 My_Dict 中的所有鍵。使用 super().keys() 呼叫父級
keys() 方法，確保標準的字典行為。

在 MyList 類別的 insert 方法中，我們可以看到如何讓已建立的字典實例表現出字典行為。我們將keys()方法連結到它，並且我們也用它來評估使用者名稱金鑰。我們在 if 和 else 區塊中執行此操作。在 if 區塊中，它會列印頭節點的鍵和使用者名稱。在 else 區塊中，它會列印其他節點的鍵和其他節點的使用者名稱。

上面字典理解中的遍歷方法：

我們使用 current_dict 中的每個鍵值對來建立一個字典。 current_dict = getattr(current_dict, 'next', None) 移動到下一個節點，繼續直到 current_dict 變成 None。

注意：當涉及記憶體使用時，讓我們的類別繼承自 dict 意味著更多的記憶體使用。與我們之前創建的類似字典的節點的鍊錶不同。

結論

本文的目的是提供更多關於鍊錶的觀點和見解，超出我通常所理解的範圍。我沒有創新。我只是在嘗試程式碼，試圖為那些可能認為程式碼過於抽象的人提供更多見解。不過我想從更資深的程式設計師那裡知道，如果使用或過去使用時可能會有什麼缺點。

以上是在 Python 中用鍊錶模仿字典列表的詳細內容。更多資訊請關注PHP中文網其他相關文章！