大话数据结构之 ＜链表＞（C语言）

引言：链表是一种常见的基础数据结构，属于线性表的一种，但它的存储方式与数组这类连续存储的线性表有所不同。链表由多个节点组成，每个节点在内存中的存储位置是随机的，它们通过指针或引用彼此连接。下面为你详细介绍链表的关键特性、常见类型以及实际应用场景。

链表的概念及结构

现实中 数据结构中 

链表的分类

链表的常见类型

• 单链表：这是最简单的链表类型，每个节点只包含一个指向下一个节点的指针。链表的遍历方向是单向的，只能从链表的头节点开始，依次向后访问各个节点。

• 双向链表：双向链表的每个节点包含两个指针，一个指向前一个节点，另一个指向后一个节点。这种结构使得链表可以双向遍历，既可以从前往后遍历，也可以从后往前遍历。

• 循环链表：循环链表又可分为单循环链表和双循环链表。单循环链表的尾节点的指针指向头节点，形成一个环形结构；双循环链表的头节点的前驱指针指向尾节点，尾节点的后继指针指向头节点。循环链表的特点是可以循环遍历，适合一些需要循环操作的场景。

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

2. 带头或者不带头 

3. 循环或者非循环 

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构： 

• 1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

• 2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而 简单了，后面我们代码实现了就知道了。

链表的关键特性

• 非连续存储：链表的各个节点在内存里是分散存放的，并非像数组那样连续排列。
• 节点结构：每一个节点通常包含两部分内容，一部分是数据域，用于存储具体的数据；另一部分是指针域，用于指向链表中的下一个节点或者前一个节点。
• 动态扩展：链表的长度能够动态改变，可以根据实际需求随时添加或删除节点，这使得它的内存使用效率更高。
• 插入和删除效率高：在链表中进行插入和删除操作时，一般不需要移动大量的元素，只需修改相关节点的指针即可，时间复杂度为 O (1)。不过，如果要在指定位置进行插入或删除操作，需要先遍历到该位置，此时时间复杂度为 O (n)。
• 随机访问困难：链表不支持像数组那样通过下标直接访问元素，要访问链表中的某个节点，必须从链表的头节点开始，依次遍历，直到找到目标节点，因此访问的时间复杂度为 O (n)。

顺序表和链表的区别

不带头不循环单链表：

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//实现一个最简单的不带头不循环单向链表
//因为不带哨兵位的头节点，所以不用初始化
//单链表可以为空，可以打印
//以下为单链表的基本实现的功能/*    1.打印单链表2.初始化3.尾插4.尾删5.头删6.头删7.查找 8.在pos位置之前插入9.pos位置删除10.在pos位置之后删除、11.在pos位置之后插入 
*/ typedef int SLTDataType;
//定义单个节点 
typedef struct SListNode
{	SLTDataType data;	     //数据域 -- 存放该节点存储的数据 struct SListNode* next;  //指针域 -- 存放下一个节点的地址 
}SLTNode;//打印函数 
void SLTPrint(SLTNode* phead)
{assert(phead);SLTNode* cur = phead;while(cur) {printf("%d->",cur->data);cur = cur->next; }printf("NULL\n");
}//创建新的节点 
SLTNode* BuySLTnode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if(newnode == NULL){perror("malloc fail");return NULL;}newnode->data = x;newnode->next = NULL;return newnode;
}//尾插 
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = BuySLTnode(x); if(*pphead == NULL){*pphead = newnode;}else{//找尾SLTNode* tail = *pphead;while(tail->next != NULL){tail = tail->next;} tail->next = newnode;}}//头插 
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead); SLTNode* newnode = BuySLTnode(x); newnode->next = *pphead;*pphead = newnode;
}//尾删 
void SLTPopBack(SLTNode** pphead)
{assert(pphead);assert(*pphead);if((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* tail = *pphead;while(tail->next->next != NULL){tail = tail->next;}free(tail->next);tail->next = NULL;}
}//头删 
void SLTPopFront(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* first = *pphead;*pphead = first->next;free(first);first = NULL;
}//查找 
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{assert(phead);SLTNode* cur = phead;while(cur){if(cur->data == x){return cur;}cur = cur->next;} return NULL;
}//在pos位置之前插入 
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(*pphead);if (pos == *pphead){SLTPushFront(pphead, x);}else{SLTNode* newnode = BuySLTnode(x);SLTNode* cur = *pphead;while(cur->next != pos){cur = cur->next;}	newnode->next = pos;cur->next = newnode;}	
}//pos位置删除 
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(*pphead);if (*pphead == pos){SLTPopFront(pphead);}else{SLTNode* cur = *pphead;while(cur->next != pos){cur = cur->next;	}cur->next = pos->next;free(pos);pos= NULL; }
}//pos位置后插入 
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode =  BuySLTnode(x);
//	SLTNode* next = pos->next->next;
//	poe->next = newnode;
//	newnode->next = next; newnode->next = pos->next;pos->next = newnode; 
}//pos位置后删除 
void SLTEraseAfter(SLTNode* pos)
{assert(pos);assert(pos->next);SLTNode* del = pos->next;pos->next = del->next;free(del);del = NULL;	
}int main()
{//现在我们来实现一下单链表的基本的功能//首先插入一些值，并打印出来观察一下 SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);SLTPrint(plist);//尾插一些值看一下 SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);	SLTPushFront(&plist, 5);	SLTPrint(plist);	//头删三个 //尾删三个//并打印一下看一下结果SLTPopBack(&plist); SLTPopBack(&plist);	SLTPopBack(&plist);SLTPopFront(&plist);SLTPopFront(&plist);SLTPopFront(&plist);SLTPrint(plist);//以上尾简单单链表的基本功能的实现//还有几个功能未使用//下次有机会再实现//return 0;} 

带头双向循环链表 

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>// 带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;}ListNode;//创建新的节点ListNode* BuyNode(LTDataType x)
{ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));if(newnode == NULL){perror("malloc fail");return;} newnode->data=x; newnode->next = NULL;newnode->prev = NULL;return newnode;} // 创建返回链表的头结点.
ListNode* ListCreate()
{ListNode* newnode = BuyNode(-1);newnode->prev = newnode;newnode->next = newnode;return newnode; 
}// 双向链表销毁
void ListDestory(ListNode* pHead)
{assert(pHead);ListNode* cur = pHead->next;while(cur != pHead){ListNode* next = cur->next;free(cur);cur = next; }free(pHead);}
// 双向链表打印
void ListPrint(ListNode* pHead)
{assert(pHead);ListNode* cur = pHead->next;printf("pHead<=>");while(cur != pHead){printf("%d<=>",cur->data);cur = cur->next; }
}// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* newnode =  BuyNode(x);ListNode* first = pHead->prev;newnode->next =pHead;pHead->prev = newnode;first-> next = newnode;newnode->prev= first;
}// 双向链表尾删
void ListPopBack(ListNode* pHead)
{assert(pHead);ListNode* tail = pHead->prev;ListNode* tailprev = tail->prev;tailprev->next = pHead;pHead-> prev = tailprev;free(tail);
}// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* newnode = BuyNode(x);
//	ListNode* head = pHead->next;
//	pHead->next = newnode;
//	newnode->prev = pHead;
//	newnode->next = head;
//	head->prev = newnode;   newnode->next = pHead->next;pHead->next->prev = newnode;pHead->next = newnode;newnode->prev = pHead; }// 双向链表头删
void ListPopFront(ListNode* pHead)
{assert(pHead);ListNode* first = pHead->next;ListNode* firstnext = first->next;pHead->next = firstnext;firstnext->prev = pHead;free(first);	}
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* cur = pHead->next;while(cur!= pHead){if(cur->data == x){return cur;}cur = cur->next; }return NULL;
}
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* newnode = BuyNode(x);ListNode* prev = pos->prev;prev->next = newnode;newnode->prev = prev;newnode->next = pos;pos->prev = newnode;  } 
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{assert(pos);ListNode* p = pos->prev;ListNode* q = pos->next;p->next = q;q->prev = p;free(pos); }int  main(){ListNode* sl =  ListCreate();ListPushBack(sl, 1);ListPushBack(sl, 2);ListPushBack(sl, 3);ListPushBack(sl, 4);ListPushBack(sl, 5);// ListPrint(sl);ListPushFront(sl, 1);ListPushFront(sl, 2);ListPushFront(sl, 3);ListPushFront(sl, 4);ListPushFront(sl, 5);ListPrint(sl);return 0 ;}