C语言深入浅出：C语言链表的全面解析

严言

目录一、单链表1.基本概念节点结构定义2.创建链表示例代码输出结果3.插入节点示例代码输出结果4.删除节点示例代码输出结果二、双向链表1.基本概念节点结构定义2.创建双向链表示例代码输出结果3.插入节点示例代码输出结果4.删除节点示例代码输出结果三、循环链表1.基本概念节点结构定义2.创建循环链表示例代码输出结果3.插入节点示例代码输出结果4.删除节点示例代码输出结果四、链表的优缺点与应用1.优点2.缺点3.常见应用五、总结六、结束语相关文章：链表是一种常见的数据结构，由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。链表的最大特点是节点在内存中不必连续存储，因而在插入和删除操作时更加高效。下面我们将详细讲解C语言中单链表、双向链表和循环链表的基本概念、实现方法及其相关操作。以下是本文中提到的重要内容及其简要描述的表格：内容描述单链表（SinglyLinkedList）每个节点包含一个数据域和一个指针域，指向下一个节点。头节点指向链表的第一个节点，尾节点指向NULL。双向链表（DoublyLinkedList）每个节点包含数据域、前驱指针和后继指针，允许双向遍历。前驱指针指向前一个节点，后继指针指向后一个节点。循环链表（CircularLinkedList）最后一个节点的指针域指向头节点，形成一个环形结构。可以是单向的或双向的。创建节点动态分配内存，为链表创建新节点。插入节点将新节点插入到链表中的特定位置或链表末尾。删除节点从链表中移除特定节点，并释放相应的内存。动态内存分配链表节点在运行时动态分配和释放内存，不需要在编译时指定大小。插入和删除效率插入和删除操作效率高，在已知节点位置的情况下时间复杂度为O(1)。随机访问效率随机访问效率低，无法通过索引直接访问元素，必须从头开始遍历，时间复杂度为O(n)。应用常用于实现队列、栈、图和网络的表示等数据结构，以及内存管理中的空闲块管理。一、单链表1.基本概念单链表（SinglyLinkedList）是一种链表结构，其中每个节点包含一个数据域和一个指针域，指针域指向下一个节点。链表的第一个节点称为头节点，最后一个节点的指针域指向NULL，表示链表的结束。节点结构定义structNode{intdata;//数据域structNode*next;//指针域，指向下一个节点};12342.创建链表示例代码#include#include//节点结构定义structNode{intdata;structNode*next;};//创建新节点structNode*createNode(intdata){structNode*newNode=(structNode*)malloc(sizeof(structNode));newNode->data=data;newNode->next=NULL;returnnewNode;}//添加节点到链表末尾voidappend(structNode**headRef,intdata){structNode*newNode=createNode(data);if(*headRef==NULL){*headRef=newNode;}else{structNode*temp=*headRef;while(temp->next!=NULL){temp=temp->next;}temp->next=newNode;}}//打印链表voidprintList(structNode*head){structNode*temp=head;while(temp!=NULL){printf("%d->",temp->data);temp=temp->next;}printf("NULL\n");}intmain(){structNode*head=NULL;append(&head,1);append(&head,2);append(&head,3);printList(head);return0;}12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849输出结果1->2->3->NULL13.插入节点示例代码//在特定位置插入新节点voidinsertAfter(structNode*prevNode,intdata){if(prevNode==NULL){printf("前置节点不能为空\n");return;}structNode*newNode=createNode(data);newNode->next=prevNode->next;prevNode->next=newNode;}intmain(){structNode*head=NULL;append(&head,1);append(&head,2);append(&head,3);insertAfter(head->next,4);//在第二个节点后插入4printList(head);return0;}1234567891011121314151617181920输出结果1->2->4->3->NULL14.删除节点示例代码//删除包含特定数据的节点voiddeleteNode(structNode**headRef,intkey){structNode*temp=*headRef;structNode*prev=NULL;if(temp!=NULL&temp->data==key){*headRef=temp->next;free(temp);return;}while(temp!=NULL&temp->data!=key){prev=temp;temp=temp->next;}if(temp==NULL)return;prev->next=temp->next;free(temp);}intmain(){structNode*head=NULL;append(&head,1);append(&head,2);append(&head,3);deleteNode(&head,2);//删除包含数据2的节点printList(head);return0;}12345678910111213141516171819202122232425262728293031输出结果1->3->NULL1二、双向链表1.基本概念双向链表（DoublyLinkedList）是一种链表结构，其中每个节点包含三个部分：数据域、前驱指针域和后继指针域。前驱指针指向前一个节点，后继指针指向后一个节点。双向链表允许双向遍历。节点结构定义structDNode{intdata;structDNode*prev;//前驱指针structDNode*next;//后继指针};123452.创建双向链表示例代码#include#include//双向链表节点结构定义structDNode{intdata;structDNode*prev;structDNode*next;};//创建新节点structDNode*createDNode(intdata){structDNode*newNode=(structDNode*)malloc(sizeof(structDNode));newNode->data=data;newNode->prev=NULL;newNode->next=NULL;returnnewNode;}//添加节点到链表末尾voidappendD(structDNode**headRef,intdata){structDNode*newNode=createDNode(data);if(*headRef==NULL){*headRef=newNode;}else{structDNode*temp=*headRef;while(temp->next!=NULL){temp=temp->next;}temp->next=newNode;newNode->prev=temp;}}//打印双向链表voidprintDList(structDNode*head){structDNode*temp=head;while(temp!=NULL){printf("%d",temp->data);temp=temp->next;}printf("NULL\n");}intmain(){structDNode*head=NULL;appendD(&head,1);appendD(&head,2);appendD(&head,3);printDList(head);return0;}12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152输出结果123NULL13.插入节点示例代码//在特定节点后插入新节点voidinsertAfterD(structDNode*prevNode,intdata){if(prevNode==NULL){printf("前置节点不能为空\n");return;}structDNode*newNode=createDNode(data);newNode->next=prevNode->next;prevNode->next=newNode;newNode->prev=prevNode;if(newNode->next!=NULL){newNode->next->prev=newNode;}}intmain(){structDNode*head=NULL;appendD(&head,1);appendD(&head,2);appendD(&head,3);insertAfterD(head->next,4);//在第二个节点后插入4printDList(head);return0;}123456789101112131415161718192021222324输出结果1243NULL14.删除节点示例代码//删除包含特定数据的节点voiddeleteDNode(structDNode**headRef,intkey){structDNode*temp=*headRef;while(temp!=NULL&temp->data!=key){temp=temp->next;}if(temp==NULL)return;if(temp->prev!=NULL){temp->prev->next=temp->next;}else{*headRef=temp->next;}if(temp->next!=NULL){temp->next->prev=temp->prev;}free(temp);}intmain(){structDNode*head=NULL;appendD(&head,1);appendD(&head,2);appendD(&head,3);deleteDNode(&head,2);//删除包含数据2的节点printDList(head);return0;}1234567891011121314151617181920212223242526272829303132输出结果13NULL1三、循环链表1.基本概念循环链表（CircularLinkedList）是一种链表结构，其中最后一个节点的指针域指向链表的头节点，形成一个环形结构。循环链表可以是单向的或双向的。节点结构定义structCNode{intdata;structCNode*next;};12342.创建循环链表示例代码#include#include//循环链表节点结构定义structCNode{intdata;structCNode*next;};//创建新节点structCNode*createCNode(intdata){structCNode*newNode=(structCNode*)malloc(sizeof(structCNode));newNode->data=data;newNode->next=newNode;//初始时，节点的next指向自身returnnewNode;}//添加节点到循环链表末尾voidappendC(structCNode**headRef,intdata){structCNode*newNode=createCNode(data);if(*headRef==NULL){*headRef=newNode;}else{structCNode*temp=*headRef;while(temp->next!=*headRef){temp=temp->next;}temp->next=newNode;newNode->next=*headRef;}}//打印循环链表voidprintCList(structCNode*head){if(head==NULL)return;structCNode*temp=head;do{printf("%d->",temp->data);temp=temp->next;}while(temp!=head);printf("(backtohead)\n");}intmain(){structCNode*head=NULL;appendC(&head,1);appendC(&head,2);appendC(&head,3);printCList(head);return0;}123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051输出结果1->2->3->(backtohead)13.插入节点在循环链表中插入节点时，需要特别小心处理环的连接，以确保新节点正确地链接到链表中。示例代码//在特定位置后插入新节点voidinsertAfterC(structCNode*prevNode,intdata){if(prevNode==NULL){printf("前置节点不能为空\n");return;}structCNode*newNode=createCNode(data);newNode->next=prevNode->next;prevNode->next=newNode;}intmain(){structCNode*head=NULL;appendC(&head,1);appendC(&head,2);appendC(&head,3);insertAfterC(head->next,4);//在第二个节点后插入4printCList(head);return0;}1234567891011121314151617181920输出结果1->2->4->3->(backtohead)14.删除节点在循环链表中删除节点时，特别要注意处理头节点的删除和尾节点的循环连接。示例代码//删除包含特定数据的节点voiddeleteCNode(structCNode**headRef,intkey){if(*headRef==NULL)return;structCNode*curr=*headRef,*prev=NULL;//处理头节点可能是目标节点的情况if(curr->data==key){while(curr->next!=*headRef){curr=curr->next;}if(curr==*headRef){//链表只有一个节点free(*headRef);*headRef=NULL;}else{//链表有多个节点curr->next=(*headRef)->next;free(*headRef);*headRef=curr->next;}return;}//查找目标节点do{prev=curr;curr=curr->next;}while(curr!=*headRef&curr->data!=key);//未找到目标节点if(curr==*headRef)return;//解除目标节点prev->next=curr->next;free(curr);}intmain(){structCNode*head=NULL;appendC(&head,1);appendC(&head,2);appendC(&head,3);deleteCNode(&head,2);//删除包含数据2的节点printCList(head);return0;}123456789101112131415161718192021222324252627282930313233343536373839404142434445输出结果1->3->(backtohead)1四、链表的优缺点与应用1.优点动态内存分配：链表可以在运行时动态分配和释放内存，不需要在编译时指定大小。插入和删除效率高：在已知节点位置的情况下，链表的插入和删除操作非常高效，时间复杂度为O(1)。2.缺点额外的存储开销：每个节点需要存储指针，增加了内存使用。随机访问不便：无法通过索引直接访问元素，必须从头开始遍历，时间复杂度为O(n)。3.常见应用实现数据结构：如队列、栈等。内存管理：如动态内存分配器的空闲块管理。图和网络的表示：如邻接表表示法。五、总结链表是一种重要的基础数据结构，适用于频繁的插入和删除操作。通过本篇详细讲解了单链表、双向链表和循环链表的概念和实现，以及各类常用操作的示例代码。掌握链表的使用对于理解更复杂的数据结构和算法具有重要意义。六、结束语本节内容已经全部介绍完毕，希望通过这篇文章，大家对C语言链表有了更深入的理解和认识。感谢各位的阅读和支持，如果觉得这篇文章对你有帮助，请不要吝惜你的点赞和评论，这对我们非常重要。再次感谢大家的关注和支持！点我关注❤️相关文章：指针的神秘探险：从入门到精通的奇幻之旅!