在双向链表中，插入操作会影响多少个指针？
昨天我接受了采访。当它启动时，第一件事情就是面试官问的是在双向链表中，插入操作会影响多少个指针？
“在一个双向链表，有多少指针将在插入操作的影响？”
因为，他没有具体要求在哪里插入我回答说，这取决于DLL中有多少个节点。
由于将受到影响的总指针将取决于列表是否为空以及插入发生的位置。
但是，他没有说我是否说服了他。
我是对的还是我错过了什么？
我认为答案取决于我们是将新节点插入列表中间（由两个节点包围）还是列表的头部或尾部。
对于列表中的中间插入，在一个新的节点以拼接如下：
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
所以，毕竟它并不取决于节点的总数，对吧？ – Barry
你所做的指针数学的数量并不取决于节点的数量。但是，这并不是说插入链表的运行时间不取决于列表的大小。相反，对于排序列表，它仍然需要'O（N * lgN）'时间才能找到插入点_before_，我们甚至开始了实际的插入操作。 –
为什么O（N * log N）？对于一个有排序的*数组*，它可以通过二进制搜索在O（logN）中完成，对于排序的*列表*，它不应该超过O（N）（最糟糕的情况是，您需要查看所有元素）。我不清楚为什么在最糟糕的情况下你需要考虑更多的因素。 –
您的问题尚不清楚。什么*精确*“受影响”是什么意思？读？书面？提领？而“插入”的意思是什么？它是否包含搜索要插入的位置，还是仅引用* actual *插入操作？ –
@JörgWMittag我猜这里的“影响”意味着，当我插入时，我必须改变指针next和prev到新节点。 – Barry