C++教程:链表节点的插入和删除

插入结点

数组在内存中是顺序存储的，要在数组中插入一个数据就变得颇为麻烦。这就像是在一排麻将中插入一个牌，必须把后面的牌全部依次顺移。然而，链表中各结点的关系是由指针决定的，所以在链表中插入结点要显得方便一些。这就像是把一条链子先一分为二，然后用一个环节再把它们连接起来。如下图9.6.2所示。 下面我们先对插入结点这个功能具体分析一下：

1. 我们必须知道对哪个链表进行操作，所以表头指针head是必须知道的。
2. 为了确定插入位置，插入位置前的结点指针pGuard是必须是知道的。
3. 用一个newnode指针来接受新建的结点。
4. 如果要插入的位置是表头，由于操作的是表头指针而不是一个结点，所以要特殊处理。
5. 在插入结点的过程中，始终要保持所有的结点都在我们的控制范围内，保证链表的完整性。为了达到这一点，我们采用先连后断的方式：先把新结点和它的后继结点连接，再把插入位置之前的结点与后继结点断开，并与新结点连接。如下图9.6.3所示。

做完了分析，我们可以开始编写插入函数了。为了简单起见，我们规定新结点插入位置为数据是关键字的结点之后，这样就可以使用刚才编写好的search函数了。如果该结点不存在，则插入在表头。则插入函数如下：（程序9.6.3）
void insert(node * &head,char keyWord,char newdata)//keyWord是查找关键字符
{