一、链表的数据结构链表是一种线性数据结构其元素在逻辑上是线性排列的但在物理存储上不要求连续。每个元素节点包含数据域 指针域通过指针将节点链接起来数据域是存储的数据信息指针域是指向下一个节点的指针。typedefstructListNode{intdata;structListNode*next;}ListNode;ListNode*a;data存储的数据nextnext 是一个 指向 struct ListNode类型的指针最后一个节点next NULLa 是一个指向 ListNode结构体的指针二、链表的类型头指针是指向链表第一个节点的指针用来表示链表的起始位置。如果链表没有头结点那么头指针直接指向第一个数据节点如果链表有头结点那么头指针指向头结点。头指针用于访问整个链表因此头指针是链表结构所必需的。1.有头结点的链表和无头结点的链表头结点是人为在链表最前端增加的一个辅助节点通常不保存实际数据。头结点的 next 指针指向链表中的第一个数据节点。对于头结点来说其数据域可以为空也可以存储一些附加信息例如链表长度等。头结点的主要作用是作为链表操作的统一入口因此头结点不是链表结构所必需的但在实现中经常被引入以简化操作。1.1创建一个有头结点的空链表#includestdio.h#includestdlib.h//定义结点typedefstructListNode{intdata;structListNode*next;}ListNode;//创建结点ListNode*list_create_node(intdata){ListNode*node(ListNode*)malloc(sizeof(ListNode));if(nodeNULL)returnNULL;node-datadata;node-nextNULL;returnnode;}//创建一个带头结点的空链表ListNode*list_create(){ListNode*head(ListNode*)malloc(sizeof(ListNode));if(headNULL)returnNULL;head-nextNULL;returnhead;}1.2创建无头结点的空链表#includestdio.h#includestdlib.htypedefstructListNode{intdata;structListNode*next;}ListNode;ListNode*list_create(){ListNode*headNULL;// 空链表returnhead;}【注意】无论链表是否设置头结点头指针始终指向链表的第一个节点。当存在头结点时第一个节点就是头结点当没有头结点时第一个节点就是第一个数据节点。那么为何要引入头结点呢如果链表没有头结点头指针直接指向第一个数据节点。当需要在第一个节点之前插入新的节点时需要修改头指针的指向例如1.在第一个节点前插入新节点需要让头指针指向新节点2.删除第一个节点时也需要更新头指针也就是说在这种情况下头指针需要频繁改变指向并且对第一个节点的操作需要进行特殊处理。2.单向列表和双向链表2.1单向链表每个节点只包含一个 next 指针指向链表中的下一个节点。链表从头节点开始依次连接到尾节点尾节点的 next 为 NULL空指针。单向链表的特点是结构简单占用内存少但只能从前往后遍历无法直接访问前驱节点。2.1.1单向列表的插入//添加结点(头插法)boollist_insert_head(ListNode*head,intdata){if(headNULL)returnfalse;ListNode*nodelist_create_node(data);if(nodeNULL)returnfalse;node-nexthead-next;head-nextnode;returntrue;}//尾插法boollist_insert_tail(ListNode*head,intdata){if(headNULL)returnfalse;ListNode*currhead;while(curr-next)currcurr-next;ListNode*nodelist_create_node(data);if(nodeNULL)returnfalse;curr-nextnode;returntrue;}//指定位置插入(第n个结点之后插入)除头结点之外boollist_insert_after(ListNode*head,intpos,intdata){if(headNULL)returnfalse;ListNode*currhead;for(inti0;ipos;i){if(curr-nextNULL)returnfalse;currcurr-next;}ListNode*nodelist_create_node(data);if(nodeNULL)returnfalse;node-nextcurr-next;curr-nextnode;returntrue;}2.1.2单向链表的删除//删除头结点之后的第一个结点boollist_delete_first(ListNode*head){if(headNULL||head-nextNULL)returnfalse;ListNode*tmphead-next;head-nexttmp-next;free(tmp);returntrue;}//删除第n个结点(计数)boollist_delete_n(ListNode*head,intn){if(headNULL)returnfalse;ListNode*currhead;for(inti0;in;i){if(curr-nextNULL)returnfalse;currcurr-next;}ListNode*targetcurr-next;if(targetNULL)returnfalse;curr-nexttarget-next;free(target);returntrue;}2.1.3单向链表的反转voidlist_reverse(ListNode*head){if(headNULL||head-nextNULL)return;ListNode*prevNULL;ListNode*currhead-next;ListNode*nextNULL;while(curr){nextcurr-next;curr-nextprev;prevcurr;currnext;}head-nextprev;}2.2双向链表每个节点包含两个指针next 指向后继节点prev 指向前驱节点。双向链表允许从前向后和从后向前遍历插入和删除节点时可以直接访问前驱节点操作更灵活。但每个节点需要额外的存储空间用于 prev 指针结构比单向链表复杂。2.2.1创建双向链表//结构体typedefstructDListNode{intdata;structDListNode*next;structDListNode*prev;}DListNode;//利用数组创建双向链表DListNode*dlist_create_from_array(intdata[],intn){DListNode*headmalloc(sizeof(DListNode));if(headNULL)returnNULL;head-nextNULL;head-prevNULL;DListNode*phead;for(inti0;in;i){DListNode*tmpmalloc(sizeof(DListNode));if(tmpNULL)returnNULL;tmp-datadata[i];tmp-nextNULL;tmp-prevp;p-nexttmp;ptmp;}returnhead;}2.2.2双向列表的插入头插法booldlist_insert_head(DListNode*head,intdata){if(headNULL)returnfalse;DListNode*nodemalloc(sizeof(DListNode));if(nodeNULL)returnfalse;node-datadata;DListNode*firsthead-next;node-nextfirst;node-prevhead;head-nextnode;if(first)first-prevnode;returntrue;}尾插法booldlist_insert_tail(DListNode*head,intdata){if(headNULL)returnfalse;DListNode*currhead;while(curr-next)currcurr-next;DListNode*nodemalloc(sizeof(DListNode));if(nodeNULL)returnfalse;node-datadata;node-nextNULL;node-prevcurr;curr-nextnode;returntrue;}指定位置插入voiddlist_insert_after(DListNode*head,intn,intdata){DListNode*currhead;for(inti0;in;i){if(curr-nextNULL)return;currcurr-next;}DListNode*new_nodemalloc(sizeof(DListNode));if(new_nodeNULL)return;new_node-datadata;DListNode*next_nodecurr-next;curr-nextnew_node;new_node-prevcurr;new_node-nextnext_node;if(next_node)next_node-prevnew_node;}2.2.3双向链表的删除voiddelete_point(DListNode*head,intn){for(inti0;in;i){if(headNULL)return;headhead-next;}if(headNULL)return;DListNode*currhead;DListNode*prevhead-prev;DListNode*nexthead-next;if(prev!NULL)prev-nextnext;if(next!NULL)next-prevprev;free(curr);}2.2.4双向链表的反转//双向链表的反转voidchange(DListNode*list){DListNode*currlist-next;DListNode*nextNULL;DListNode*prevNULL;while(curr){nextcurr-next;curr-nextprev;curr-prevnext;prevcurr;currnext;}list-nextprev;prev-prevlist;}3.循环链表循环链表是一种特殊的链表结构其最后一个节点的指针指向链表的头节点从而形成一个首尾相连的循环。它可以是单向或双向链表特点是可以从任意节点开始遍历而不必考虑末尾空指针常用于需要循环访问的场景如任务调度、约瑟夫环问题或循环队列。//使用数组创建循环链表typedefstructnode{intdata;structnode*next;}node;structnode*create_list(intdata[],intn){node*head(node*)malloc(sizeof(structnode));if(headNULL)returnNULL;node*phead;for(inti0;in;i){node*tmp(node*)malloc(sizeof(structnode));if(tmpNULL)returnNULL;tmp-datadata[i];p-nexttmp;pp-next;}p-nexthead;returnhead;}3.1循环链表的反转//循环链表的反转voidchange(node*head){node*prevhead;node*nextNULL;node*currhead-next;while(curr!head){nextcurr-next;curr-nextprev;prevcurr;currnext;}curr-nextprev;}三、链表与数组的对比特性数组链表内存分配连续内存非连续节点分散访问方式支持随机访问O(1)不支持随机访问需要遍历O(n)插入/删除开头或中间O(n)末尾O(1)动态数组可能扩容已知节点O(1)否则查找位置O(n)空间开销数据本身数据 指针单链表 1 个双链表 2 个扩展性固定长度或动态扩容动态可随时增加或删除节点优势随机访问快内存紧凑编程简单插入删除灵活适合动态操作双向遍历或循环操作方便劣势插入删除开销大扩容可能耗时随机访问慢指针开销大编程复杂总之数组适合频繁访问链表适合频繁插入删除。