在雙向鏈表的尾部插入

我第一次使用鏈接列表，並且必須創建一個可以在雙鏈表的末尾插入節點的函數。到目前爲止，我有在雙向鏈表的尾部插入

void LinkedList::insertAtTail(const value_type& entry) { 
    Node *newNode = new Node(entry, NULL, tail); 
    tail->next = newNode; 
    tail = newNode; 
    ++node_count; 
}

節點類接受的值存儲，下一個指針的值指向，並在該順序在先指針的值。每當我嘗試在此處插入節點時，都會收到一條錯誤消息，說明存在未處理的異常，並且在寫入位置0x00000008時存在訪問衝突。

我不完全確定這裏出了什麼問題，但我認爲它與根據錯誤消息取消引用空指針有關。我真的很感謝解決這個問題的一些幫助。

編輯：

我應該及早澄清，尾巴是指向在列表中的最後一個節點的指針。尾 - >下一個訪問最後一個節點的下一個變量，它在函數運行之前指向NULL，但在執行之後應該指向創建的新節點。

來源

2012-10-09 Brandon Bosso

只是一個鏡頭顯示我們：'LinkedList'和'Node'類，沒有太多在你的第一篇文章的背景。 –

指向'newNode'的'tail'和'tail-> next'有什麼問題嗎？ *（看起來像一個循環引用，但我可能是錯的。）* –

你的'tail'最初是NULL嗎？您不能在'tail-> next'中取消引用它，直到它已經指向第一個元素 –

哪裏tail點開始？如果它是NULL，那麼在嘗試插入第一個元素時，您將取消引用空指針。

如果您在解除引用前測試tail，這會對您有所幫助嗎？

如果tail爲null，並且offsetof(Node, next)是8，將解釋訪問衝突，因爲tail->next將在0x00000000地址+ 8是0x00000008，所以分配給tail->next會嘗試在該地址寫入到內存，這正是你所看到的錯誤。

來源

2012-10-09 00:21:47

感謝大家的幫助！原來，尾巴指向NULL。當我意識到這是一個簡單的修復。再次感謝！ –

這很難說是什麼引起的錯誤，而不插入操作之前知道名單的狀態（這實際上是追加而非嵌入，順便說一句）。

您很可能沒有處理追加到空列表的初始情況。基本算法（空列表由空頭指針指示的，其他一切都是不確定的）：

def append (entry): # Common stuff no matter the current list state. node = new Node() node->payload = entry node->next = NULL # Make first entry in empty list. if head = NULL: node->prev = NULL head = node tail = node return # Otherwise, we are appending to existing list. next->prev = tail tail->next = node tail = node

來源

2012-10-09 00:20:07 paxdiablo

假設你的LinkedList的同時有頭部和尾部，也許嘗試：

void LinkedList::insertAtTail(const value_type& entry) 
{ 
    Node *newNode = new Node(entry, NULL, tail); 
    if (tail) 
     tail->next = newNode; 
    tail = newNode; 
    if (!head) 
     head = newNode; 
    ++node_count; 
}

在黑暗

來源

2012-10-09 00:25:20 WhozCraig

在雙向鏈表的尾部插入

回答

相關問題