阅读:0       作者:严长生

链表的插入和删除操作详解(C语言实现+详解注释)

链表的基本操作中,链表结点的插入和删除相对比较复杂,需根据结点插入位置的不同,使用合理的方法在不破坏原链表结构的前提下将其插入到链表中。

本节将详解介绍这两种操作的具体实现方法,读者只需牢记实现步骤,即可轻松解决这两大难点。

链表中插入结点

链表中插入结点,根据插入位置的不同,可分为以下 3 种情况:
  1. 插入到链表的首部,也就是头结点和首元结点中间;
  2. 插入到链表中间的某个位置;
  3. 插入到链表最末端;

图 1 链表中插入结点5

虽然插入位置有区别,都使用相同的插入手法。分为 2 步,如图 1 所示:
  • 将新结点的 next 指针指向插入位置后的结点;
  • 将插入位置前的结点的 next 指针指向插入结点;

提示:在做插入操作时,首先要找到插入位置的上一个结点,拿图 1 来说,也就是找到结点 1,相应的结点 2 可通过结点 1 的 next 指针表示。这样,先进行步骤 1,后进行步骤 2,实现过程中不需要添加其他辅助指针。

实现代码:
link * insertElem(link * p,int elem,int add){
    link * temp=p;//创建临时结点temp
    //首先找到要插入位置的上一个结点
    for (int i=1; i<add; i++) {
        if (temp==NULL) {
            printf("插入位置无效\n");
            return p;
        }
        temp=temp->next;
    }    
    //创建插入结点c
    link * c=(link*)malloc(sizeof(link));
    c->elem=elem;
    //向链表中插入结点
    c->next=temp->next;
    temp->next=c;
    return  p;
}
注意,首先要保证插入位置的可行性,例如图 1 中,原本只有 5 个结点,因此插入位置可选择的范围为:1-6,如果超过 6,由于操作本身无意义,程序会提示插入位置无效。

链表中删除节点

当需要从链表中删除某个结点时,需要进行 2 步操作:
  • 将结点从链表中摘下来;
  • 手动释放掉结点,回收被结点占用的内存空间;

 

使用 malloc 函数申请的空间,一定要注意手动 free 掉。否则在程序运行的整个过程中,申请的内存空间不会自己释放(只有当整个程序运行完了以后,这块内存才会被回收),造成内存泄漏,别把它当成是小问题。

实现代码:
link * delElem(link * p,int add){
    link * temp=p;
    //temp指向被删除结点的上一个结点
    for (int i=1; i<add; i++) {
        temp=temp->next;
    }
    link * del=temp->next;//单独设置一个指针指向被删除结点,以防丢失
    temp->next=temp->next->next;//删除某个结点的方法就是更改前一个结点的指针域
    free(del);//手动释放该结点,防止内存泄漏
    return p;
}

完整代码

#include <stdio.h>
#include <stdlib.h>

typedef struct Link{
    int  elem;
    struct Link *next;
}link;
link * initLink();
//链表插入的函数,p是链表,elem是插入的结点的数据域,add是插入的位置
link * insertElem(link * p,int elem,int add);
//删除结点的函数,p代表操作链表,add代表删除节点的位置
link * delElem(link * p,int add);
void display(link *p);

int main() {
    //初始化链表(1,2,3,4)
    printf("初始化链表为:\n");
    link *p=initLink();
    display(p);
   
    printf("在第4的位置插入元素5:\n");
    p=insertElem(p, 5, 4);
    display(p);
   
    printf("删除元素3:\n");
    p=delElem(p, 3);
    display(p);
    return 0;
}

link * initLink(){
    link * p=(link*)malloc(sizeof(link));//创建一个头结点
    link * temp=p;//声明一个指针指向头结点,用于遍历链表
    //生成链表
    for (int i=1; i<5; i++) {
        link *a=(link*)malloc(sizeof(link));
        a->elem=i;
        a->next=NULL;
        temp->next=a;
        temp=temp->next;
    }
    return p;
}
link * insertElem(link * p,int elem,int add){
    link * temp=p;//创建临时结点temp
    //首先找到要插入位置的上一个结点
    for (int i=1; i<add; i++) {
        if (temp==NULL) {
            printf("插入位置无效\n");
            return p;
        }
        temp=temp->next;
    }
    //创建插入结点c
    link * c=(link*)malloc(sizeof(link));
    c->elem=elem;
    //向链表中插入结点
    c->next=temp->next;
    temp->next=c;
    return  p;
}

link * delElem(link * p,int add){
    link * temp=p;
    //遍历到被删除结点的上一个结点
    for (int i=1; i<add; i++) {
        temp=temp->next;
    }
    link * del=temp->next;//单独设置一个指针指向被删除结点,以防丢失
    temp->next=temp->next->next;//删除某个结点的方法就是更改前一个结点的指针域
    free(del);//手动释放该结点,防止内存泄漏
    return p;
}
void display(link *p){
    link* temp=p;//将temp指针重新指向头结点
    //只要temp指针指向的结点的next不是Null,就执行输出语句。
    while (temp->next) {
        temp=temp->next;
        printf("%d",temp->elem);
    }
    printf("\n");
}
运行结果:
初始化链表为:
1234
在第4的位置插入元素5:
12354
删除元素3:
1254