如何解決鏈接列表中損壞的指針？

Question

如果我發現鏈表中的指針（鏈接）字段已損壞，我該如何解決此問題？

我在面試中被問到這個問題。我說不，它不可能解決它。採訪者告訴它可能。有什麼方法嗎？

Answer 1

也許你應該擺脫它？ 真的，在一般情況下，我們不能只是插入其他人的任何列表元素。

Answer 2

好吧，假設這是一個雙向鏈表：

如果它是被損壞了的「下一個」指針，可以在尾部開始，並使用「上一個」指針，遍歷朝向頭部而名單保持對所遍歷的最後一個元素的引用。當你發現有壞指針的元素時，你只需要讓該元素的「下一個」指針指向最後一個被遍歷的元素。

如果一個「上一個」鏈接在雙向鏈表中被破壞，這個過程可以顛倒 - 從頭開始​​，遍歷直到發現錯誤的「前一個」指針，並使用對最後一個元素的引用被遍歷。

Answer 3

在開發我的嵌入式作業時，我使用了很多前向鏈接隊列。我保持一個數字以及頭指針。隊列有一個check（）方法，它運行[count]鏈接，並在結果指針與頭部不相同的情況下調用關鍵錯誤處理程序。這不是萬無一失的，但它足以很好地捕捉到雙重推送和其他常見的隊列錯誤。

注意：在多線程應用程序中，必須鎖定隊列以安全檢查隊列。

Answer 4

在一個雙向鏈表中，如果指針（前一個或下一個指針）中的任何一個被損壞，我們就可以解決被破壞的指針。

如果下一個指針不正確，我們可以反向遍歷列表，然後我們可以糾正它，否則，如果先前的指針不正確，我們可以向前遍歷列表來糾正它。

現在我們必須考慮如何識別列表中損壞的鏈接（指針）。我們使用分別爲每個節點分配動態內存（malloc或calloc）。如果我們經常撥打malloc或calloc來小的小內存可能會影響系統的性能。與此不同，我們可以在初始階段分配一大堆堆內存，然後我們可以爲每個節點創建實現自己的內存分配功能。還可以使用它僅用於列表節點創建，以識別列表的損壞鏈接。

這增加了系統的性能，並且通過檢查分配給列表的初始內存的限制，它將有助於識別節點的鏈接是否已損壞。

一旦我們得到一個指向節點的指針，我們必須在訪問該節點中的數據之前先進行下面的檢查。

check_limit(node); 
check_limit(node->next); 
check_limit(node->previous); 

而且我們可以檢查node->previous是否等於current_node。

之後也有可能是node->next可能指向錯誤的地址，但在初始內存限制內。在這種情況下，我們可以讀取node->next->previous（這不會導致崩潰，即使next指向錯誤的地址但在初始內存限制內），並檢查它是否等於node。

而且未使用的初始內存空間應始終設置爲NULL（使用memset）。

通過這些方法，我們可以找出列表中損壞的指針的99％。