C语言数据结构系列：链表详解与代码示例

一、链表的数据结构

链表是一种线性数据结构，其元素在逻辑上是线性排列的，但在物理存储上不要求连续。

每个元素（节点）包含数据域 + 指针域，通过指针将节点链接起来，数据域是存储的数据信息，指针域是指向下一个节点的指针。

typedefstructListNode{intdata;structListNode*next;}ListNode;ListNode*a;

• data：存储的数据
• next：next 是一个 指向 struct ListNode类型的指针
• 最后一个节点next = NULL
• a 是一个指向 ListNode结构体的指针

二、链表的类型

头指针：是指向链表第一个节点的指针，用来表示链表的起始位置。如果链表没有头结点，那么头指针直接指向第一个数据节点；如果链表有头结点，那么头指针指向头结点。头指针用于访问整个链表，因此头指针是链表结构所必需的。

1.有头结点的链表和无头结点的链表

头结点：是人为在链表最前端增加的一个辅助节点，通常不保存实际数据。头结点的 next 指针指向链表中的第一个数据节点。

对于头结点来说，其数据域可以为空，也可以存储一些附加信息，例如链表长度等。头结点的主要作用是作为链表操作的统一入口，因此头结点不是链表结构所必需的，但在实现中经常被引入以简化操作。

1.1创建一个有头结点的空链表

#include<stdio.h>#include<stdlib.h>//定义结点typedefstructListNode{intdata;structListNode*next;}ListNode;//创建结点ListNode*list_create_node(intdata){ListNode*node=(ListNode*)malloc(sizeof(ListNode));if(node==NULL)returnNULL;node->data=data;node->next=NULL;returnnode;}//创建一个带头结点的空链表ListNode*list_create(){ListNode*head=(ListNode*)malloc(sizeof(ListNode));if(head==NULL)returnNULL;head->next=NULL;returnhead;}

1.2创建无头结点的空链表

#include<stdio.h>#include<stdlib.h>typedefstructListNode{intdata;structListNode*next;}ListNode;ListNode*list_create(){ListNode*head=NULL;// 空链表returnhead;}

【注意】
无论链表是否设置头结点，头指针始终指向链表的第一个节点。当存在头结点时，第一个节点就是头结点；当没有头结点时，第一个节点就是第一个数据节点。

那么为何要引入头结点呢？

如果链表没有头结点，头指针直接指向第一个数据节点。当需要在第一个节点之前插入新的节点时，需要修改头指针的指向，例如：

1.在第一个节点前插入新节点，需要让头指针指向新节点
2.删除第一个节点时，也需要更新头指针

也就是说，在这种情况下，头指针需要频繁改变指向，并且对第一个节点的操作需要进行特殊处理。

2.单向列表和双向链表

2.1单向链表

每个节点只包含一个 next 指针，指向链表中的下一个节点。链表从头节点开始依次连接到尾节点，尾节点的 next 为 NULL（空指针）。单向链表的特点是结构简单，占用内存少，但只能从前往后遍历，无法直接访问前驱节点。

2.1.1单向列表的插入

//添加结点(头插法)boollist_insert_head(ListNode*head,intdata){if(head==NULL)returnfalse;ListNode*node=list_create_node(data);if(node==NULL)returnfalse;node->next=head->next;head->next=node;returntrue;}//尾插法boollist_insert_tail(ListNode*head,intdata){if(head==NULL)returnfalse;ListNode*curr=head;while(curr->next)curr=curr->next;ListNode*node=list_create_node(data);if(node==NULL)returnfalse;curr->next=node;returntrue;}//指定位置插入(第n个结点之后插入)（除头结点之外）boollist_insert_after(ListNode*head,intpos,intdata){if(head==NULL)returnfalse;ListNode*curr=head;for(inti=0;i<pos;i++){if(curr->next==NULL)returnfalse;curr=curr->next;}ListNode*node=list_create_node(data);if(node==NULL)returnfalse;node->next=curr->next;curr->next=node;returntrue;}

2.1.2单向链表的删除

//删除头结点之后的第一个结点boollist_delete_first(ListNode*head){if(head==NULL||head->next==NULL)returnfalse;ListNode*tmp=head->next;head->next=tmp->next;free(tmp);returntrue;}//删除第n个结点(计数)boollist_delete_n(ListNode*head,intn){if(head==NULL)returnfalse;ListNode*curr=head;for(inti=0;i<n;i++){if(curr->next==NULL)returnfalse;curr=curr->next;}ListNode*target=curr->next;if(target==NULL)returnfalse;curr->next=target->next;free(target);returntrue;}

2.1.3单向链表的反转

voidlist_reverse(ListNode*head){if(head==NULL||head->next==NULL)return;ListNode*prev=NULL;ListNode*curr=head->next;ListNode*next=NULL;while(curr){next=curr->next;curr->next=prev;prev=curr;curr=next;}head->next=prev;}

2.2双向链表

每个节点包含两个指针：next 指向后继节点，prev 指向前驱节点。双向链表允许从前向后和从后向前遍历，插入和删除节点时可以直接访问前驱节点，操作更灵活。但每个节点需要额外的存储空间用于 prev 指针，结构比单向链表复杂。

2.2.1创建双向链表

//结构体typedefstructDListNode{intdata;structDListNode*next;structDListNode*prev;}DListNode;//利用数组创建双向链表DListNode*dlist_create_from_array(intdata[],intn){DListNode*head=malloc(sizeof(DListNode));if(head==NULL)returnNULL;head->next=NULL;head->prev=NULL;DListNode*p=head;for(inti=0;i<n;i++){DListNode*tmp=malloc(sizeof(DListNode));if(tmp==NULL)returnNULL;tmp->data=data[i];tmp->next=NULL;tmp->prev=p;p->next=tmp;p=tmp;}returnhead;}

2.2.2双向列表的插入

头插法

booldlist_insert_head(DListNode*head,intdata){if(head==NULL)returnfalse;DListNode*node=malloc(sizeof(DListNode));if(node==NULL)returnfalse;node->data=data;DListNode*first=head->next;node->next=first;node->prev=head;head->next=node;if(first)first->prev=node;returntrue;}

尾插法

booldlist_insert_tail(DListNode*head,intdata){if(head==NULL)returnfalse;DListNode*curr=head;while(curr->next)curr=curr->next;DListNode*node=malloc(sizeof(DListNode));if(node==NULL)returnfalse;node->data=data;node->next=NULL;node->prev=curr;curr->next=node;returntrue;}

指定位置插入

voiddlist_insert_after(DListNode*head,intn,intdata){DListNode*curr=head;for(inti=0;i<n;i++){if(curr->next==NULL)return;curr=curr->next;}DListNode*new_node=malloc(sizeof(DListNode));if(new_node==NULL)return;new_node->data=data;DListNode*next_node=curr->next;curr->next=new_node;new_node->prev=curr;new_node->next=next_node;if(next_node)next_node->prev=new_node;}

2.2.3双向链表的删除

voiddelete_point(DListNode*head,intn){for(inti=0;i<n;i++){if(head==NULL)return;head=head->next;}if(head==NULL)return;DListNode*curr=head;DListNode*prev=head->prev;DListNode*next=head->next;if(prev!=NULL)prev->next=next;if(next!=NULL)next->prev=prev;free(curr);}

2.2.4双向链表的反转

//双向链表的反转voidchange(DListNode*list){DListNode*curr=list->next;DListNode*next=NULL;DListNode*prev=NULL;while(curr){next=curr->next;curr->next=prev;curr->prev=next;prev=curr;curr=next;}list->next=prev;prev->prev=list;}

3.循环链表

循环链表是一种特殊的链表结构，其最后一个节点的指针指向链表的头节点，从而形成一个首尾相连的循环。它可以是单向或双向链表，特点是可以从任意节点开始遍历而不必考虑末尾空指针，常用于需要循环访问的场景，如任务调度、约瑟夫环问题或循环队列。

//使用数组创建循环链表typedefstructnode{intdata;structnode*next;}node;structnode*create_list(intdata[],intn){node*head=(node*)malloc(sizeof(structnode));if(head==NULL)returnNULL;node*p=head;for(inti=0;i<n;++i){node*tmp=(node*)malloc(sizeof(structnode));if(tmp==NULL)returnNULL;tmp->data=data[i];p->next=tmp;p=p->next;}p->next=head;returnhead;}

3.1循环链表的反转

//循环链表的反转voidchange(node*head){node*prev=head;node*next=NULL;node*curr=head->next;while(curr!=head){next=curr->next;curr->next=prev;prev=curr;curr=next;}curr->next=prev;}

三、链表与数组的对比

总之，数组适合频繁访问，链表适合频繁插入删除。