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

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

In a doubly linked list, How many pointers are affected on an insertion operation?