《计算思维与算法入门》 —2.4.3 在单向链表中添加新节点

2.4.3  在单向链表中添加新节点

在单向链表中添加新节点如同在一列火车中加入新的车厢，有三种情况：加到第一个节点之前、加到最后一个节点之后以及加到此链表中间任一位置。接下来我们使用图解方式来说明。

1．将新节点加到第一个节点之前，即成为此链表的首节点

只需把新节点的指针指向链表原来的第一个节点，再把链表头指针指向新节点即可，如图2-29所示。

图2-29  将新节点加到第一个节点之前

2．将新节点加到最后一个节点之后

只需把链表的最后一个节点的指针指向新节点，新节点的指针再指向NULL即可，如图2-30所示。

图2-30  将新节点加到最后一个节点之后

3．将新节点加到链表中间的位置

例如要插入的节点在X与Y之间，只要将X节点的指针指向新节点，新节点的指针指向Y节点即可，如图2-31和图2-32所示。

图2-31  新节点的指针指向Y节点

图2-32  X节点的指针指向新节点