链表节点的插入和删除

插入结点

数组在内存中是顺序存储的，要在数组中插入一个数据就变得颇为麻烦。这就像是在一排麻将中插入一个牌，必须把后面的牌全部依次顺移。然而，链表中各结点的关系是由指针决定的，所以在链表中插入结点要显得方便一些。这就像是把一条链子先一分为二，然后用一个环节再把它们连接起来。如下图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是查找关键字符
{
   node *newnode=new node;//新建结点
   newnode->data=newdata;//newdata是新结点的数据
   node *pGuard=search(head,keyWord);//pGuard是插入位置前的结点指针
   if (head==NULL || pGuard==NULL)//如果链表没有结点或找不到关键字结点
   {//则插入表头位置
      newnode->next=head;//先连
     head=newnode;//后断
   }
   else//否则
   {//插入在pGuard之后
      newnode->next=pGuard->next;//先连
      pGuard->next=newnode;//后断
   }
}

删除结点

与插入数据类似，数组为了保持其顺序存储的特性，在删除某个数据时，其后的数据都要依次前移。而链表中结点的删除仍然只要对结点周围小范围的操作就可以了，不必去修改其他的结点。

仍然我们先要来具体分析删除结点这个功能：

1. 我们必须知道对哪个链表进行操作，所以表头指针head是必须知道的。
2. 一般来说，待删除的结点是由结点的数据确定的。然而我们还要操作待删除结点之前的结点（或指针），以连接前后两段链表。之前所写的search函数只能找到待删除的结点，却无法找到这个结点的前趋结点。所以，我们只好放弃search函数，另起炉灶。
3. 令pGuard指针为待删除结点的前趋结点指针。
4. 由于要对待删除结点作内存释放，需要有一个指针p指向待删除结点。
5. 如果待删除结点为头结点，则我们要操作表头head，作为特殊情况处理。
6. 在删除结点的过程中，仍然要始终保持所有的结点都在我们的控制范围内，保证链表的完整性。为了达到这一点，我们还是采用先连后断的方式：先把待删除结点的前趋结点和它的后继结点连接，再把待删除结点与它的后继结点断开，并释放其空间。如下图9.6.4所示。
7. 如果链表没有结点或找不到待删除结点，则给出提示信息。

由于delete是C++中的保留字，我们无法用它作为函数名，所以只好用Delete代替（C++是大小写敏感的，Delete和delete是不同的）。都准备好了，我们就可以开始写函数了：（程序9.6.4）

void Delete(node * &head,char keyWord)//可能要操作表头指针，所以head是引用
{
   if (head!=NULL)//如果链表没有结点，就直接输出提示
   {
      node *p;
      node *pGuard=head;//初始化pGuard指针
      if (head->data==keyWord)//如果头结点数据符合关键字
      {
         p=head;//头结点是待删除结点
        head=head->next;//先连
         delete p;//后断
         cout <<"The deleted node is " <<keyWord <<endl;
         return;//结束函数运行
      }
      else//否则
      {
         while (pGuard->next!=NULL)//当pGuard没有达到表尾
         {
            if (pGuard->next->data==keyWord)//如果pGuard后继结点数据符合关键字
            {
               p=pGuard->next;//pGuard后继结点是待删除结点 
               pGuard->next=p->next;//先连
               delete p;//后断
               cout <<"The deleted node is " <<keyWord <<endl;
               return;//结束函数运行
            }
            pGuard=pGuard->next;//pGuard指针向后移动
          }
      }
   }
   cout <<"The keyword node is not found or the link list is empty!" <<endl;//输出提示信息
}