5.5.5　链表的插入和删除

    与数组相比，链表可以很方便地进行数据元素的插入和删除，在一个链表中插入一个节点或删除一个节点，只需要知道待插入或删除节点的位置及指向前一个节点的指针。图5.3是链表节点插入删除操作的形象示意图。

    5.5.5 链表的插入和删除 - 图1

    图　5.3　链表节点的插入删除示意图

    从图5.3可以看出，向一个链表中插入一个节点，只需要以下两步操作。

    ❑将插入位置前一节点（B）的指针域赋值给待插入节点（E）的指针域，使其指向插入位置后一节点（C）。

    ❑将待插入节点（E）的地址赋值给前一节点（B）的指针域。

    从一个链表中删除一个节点，只需将待删除节点（C）的指针域赋值给删除位置前一节点（B）的指针域即可。

    注意

    将节点插入在链表头或删除首节点时，要对head指针重新赋值。

    举例来说，有一个存储学生信息的链表，是按照年龄大小也就是节点的成员变量age的大小升序排列的，现在要插入一个新节点或删除一个旧节点，但要保持链表的排序关系，代码5.10和代码5.11分别演示了链表节点的插入和删除操作。

    代码5.10　链表节点的插入InsertANode

    ＜———————————-文件名：example510.cpp———————————————-＞ 01　#include＜iostream＞ 02　struct student 03　{ 04　char name[20]； 05　int age； 06　student*next； 07　}； 08　int main（） 09　{ 10　using namespace std； 11　student c={"Terry"，30，NULL}； 12　student b={"Deco"，27，＆c}； 13　student a={"Kaka"，23，＆b}； 14　int age； 15　cout＜＜"请输入likuan的年龄，你输入的数值将决定该节点插入链表的位置："＜＜endl； 16　cin＞＞age； 17　student insertD={"likuan"，age,NULL}； 18　student*head=＆a； 19　student*pointer=head； 20　student*before=NULL； 21　while（pointer） 22　{ 23　if（insertD. age＜=（*pointer）.age）//寻找插入位置 24　break； 25　before=pointer；//记录插入位置前一节点的地址 26　pointer=（*pointer）. next； 27　} 28　if（before==NULL） 29　{ 30　insertD. next=head；//在链表头部插入 31　head=＆insertD； 32　} 33　else 34　{ 35　insertD. next=（*before）.next；//在链表中间或末尾插入 36　（*before）. next=＆insertD； 37　} 38　student*coutPointer=head；//输出链表数据 39　cout＜＜"Head-＞"； 40　while（coutPointer）//while（coutPointer！=NULL） 41　{ 42　cout＜＜（coutPointer）. name＜＜"-＞"＜＜（coutPointer）.age＜＜"-＞"； 43　coutPointer=（*coutPointer）. next； 44　} 45　cout＜＜"End"＜＜endl； 46　return 0； 47　}

    输出结果如下所示。

    请输入likuan的年龄，你输入的数值将决定该节点插入链表的位置： 21　（注：键盘输入） Head-＞likuan-＞21-＞Kaka-＞23-＞Deco-＞27-＞Terry-＞30-＞End或 请输入likuan的年龄，你输入的数值将决定该节点插入链表的位置： 24　（注：键盘输入） Head-＞Kaka-＞23-＞likuan-＞24-＞Deco-＞27-＞Terry-＞30-＞End

    【代码解析】代码中声明了一个struct型指针pointer用于链表的遍历，声明了struct型指针before用以记录要插入位置前一个节点的地址，并对before初始化为NULL，执行完毕第一个while结构后，如果before仍为NULL，说明insertD.age小于首节点的age变量，应当将insertD插入在链表的头部，将head指针赋值给insertD的指针域，并将insertD的指针赋值给head指针，否则，应将insertD插入到before所指的节点后，将before所指节点的指针域赋值给insertD的指针域，并将insertD的地址赋值给before所指节点的指针域，后一个while结构用于输出链表数据，说明节点插入正确。

    代码5.11　链表节点的删除RemoveANode

    ＜———————————-文件名：example511.cpp———————————————-＞ 01　#include＜iostream＞ 02　#include＜string＞ 03　struct student 04　{ 05　char name[20]； 06　int age； 07　student*next； 08　}； 09　int main（） 10　{ 11　using namespace std； 12　char deleteName[20]； 13　cout＜＜"请输入要删除的节点姓名（Kaka,Deco或Terry）："＜＜endl； 14　cin＞＞deleteName； 15　student c={"Terry"，30，NULL}； 16　student b={"Deco"，27，＆c}； 17　student a={"Kaka"，23，＆b}； 18　student*head=＆a； 19　student*pointer=head； 20　student*before=NULL； 21　bool isFind=false； 22　while（pointer） 23　{ 24　if（strcmp（deleteName，（*pointer）. name）==0）//寻找删除位置 25　{ 26　isFind=true；//已经找到 27　break； 28　} 29　before=pointer；//记录删除位置前一节点地址 30　pointer=（*pointer）. next； 31　} 32　if（isFind） 33　{ 34　if（before==NULL） 35　head=（*head）. next//删除链表首记录 36　else 37　{ 38　（before）. next=（pointer）.next；//在链表中间或末尾删除 39　} 40　} 41　else 42　cout＜＜"未找到你输入的项"＜＜endl；//未找到输入数据 43　student*coutPointer=head；//输出链表数据 44　cout＜＜"Head-＞"； 45　while（coutPointer）//while（coutPointer！=NULL） 46　{ 47　cout＜＜（coutPointer）. name＜＜"-＞"＜＜（coutPointer）.age＜＜"-＞"； 48　coutPointer=（*coutPointer）. next； 49　} 50　cout＜＜"End"＜＜endl； 51　return 0； 52　}

    输出结果如下所示。

    请输入要删除的节点姓名（Kaka,Deco或Terry）： Kaka（注：键盘输入） Head-＞Deco-＞27-＞Terry-＞30-＞End或 请输入要删除的节点姓名（Kaka,Deco或Terry）： Terry（注：键盘输入） Head-＞Kaka-＞23-＞Deco-＞27-＞End

    【代码解析】代码5.11声明了一个struct型指针pointer用于链表的遍历，查找成员变量name与用户输入的字符串相同的节点，声明了struct型指针before用以记录待删除前一个节点的地址，并对before初始化为NULL,bool型变量isFind用来判断在链表中是否存在包含用户输入字符串的节点，如果“strcmp（deleteName，（*pointer）.name）==0”，isFind为true，证明找到了成员变量name与用户输入的字符串相同的节点。

    执行完毕第一个while结构后，如果before仍为NULL，说明用户要删除的是链表的首节点，将首节点的指针域赋值给head指针，否则，说明要删除的是中间节点或最终节点，执行“（before）.next=（pointer）.next；”即可，输出结果证明程序进行的删除操作是正确的。