在LinkedList中插入一个节点:语句的顺序重要吗?

Question

参考以下与LinkedList对应的PDF(第14页):

显然，新节点需要插入到"p"所指向的节点之后。

http://www.cs.utep.edu/vladik/cs2401.10a/Ch_16_Linked_Lists.pdf

我的问题:

如果我们向前移动到PDF的第16页，为什么它说插入节点的语句序列非常重要?我的意思是我可以这样写代码吗?

p.link = newNode; // writing this part of code first 
newNode.link = p.link; //writing this part of code after the above one.

请让我知道这两份报表按不同的顺序写有什么不同?

谢谢

Answer 1

确实有相当显著的差异。

p.link = newNode; 
newNode.link = p.link; //p.link = newNode, per above, so now newNode.link = newNode

先前在p.link的内容现在丢失了，不再连接。newNode只是链接到它自己，所以如果你遵循所有的链接，你最终会在newNode处无限循环。

你可能想要的是下面的选项:

newNode.link = p.link; 
p.link = newNode;  

本例中，newNode.link设置为原来的p.link, p.link设置为newNode。

Answer 2

PDF是正确的。

如果您按照上面列出的顺序执行步骤，newNode将指向自己，而链表的其余部分将"丢失"。

由于您将p.link设置为newNode，因此您不再拥有指向p.link之前指向的指针(下一个元素)。(您可以通过在将p.link赋值给newNode之前将其保存为临时变量来解决这个问题，但是这需要一个额外的变量，当它不是真正需要的时候。)

Answer 3

假设:

这是你的newNode:

+---+
| n |
+---+

这是你的p:

+---+
| p |
+---+

p。link = newNode;

+---+    +---+
| p | -> | n |
+---+    +---+

newNode。Link = p. Link

+---+    +---+            +---+    +---+
| p | -> | q |  same with | n | -> | q |
+---+    +---+            +---+    +---+

解释

1. p。link = newNode表示p的下一个是newNode
2. newNode。link = p.link表示p的下一个与newNode
的下一个相同