將中間節點插入雙向鏈表[如何]

我似乎在這個任務的圈子。即使畫出來似乎也沒有給我一個工作的解決方案。有人能幫我找到我的思維過程在哪裏崩潰嗎？將中間節點插入雙向鏈表[如何]

// method receives node ins to be inserted 
// and node prev in front of which ins should be inserted 
public void insertIntermediate(DLLNode ins, DLLNode prev) 
{ 
    ins.pred = prev ; // update node ins' predecessor information 
    ins.succ = prev.succ ; // update node ins' successor information 
    prev.succ = ins ; // update list's information 
    prev.succ.pred = ins ; // update list's information 
}

[EDIT2]（除去EDIT1以減少混亂）

@Andrew，確定我發現：什麼是錯誤的與上述是線的順序3 & 4：

第3行導致我無法訪問prev.succ.pred。

通過交換兩條線我解決了這個問題。感謝提示！

ADD-ON問題：

我碰到雖然另一個奇怪的問題，這就是爲什麼我失去了這麼多的時間來尋找解決方案：如果我再重新插入一個已經存在的元素，由於某種原因，整個事情進入無限循環，當我打印它 ...例如

myList.addBeforeFirst(B) ; 
myList.addBeforeFirst(B) ;

導致一個循環，而：

myList.addBeforeFirst(B) ; 
myList.addBeforeFirst(C) ;

工作正常

這裏的方法：

public void addBeforeFirst(DLLNode ins) 
{ 
    ins.succ = first ; 
    ins.succ.pred = ins ; 
    first = ins ; 
}

和節點：

DLLNode B = new DLLNode("Hi", null, null) ; 
DLLNode C = new DLLNode("Salut", null, null) ;

爲什麼會這樣呢？

來源

2011-03-21 raoulbia

這是一個加倍鏈接列表，是嗎？那是什麼意思？確保您正在更新全部的相關鏈接，並按正確順序排列。另外，確保所有相關的節點都存在。

編輯：

讓我們通過您的語句秩序。

開始之前，您有prev，其屬性succ指向後繼節點。（或者是否可以有例外情況？如果存在，您將如何處理這種例外情況？）應該與prev相同，前提條件是prev.succ指向後繼節點。

現在，您的前兩條語句設置爲ins.pred和ins.succ。這基本上是正確的想法，但看到我上面的問題。

現在，您將prev.succ設置爲ins。關注這個聲明。你有沒有現在丟失的信息？究竟做了以下說明嗎？這是你的意圖嗎？

我認爲這是我可以做的最好的事情，而不必完全放棄解決方案。

編輯的無限循環問題：

您遇到的問題是由價值和傳遞參數通過引用傳遞參數之間的區別。因爲你是通過引用傳遞的，所以你傳遞了兩次對同一個對象（B）的引用。這意味着你最終做了以下內容：

第一次調用：

B.succ = first; 
B.succ.pred = B; /* why not just first.pred = ins? */ 
first = B;

現在，首先是設置爲B.因此，第二個電話，使用B：

B.succ = B; 
B.succ.pred = B; /* so, now B is its own pred and succ */ 
first = B; /* no change here */

所以，現在，首先是B，first.succ是B，first.succ.succ是B等，因此是無限循環。

來源

2011-03-21 22:03:50 Andrew

對我來說，似乎我涵蓋了所有四個鏈接：2之間prev和插件（前進和後退）和2之間插件和prev.succ（前進和後退），所以不知道缺少什麼？ – raoulbia 2011-03-21 22:28:39

@Baba我會編輯我的答案，因爲這可能會有點冗長的評論。 – Andrew 2011-03-21 22:35:15

嗨安德魯，看我的編輯 – raoulbia 2011-03-21 23:05:20

將中間節點插入雙向鏈表[如何]

回答

相關問題