Python與單尾鏈接列表

Question

我有一個鏈接列表，我想實現爲一個隊列。我已經發現它的工作原理，但是我對這個特定部分的工作原理有疑問。下面是代碼：

class LinkedQueue: 
    class _Node: 
     def __init__(self, element, next): 
      self._element = element 
      self._next = next 

    def __init__(self): 
     self._head = None 
     self._tail = None 
     self._size = 0 

    def enqueue(self, e): 
     newest = self._Node(e, None) 
     if self.is_empty(): 
      self._head = newest 
     else: 
      self._tail._next = newest 
     self._tail = newest 
     self._size += 1 

如果隊列是空的，我入隊，第一個條件在排隊的真實，被觸發，最新被分配到self._head。但是，當我添加另一個元素時，else塊被觸發，並且self._tail._next被分配最新。這顯然會改變_head的_next變量。但是，分配第三個元素時，_head的_next變量不會更改。這是爲什麼？另外，不應該_tail被最新改變，並且因此_next變量被新分配的None覆蓋。

該代碼完全工作，我理解鏈表的邏輯，但我不明白爲什麼這個特定的代碼工作。

Answer 1

你問：

self._tail._next分配newest。這顯然改變了_head的變量 _next。

是的，因爲當時_tail和_head是同一個對象的兩個名字。

所以當然分配給_tail._next具有完全按照分配給_head._next也有同樣的效果 - 這怎麼可能不是，因爲_tail和_head指的是相同的對象？

讓我們來看看它們是如何引用同一個對象的！當if分支執行時，您執行self._head = newest;然後無條件地if/else你做self._tail = newest。在Python中，賦值始終是引用 - 賦值（對於名稱[*]）本身從不隱式地創建副本。

（作業到一個列表中的一個片段是一個非常不同的操作，因此這個迂迴的括號 - 但現在讓我們忘記它，因爲你不處理片的任務:-)。

然而，分配的第三元件的情況下，對於_head 的_next變量不被改變。這是爲什麼？

因爲在那個時候它沒有任何更多的事實，_tail和_head是同一對象兩個名字：他們是那麼的不同對象的名稱。

那是因爲你周圍的第二次指派了不同的東西（newest）到self._tail - 但指派了什麼新的self._head，因此這仍然是指以前的對象......這_tail不涉及任何更長的時間。

此外，不應該由_tailnewest被改變，並且這樣的_next 變量由新分配的無覆蓋？

self._tail確實重新綁定（「改變」是一個非常模糊的術語 - ！）來指代相同的對象爲newest，所以如果你在當時印刷self._tail._next（在enqueue方法的盡頭）你確實將它看作None。但緊前分配self._tail._next影響當時什麼簡稱self._tail的_next屬性（前self._tail=newest！） - 與新分配到self._tail立即成爲倒數第一位在列表中的節點。

Answer 2

也許你可以檢查此參考... http://interactivepython.org/runestone/static/pythonds/BasicDS/ImplementingaQueueinPython.html

你可以使用隊列抽象數據類型.. http://interactivepython.org/runestone/static/pythonds/BasicDS/TheQueueAbstractDataType.html