練習 14：雙鏈表 · 笨辦法學 Python · 續中文版

# 練習 14：雙鏈表 > 原文：[Exercise 14: Double Linked Lists](https://learncodethehardway.org/more-python-book/ex14.html) > 譯者：[飛龍](https://github.com/wizardforcel) > 協議：[CC BY-NC-SA 4.0](http://creativecommons.org/licenses/by-nc-sa/4.0/) > 自豪地采用[谷歌翻譯](https://translate.google.cn/) 以前的練習可能需要花一段時間才能完成，因為你必須弄清楚如何使單個鏈表工作。希望視頻為你提供完成練習的足夠信息，并向你展示如何審計代碼。在本練習中，你將實現更好的鏈表`DoubleLinkedList`。在`SingleLinkedList`中，你應該已經意識到，涉及列表末尾的任何操作，都必須遍歷每個節點，直到到達末尾。`SingleLinkedList`僅僅對于列表前面是高效的，那里你可以輕松地更改`next`指針。`shift`和`unshift`操作非常快，但`pop`和`push`的開銷隨鏈表增大而增大。你可以通過保留下一個元素到最后一個元素的引用來加速，但是如果要替換該元素，該怎么辦？同樣，你必須遍歷所有的元素來找到這個元素。你可以通過細微變化來獲得一些速度改進，但更好的解決方案是，修改結構，使其可以從任何位置工作。 `DoubleLinkedList`與`SingleLinkedList`幾乎一樣，但它還有`prev`（上一個）鏈接，指向它前面的`DoubleLinkedListNode`。每個節點有一個額外的指針，使許多操作突然變得容易得多。你還可以在`DoubleLinkedList`中，輕易添加一個指向`end`的指針，所以你可以直接訪問頭部和尾部。這使得`push`和`pop`效率更加高效，因為你可以直接訪問尾部，并使用`node.prev`指針獲取上一個節點。考慮到這些變化，我們的節點類看起來像這樣： ```py class DoubleLinkedListNode(object): def __init__(self, value, nxt, prev): self.value = value self.next = nxt self.prev = prev def __repr__(self): nval = self.next and self.next.value or None pval = self.prev and self.prev.value or None return f"[{self.value}, {repr(nval)}, {repr(pval)}]" ``` 所有添加的東西就是`self.prev = prev`，以及在`__repr__`中處理它。`DoubleLinkedList `類的實現使用`SingleLinkedList`的相同方式，除了你需要為鏈表末尾添加一個額外的變量。 ```py class DoubleLinkedList(object): def __init__(self): self.begin = None self.end = None ``` ## 引入不變條件所有要實現的操作都一樣，但是我們有一些額外的事情需要考慮： ```py def push(self, obj): """將新的值附加到鏈表尾部。""" def pop(self): """移除最后一個元素并返回它。""" def shift(self, obj): """將新的值附加到鏈表頭部。""" def unshift(self): """移除第一個元素并返回它。""" def detach_node(self, node): """你有時需要這個操作，但是多數都在 remove() 里面。它應該接受一個節點，將其從鏈表分離，無論節點是否在頭部、尾部還是在中間。""" def remove(self, obj): """尋找匹配的元素并從中移除。""" def first(self): """返回第一個元素的*引用*，不要移除。""" def last(self): """返回最后一個元素的*引用*，不要移除。""" def count(self): """計算鏈表中的元素數量。""" def get(self, index): """獲取下標處的值。""" def dump(self, mark): """轉儲鏈表內容的調試函數。""" ``` 使用`self.end`指針，你現在必須在每個操作中處理更多的條件： + 是否有零個元素？那么`self.begin`和`self.end`都需要是`None`。 + 如果有一個元素，那么`self.begin`和`self.end`必須相等（指向同一個節點）。 + 第一個節點的`prev`必須始終為`None`。 + 最后一個節點的`next`必須始終為`None`。這些事實必須在`DoubleLinkedList`的生命周期中維持，這使得它們成為“不變條件”或者只是“不變量”。不變量的想法是，無論如何，這些基礎檢查顯示了結構正常工作。查看不變量的一種方法是，任何重復調用的測試或者`assert`調用可以移動進一個函數，叫做`_invariant`，它執行這些檢查。然后，你可以在測試中或每個函數的開始和結束處調用此函數。這樣做會減少你的缺陷率，因為你假設“不管我做什么，這些都是真的”。不變量檢查的唯一問題是它們的運行花費時間。如果每個函數調用也調用另一個函數兩次，那么你就為每個函數增加了潛在的重要負擔。如果你的`_invariant`函數也會導致成本增加，就變得更糟。想象一下，如果你添加了不變量：“所有節點都有一個`next`和`prev`，除了第一個和最后一個。這意味著每個函數調用都遍歷列表兩次。當你必須確保類一直有效時，這是值得的。如果不是，那就是一個問題。在這本書中，你可以使用`_invariant`函數，但請記住，你不需要始終使用它們。尋找方法，只在測試套件或調試中激活它們，或者在初始開發過程中使用它們，這是有效使用它們的關鍵。我建議你只在函數頂部調用`_invariant`，或者只在測試套件中調用它們。這是一個很好的權衡。 ## 挑戰練習在本練習中，你將實現`DoubleLinkedList`的操作，但此時你還將使用`_invariant`函數來檢查每個操作之前和之后是否正常。最好的方法是,在每個函數的頂部調用`_invariant`，然后在測試套件中的關鍵點調用它。`DoubleLinkedList`的測試套件幾乎是`SingleLinkedList`測試的復制粘貼副本，除了在關鍵點添加`_invariant`調用。與`SingleLinkedList`一樣，你需要自己手動研究此數據結構。你應該在紙張上繪制節點結構，并手動執行某些操作。接下來，在`dllist.py`文件中手動實現`DoubleLinkedListNode`。之后，花費一兩個 45 分鐘的時間，來嘗試黑掉一些操作來弄清楚。我推薦`push`和`pop`。之后，你可以觀看視頻以查看我的工作，以及如何組合使用我的代碼的審計和`_invariant`函數，來檢查我在做什么。 ## 深入學習與以前的練習一樣，你要按照記憶再次實現此數據結構。把你所知道的東西放在一個房間里，你的筆記本電腦在另一個房間。你將要執行此操作，直到你可以按照記憶實現`DoubleLinkedList`，而無需任何參考。