轉發鏈接列表的問題

我已經成功實現了一個向後鏈表，但我試圖找出如何實現一個轉發鏈表，我似乎無法弄清楚如何去做。問題出在我的insert方法中。我試圖跟蹤前一個節點，並將其指向新創建的節點，但我錯過了一些東西。轉發鏈接列表的問題

class Node(object): 
    def __init__(self, data=None, next_node=None): 
     self.data = data 
     self.next_node = next_node 

    def set_next(self, new_next): 
     self.next_node = new_next 

    def get_data(self): 
     return self.data 

    def get_next(self): 
     return self.next_node 

class LinkedList(object): 
    def __init__(self, head=None): 
     self.head = head 

    def insert(self, data): 
     previous_node = self.head 
     current_node = self.head 
     new_node = Node(data) 
     if previous_node is not None: 
      previous_node.set_next(new_node) 
      previous_node = self.head

來源

2016-02-17 123

爲什麼'previous_node = self.head'？每個節點插入後頭？ – Arman

這裏有一個錯字'new_node = Node（data）'應該是'new node = Node2（data）'，有可能'Node'正在調用你的向後鏈表並導致混淆？ – steven

Kurt在他的回答中說，你需要一個'while'的條件，然後在期望的'previous_node'後加上'new_node'，Kurt的回答是完全正確的 – Arman

試試這個。

如果列表爲空，請設置標題並返回。否則，循環「轉發」所有元素，直到您點擊一個None節點。一旦完成，請設置適當的next_node值。

class LinkedList(object): 
    def __init__(self, head=None): 
     self.head = head 

    def empty(self): 
     return self.head is None 

    def insert(self, data): 
     new_node = Node(data) # Want to insert this 
     if self.empty():   # Is this list empty? 
      self.head = new_node # Yes? Then add the head 
     else:     # No? There are elements in the list 
      current_node = self.head     # Save a moving reference 
      while not current_node.get_next() is None: # While there are forward nodes 
       current_node = current_node.get_next() # Move the reference forward 
      current_node.set_next(new_node)    # Set the last node, thus inserting at the "end"

來源

2016-02-17 22:18:14

目前尚不清楚你的insert方法應該做什麼。如果要在列表的開頭（頭部之前）插入，則應該設置new_node.set_next(previous_node)和self.head = new_node。如果您打算追加到列表的末尾，那麼您需要掃描列表，直到找到包含current_node.get_next() == None的節點，並執行current_node.set_next(new_node)。

由於這看起來像功課，我不想直接給你答案。我會提供一些僞代碼來幫助你入門，儘管

def insert(value): 
    let current = head 
    until current.next_node == None: 
     let current = current.next_node 

    let current.next_node = Node2(value)

來源

2016-02-17 22:01:23

我無法弄清楚我的生活如何實現這個。你願意爲你的答案添加正確的'insert'方法嗎？ – 123

我添加了一些僞代碼來幫助您開始。 –

如何檢查'None'類型的'get_next（）'？ – 123

讓我們寫出來，究竟這樣做：

def insert(self, data): 
    previous_node = self.head # set to head of list 
    current_node = self.head  # not used elsewhere 
    new_node = Node(data)  # make a new node with the given data. 
    if previous_node is not None:  # if the list isn't empty 
     previous_node.set_next(new_node) # point the list head to the new node 
     previous_node = self.head  # does nothing; this was already the list head

底線：這將創建一個新的節點，並使其在表頭的「下一個」節點。這就是這一切;你的列表永遠不會超過2個節點。事實上，你的列表永遠不會得到第一個節點，因爲你沒有代碼插入到一個空列表中。

要解決這個問題，你需要一個明確的，適應性強的算法，如：

Create a new node. 
Link the existing list behind the new node: 
    Set new.next to the current head node. 
    Point the list head to the new node.

注意這甚至一個空列表。

如果您想要一個添加到結尾的列表，那麼還要維護一個指向列表中最後一個節點的self.tail屬性。然後你的插入（append）如下所示：

Create a new node. 
Link the new node to the existing tail: 
    if tail exists: 
     Set tail.next to the new node. 
    else: 
     Set head to the new node 
    Set tail to the new node.

這是否足夠清楚地實現？

來源

2016-02-17 22:20:12 Prune

轉發鏈接列表的問題

回答

相關問題