使用循環鏈接列表插入功能

Question

這是我的代碼，每次我調用插入函數時，我都會得到一個輸出：<__main__.CircularList object at 0x10597fd68>。 我想通過調用for循環來使用插入函數來實際創建循環鏈表。

class Link (object): 
    def __init__ (self, data, next = None): 
    self.data = data 
    self.next = next 

class CircularList(object): 
    def __init__(self): 
    self.first = None 

    # Insert an element in the list 
    def insert (self, item): 
    newLink = Link (item) 
    current = self.first 

    if (current == None): 
     self.first = newLink 
     return 

    while (current.next != None): 
     current = current.next 

    current.next = newLink 
    newLink.next = self.first  

Answer 1

您的實施首先是錯誤的。如果你把if循環，你應該設置明顯的.next值本身，否則就不會有一個圓圈：

if (current == None): 
    self.first = newLink 
    newLink.next = newLink 
    return 

但接下來還有一個重要的問題：通過迭代循環列表，你永遠不會結束迭代，因爲顯然你會在你回來的那一刻再做一次。

所以，你首先需要下定決心其中你想插入項目？作爲第一項？或者在迭代的情況下達到的最後一個項目？

如果你要選擇的最後一個，你首先必須在第一項存儲在內存中：

first = current 

（您也可以在使用過程self.first），但這可能會少一點高效）

接下來你迭代的項目列表中，並且每次檢查current的next是否是第一次。在這種情況下，我們遍歷整個圓，所以：

while (current.next != first): 
    current = current.next 

現在，如果current.next指向first，我們知道我們已經完成了一次巡視。現在，我們只需要執行一些指針簿記：

current.next = newLink 
newLine.next = first 

所以完整的代碼如下：

def insert (self, item): 
    newLink = Link (item) 
    current = self.first 

    if (current == None): 
     self.first = newLink 
     newLink.next = newLink 
     return 

    first = current 
    while (current.next != first): 
     current = current.next 

    current.next = newLink 
    newLink.next = first