3-3　新数据插入链表

在链表中，如果要在任意位置新增节点元素，只要将前一个节点指标指向此新节点，然后将新节点指标指向下一个节点就可以了。例如，想要在链表内的Mango节点和Apple节点间增加Orange，整个步骤如下：

　步骤1

将Mango节点的指标指向Orange节点。

　步骤2

将Orange节点的指标指向Apple节点。

由于上述只更改两个指针就完成了数据插入，不需要遍历n个节点，所以运行时间复杂度是O（1）。