深入理解链表：从头插法到删除操作，408考研必备！

系列文章目录

• 深入浅出，408数据结构之顺序表操作详解
• C语言算法必刷经典题：输出绝对素数
• 考研408必刷经典真题 2019年41题
• “���入理解链表操作：LeetCode题解与实战 - 删除指定数值节点“

  ---

  文章目录

  • 系列文章目录
  • 前言
  • 一、链表的结构是什么？
  • 二、链表的头插法和尾插法(创建链表)
  • • 头插法：
    • 尾插法：
    • 三、链表的按位查找
    • 四、链表的按值查找
    • 五、往第i个位置插入元素
    • 六、链表的删除操作
    • 总结

      ---

      前言

      在学习链表这一数据结构时，我深刻体会到了其在算法与数据结构领域的重要性。从链表的头插法到按位查找、按值查找，再到插入元素和删除操作，每一个操作都展现了链表在实际应用中的灵活性和高效性。

      ---

      一、链表的结构是什么？

      ---

      ---

      二、链表的头插法和尾插法(创建链表)

      对于头插法和尾插法，我理解为在链表操作中的两种常见方式，分别适用于不同的场景。头插法可以快速插入元素并更新头指针，而尾插法则更适合在链表末尾添加元素。

      头插法：

      代码如下：

      #include #include typedef int Elemtype;typedef struct LNode { //因为有结构体指针，此处名称不能省略Elemtype data;struct LNode* next;//指向下一个结点}LNode,*LinkList;//LNode*是结构体指针，和LinkList完全等价的//L->next,意思是存储了下一个结点的地址，L的右边指针域有下一个结点的地址，第一个结点存了第二个结点的地址....void list_head_insert(LinkList& L) {//因为L是头结点，该函数接下来会对L进行malloc空间申请，会改变L，所以要&LinkList s;//用来指向申请的新结点Elemtype x;//存放第一个结点的数据scanf("%d", &x);L = (LinkList)malloc(sizeof(LNode));//申请头结点空间,链表的结构体类型是LNode,即sizeof(LNode)L->next = NULL;//因为插入数据一直在头结点的右边，导致第一个结点的指针域成为尾部，要设为NULLwhile (x != 9999) {s = (LinkList)malloc(sizeof(LNode));//申请一个新空间给s，强制类型转换s->data = x;//上面scanf读取到的值存放在新的s的data中//L是头结点//s是指向整个方块的指针,s->data是方块的左边数值,s->next是方块的右边指针域s->next = L->next;//因为L->next已经指向了前面的结点,即L->next=s'(s'是上一个结点),相当于s->next=s'，为步骤①L->next = s;//L的next存储新结点的地址scanf("%d", &x);//继续读取下一个结点的数值}}void print_list(LinkList L) {L = L->next;//因为L->next已经指向下个结点，此处表示头指针向第一个结点偏转while (L != NULL) {printf("%3d", L->data);L = L->next;//指针继续向下个结点偏转}printf("\n");}int main() {LinkList L;//定义链表头(里面没有数据)，是结构体指针类型list_head_insert(L);//输入数据可以为 3 4 5 6 7 9999,头插法新建链表print_list(L);//链表打印return 0;}

      图片如下：

      ---

      尾插法：

      代码如下：

      #include #include typedef int Elemtype;typedef struct LNode {Elemtype data;struct LNode* next;}LNode, * LinkList;void list_tail_insert(LinkList& L) {LinkList s;//定义申请的新结点Elemtype x;scanf("%d", &x);L = (LinkList)malloc(sizeof(LNode));//申请头结点空间，结点都是LNode*，sizeof为链表类型LNodeLinkList r = L;//r代表链表表尾结点，初始化指向链表头结点尾部,因为链表还没连上，只有一个L，所以r=Lwhile (x != 9999) {s = (LinkList)malloc(sizeof(LNode));s->data = x;r->next = s;//r是前一个结点，连接下一个结点操作r = s;//r继续向下一个结点偏转，本来是r=s->next，但s的指针域还没存结点的地址scanf("%d", &x);//继续读取下一个结点数值}r->next = NULL;//最后的尾部记得要赋上空}void print_list(LinkList L) {L = L->next;//因为L->next已经指向下个结点，此处表示头指针向第一个结点偏转while (L != NULL) {printf("%3d", L->data);L = L->next;//先打印再继续偏转}printf("\n");}int main() {LinkList L;//链表头，是结构体指针类型list_tail_insert(L);//尾插法输入数据可以为 3 4 5 6 7 9999print_list(L);//链表打印return 0;}

      图片如下：

      结果差异：

      ①头插法使数值反方法排列

      ②尾插法是相反的效果

      ---

      三、链表的按位查找

      需要如何通过遍历链表来找到目标节点

      代码如下：

      #include #include typedef int Elemtype;typedef struct LNode {Elemtype data;struct LNode* next;}LNode, * LinkList;void list_tail_insert(LinkList& L) {LinkList s;Elemtype x;scanf("%d", &x);L = (LinkList)malloc(sizeof(LNode));LinkList r = L;while (x != 9999) {s = (LinkList)malloc(sizeof(LNode));s->data = x;r->next = s;r = s;scanf("%d", &x);}r->next = NULL;}void print_list(LinkList L) {L = L->next;while (L != NULL) {printf("%3d", L->data);L = L->next;//先打印再继续偏转}printf("\n");}LinkList GetElem(LinkList L, int i) {int j = 1;//用来遍历链表,链表的第一个结点位置是1LinkList r = L->next;//r代表链表表尾结点，初始化指向链表头结点尾部,因为链表已经连上,所以r = L->nextif (i == 0) {return L;//如果要查找位置0的结点，就是头结点(位置为0)}if (i data);}return 0;}

      图片如下：

      ---

      四、链表的按值查找

      代码如下：

      #include #include typedef int Elemtype;typedef struct LNode {Elemtype data;struct LNode* next;}LNode, * LinkList;void list_tail_insert(LinkList& L) {LinkList s;Elemtype x;scanf("%d", &x);L = (LinkList)malloc(sizeof(LNode));LinkList r = L;while (x != 9999) {s = (LinkList)malloc(sizeof(LNode));s->data = x;r->next = s;r = s;scanf("%d", &x);}r->next = NULL;}void print_list(LinkList L) {L = L->next;while (L != NULL) {printf("%3d", L->data);L = L->next;}printf("\n");}LinkList LocateElem(LinkList L, Elemtype e) {LinkList r = L->next;//定义一个指针进行偏转while (r != NULL && r->data != e) {//指针不能为空，且还没找到er = r->next;}return r;}int main() {LinkList L;LinkList search;list_tail_insert(L);print_list(L);search = LocateElem(L, 6);//查找数值为6if (search != NULL) {printf("成功找到了数值为%d", search->data);}return 0;}

      图片如下：

      ---

      五、往第i个位置插入元素

      需要考虑边界情况和指针操作，以保证链表的正确性。

      代码如下：

      #include #include typedef int Elemtype;typedef struct LNode {Elemtype data;struct LNode* next;}LNode, * LinkList;void list_head_insert(LinkList& L) {LinkList s;Elemtype x;scanf("%d", &x);L = (LinkList)malloc(sizeof(LNode));L->next = NULL;while (x != 9999) {s = (LinkList)malloc(sizeof(LNode));s->data = x;s->next = L->next;L->next = s;scanf("%d", &x);}}void print_list(LNode* L) {L = L->next;while (L != NULL) {printf("%3d", L->data);L = L->next;}printf("\n");}LinkList GetElem(LinkList L, int i) {int j = 1;//用来遍历链表,链表的第一个结点位置是1LinkList r = L->next;//r代表链表表尾结点，初始化指向链表头结点尾部,因为链表已经连上,所以r = L->nextif (i == 0) {return L;//如果要查找位置0的结点，就是头结点(位置为0)}if (i data = e;//先为插入结点赋值s->next = p->next;//为图中①p->next = s;//为图中②//适用与表头、中间和表尾//如果是在表尾插结点，也行得通/*s->next = NULL;p->next = s;*/return true;//记得返回true}int main() {LinkList L;list_head_insert(L);//头插法创建链表print_list(L);bool ret;ret = ListFrontInsert(L, 2, 99);//链表L，插入的位置，插入的数值if (ret) {printf("插入成功");print_list(L);}return 0;}

      图片如下：

      ---

      六、链表的删除操作

      需要确保删除节点后正确地维护链表的连接关系，避免出现内存泄漏或指针错误。

      代码如下：

      #include #include typedef int Elemtype;typedef struct LNode {Elemtype data;struct LNode* next;}LNode, * LinkList;void list_tail_insert(LinkList& L) {LinkList s;Elemtype x;scanf("%d", &x);L = (LinkList)malloc(sizeof(LNode));LinkList r = L;while (x != 9999) {s = (LinkList)malloc(sizeof(LNode));s->data = x;r->next = s;r = s;scanf("%d", &x);}r->next = NULL;}void print_list(LinkList L) {L = L->next;while (L != NULL) {printf("%3d", L->data);L = L->next;}printf("\n");}LinkList GetElem(LinkList L, int i) {int j = 1;LinkList r = L->next;if (i == 0) {return L;}if (i next;j++;}return r;}bool ListDelete(LinkList L, int i) {//bool类型方便进行以下特殊情况判断LinkList p = GetElem(L, i - 1);//先找到删除结点的前一个结点if (p == NULL) {return false;//先判断}LinkList q = p->next;//储存要删除的结点,并赋上地址p->next = q->next;//进行断链free(q);return true;}int main() {LinkList L;list_tail_insert(L);print_list(L);bool ret;ret=ListDelete(L, 4);//删除第4个结点if (ret != NULL) {printf("删除成功\n");print_list(L);}return 0;}

      图片如下：

      ---

      总结

      通过这些学习，我更深入地理解了链表这一数据结构的设计原理和应用场景，也意识到在实际编程中灵活运用链表可以提高程序的效率和可维护性。

      如果在以上内容中存在错误或不足之处，还请各位读者批评指正，让我们共同进步！