在雙向鏈表中，插入操作會影響多少個指針？

Question

昨天我接受了採訪。當它啓動時，第一件事情就是面試官問的是

「在一個雙向鏈表，有多少指針將在插入操作的影響？」

---

因爲，他沒有具體要求在哪裏插入我回答說，這取決於DLL中有多少個節點。

由於將受到影響的總指針將取決於列表是否爲空以及插入發生的位置。

但是，他沒有說我是否說服了他。

我是對的還是我錯過了什麼？

Answer 1

我認爲答案取決於我們是將新節點插入列表中間（由兩個節點包圍）還是列表的頭部或尾部。

對於列表中的中間插入，在一個新的節點以拼接如下：

A --- B 
    ^^ splice M in here 

A.next = M 
M.prev = A 
B.prev = M 
M.next = B 

因此4指針分配發生。但是，如果插入位於頭部或尾部，則只需要兩個指針分配：

TAIL (insert M afterward) 

TAIL.next = M 
M.prev = TAIL