在双链接列表中，插入操作会影响多少指针？

Question

我昨天去面试了。开始的时候，面试官问的第一件事是

“在双链接列表中，插入操作将影响多少指针？”

因为，他没有专门问插入哪里，我回答说，这取决于DLL中有多少个节点。

由于将受影响的总指针将取决于列表是否为空以及插入的位置。

但是，不管我是否说服了他，他什么也没说。

我是对的还是遗漏了什么？

Answer 1

我认为答案取决于我们是将新节点插入到列表的中间(被两个节点包围)，还是插入列表的头还是尾。

对于列表中间的插入，按如下方式拼接到一个新节点中：

A --- B
   ^^ splice M in here

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

因此，进行了四个指针分配。但是，如果插入位于头或尾，则只需要两个指针赋值：

TAIL (insert M afterward)

TAIL.next = M
M.prev = TAIL