C++语言程序设计

链表能够方便地实现结点的插入和删除操作，这也是链表结构具有动态分配存储空间的体现，也是它优于数组的地方之一。还是举小朋友排队的例子来说明链表的插入和删除是怎样实现的。在这个比喻里面，每一个小朋友相当于一个结点，一个小朋友的手拉着另一个小朋友的手，相当于一个结点的指针域指向下一个结点。假设现有一对按大小个排好队的小朋友，又来一个小朋友需要加入该队列。这时候，就需要从原来队列里面的第一个小朋友开始，按照他们的身高找到新来小朋友应该站的位置（前一个小朋友的身高比他矮，后一个小朋友的身高比他高）。然后，把这两个小朋友的手分开，让前一个小朋友的手该拉着新来小朋友的一只手，新来小朋友的另一只手拉着后一个小朋友的一只手。这样，新来的小朋友就被插入到这个队伍里面了，并且这个队伍的小朋友还是按照身高顺序排列的。特别地，如果新来小朋友最矮，他只需要站在队伍的开头，并且让他的一只手拉着原来站在对头的小朋友的手就行了。
实际链表的插入操作也就可以类似地实现了，具体程序如下：

| 例8-15

void Insert(node* &head，node* position)
{
node * before, *current; //定义两个结点型指针before,current
before = current = head; //为这两个指针赋值为链表头指针

//搜索链表，确定指针before和current
while (current!=NULL)//如果没有到链表尾
{
if(current->data >= position ->data) break;
//因为链表数据从小到大排序，所以如果当前结点的数据
// 大于待插结点数据，就认为以找到插入位置，跳出循环
else{//否则，继续查找
before = current;//before指向current所指结点
current = current->next;
//current指向current所指结点的下一个结点
}
}
//插入结点position
if(current == head){ //插在链表头
position ->next = head;//待插结点指针指向原来的表头
head = position;//新的表头指针指向待插结点
}
else{ //插在链表中间
before ->next = position; //前一结点指向待插结点
position ->next = current; //待插结点指向当前结点
}
}

类似地，我们也可以对链表结点进行删除操作，方法就是：首先遍历链表，找到被删结点。如果该结点位于表头，则将表头指针指向该结点的下一个结点；如果该结点位于其它位置，则将该结点的前一结点直接指向该结点的下一结点。另外，需要注意的就是：如果该结点被删除，则要用delete操作释放该结点所占用的内存空间，否则会造成内存泄漏。

| 例8-16

void Delete(node* &head，int data)
//删除表头指针为head的链表中数据为data的结点
{
node * before, *current;
before = current = head;
//搜索链表，确定指针before和current
while (current!=NULL)
if(current->data == data) break;//找到被删结点，跳出循环
else{//继续查找
before = current;
current = current->next;
}
//删除数据域为data的结点
if(current!=0){
if(current == head){ //删除链表头结点
head = current ->next; //表头指针指向头结点的下一个结点
delete current; //释放被删结点
}
else{ //删除链表中间结点
before ->next = current ->next;
//被删结点的前一结点直接指向被删结点的下一结点
delete current;//释放被删结点
}
}
}