單鏈表刪除

Question

我在做單鏈表實現，我記得Linus Torvalds在談論它here。

在單向鏈表中，爲了移除節點，我們應該訪問前一個節點，然後更改它當前指向的節點。

像這樣

等任何一種方式，我們應該有機會獲得一個節點。

但Linus Torvalds通過使用C中的地址的想法刪除了特殊情況。因此，頭部還具有'先前的事物'，它是指向頭部的頭部的地址。所以他使用了C的指針和地址特徵去除特例。

特殊情況下的正常碼

的特殊情況下的代碼變得正常情況下

我覺得這種特殊的情況下去除單向鏈表不能在Python來完成，因爲我們沒有指針的概念（因此我不能在頭部前走一步）？我對嗎 ？

Answer 1

當然你可以在Python中做到這一點。他說的是，你有一些代表列表本身並指向列表頭部的數據結構，並且當你處理第一個列表項目時，就像操作列表項目中的指針一樣。

現在Python不是C，所以實現會有所不同，但這個原則適用。列表本身與第一個項目不是同一個對象，並且列表項目不應該與整個列表具有相同的方法，因此爲它們使用不同類型的對象是有意義的。

但是，它們都可以使用同名的屬性（例如next）指向下一個項目。因此，當您遍歷列表並且您位於第一個項目時，「上一個」項目就是列表本身，並且如果您需要刪除第一個項目，則您正在操作其next屬性。

在現實世界中，當然，除非作爲練習，否則絕不會編寫自己的Python鏈接列表類。內置list更高效。

Answer 2

你不能在Python中使用Linus的特定技巧，因爲正如你所知，Python沒有指針（就像這樣）或者是一個操作符地址。但是，您仍然可以通過爲列表添加一個虛擬頭節點來消除列表頭的特殊情況。您可以將其作爲列表設計的固有部分，或者您可以通過創建額外節點並將其引用到第一個數據承載節點作爲其下一個節點來實現。無論哪種方式，您可能要刪除的所有節點都是內部節點，而不是特殊情況。

Answer 3

我在閱讀你的問題時首先想到的是：你爲什麼要在python中建立一個單獨的鏈表？ Python提供了豐富的集合類型，您可以使用它們而不必擔心它們是以單鏈表，雙鏈表還是以非遞歸數據結構（通常更容易處理）實現。

但你的問題的答案是：Python當然可以建立一個單獨的鏈表。例如，下面的代碼就是這樣做的：

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

    def __str__(self): 
     return "<{}, {!s}>".format(self.x, self.next) 

n = Node(1, None) 
n = Node(2, n) 
n = Node(3, n) 
print(n) # output: <3, <2, <1, None>>> 

n.next.next = n.next.next.next 
print(n) # output: <3, <2, None>> 

到C的區別是：我們沒得malloc()或因爲Python爲我們處理內存與指針的工作。 Python具有引用而不是指針，它們是相似的，但更安全和更易於使用。

然而，實現鏈表之前，你應該考慮你的要求是關於你的收藏，也許你可以選擇從內置插件或集合模塊並不是一個好一個。

Answer 4

你需要兩個層次的間接做萊納斯暗示的方式，但你有可能做到這一點在Python也許有一個對象的引用存儲到這種物體或東西（指數爲參考索引？）。也就是說，我認爲它不會如此優雅或高效地映射到Python，並且使用對象來表示鏈接結構中的單個鏈接可能會非常浪費。

在Python的情況下，我只希望做更多的分支，以檢查你從頭部取出其中，除非有一些訣竅，我失蹤案件。

至於自己實現鏈表，其實我覺得很多使用情況下，標準庫是不夠的。這裏有一個例子：

...是格柵可能有10,000個細胞。由標準庫提供的大多數鏈接列表沒有經過優化，以每個列表32位索引的大小存儲10,000個鏈接列表，因爲它們試圖提供允許單獨使用鏈接列表的接口（不使用單獨的備份數據結構以便像數組一樣存儲）。通常，鏈接列表的最有效使用是不擁有內存或管理任何資源的。它只是以一種輔助方式鏈接數據，這些數據已經在另一個數據結構中分配和管理，就像這樣一個n元樹中的128位（16字節）樹節點，元素可以存儲在層次結構的任何級別：

struct TreeNode 
{ 
    int32 parent;  // parent index or -1 for no parent 
    int32 first_child; // first child of this node or -1 
    int32 next_sibling; // next child for the parent node or -1 
    int32 element;  // element data stored in this node or -1 
         // if no data is associated 
}; 

所以有很多的用例實現自己的鏈表和其他鏈接的結構，該結構顯著更有效的更窄，適用的用例（網格數據結構，八叉樹，四樹，圖等），但是我不認爲你可以在不容易讓你使用兩個或多個指針間接級別的語言中使用這個技巧。 Python固有地只有一個用於對象 - 與Java和C＃相同。您需要類似「對對象」或「的引用的索引，該索引指向對象」或「的索引，該索引指向對象」「的對象引用的索引。

另外，鏈接列表通常在語言中不那麼有用，因爲您不能管理所有內容都存儲在內存中的語言，因爲您最終可能會得到緩存未命中，從而導致迭代通過鏈接列表，否則如果每個列表節點在記憶在GC循環之後經常會發生，例如對於鏈接列表來說，要真正高效，就像Linux內核的情況一樣，要求你能夠很好地控制每個節點駐留在內存中的位置，以便列表遍歷實際上大部分（如果不是完全的話）只是通過連續的記憶。否則，即使這意味着線性時間刪除和中間插入，使用小型數組通常會更好。