C语言链表超详解

一.顺序表与链表的对比

• 线性表
  线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列等，线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构（存储结构）上并不一定是连续的，线性表在物理上存储时，通常以顺序表和链式结构的形式存储。
  
• 线性表的顺序存储—>顺序表
  是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
  
• 线性表的链式存储
  线性表中的数据结点在内存中的位置是任意的，即逻辑上相邻的数据元素在物理位置（内存存储的位置）上不一定相邻。
  

链式存储结构的优点：

• 空间利用率高需要一个空间就分配一个空间
• 数据元素的逻辑次序靠节点的指针来指示，插入和删除时不需要移动数据结点,任意位置插入删除时间复杂度为O(1)

链式存储结构的缺点：

• 存储密度小，每个结点的指针域需要额外占用存储空间。当每个结点的数据域所占字节不多时，指针域所占空间的比重显得很大，存储密度大空间利用率越大。

顺序表因为只有数据域，没有指针域所以它的存储密度为最大1
不过这个问题，一个结点也就多几个指针，最多8个字节，所以若是在现代计算机这点空间已经不算什么，不过如果是像单片机这种嵌入式设备内存较小，所以还是会有一点点影响的

• 链式存储结构是非随机存取结构，对任一结点的操作都要从头指针依次查找到该节点，算法复杂度较高。

顺序表的优点：

• 存储密度为1最高，因为没有指针域空间利用率高
• 随机存取，按位置访问元素的时间复杂度为O(1)，直接根据数组下标访问元素

顺序表的缺点：

• 动态顺序表增容会付出一定性能消耗，其次可能还是会存在一定的空间浪费（不可能扩容的刚刚好）
• 在头部或者中部左右的插入删除，需要移动元素，时间复杂度为O(N),效率低。
  
  总结：
  顺序表的缺点就是链表的优点，而链表的缺点就是顺序表的优点，所以说不能说链表一定就比顺序表高级，我们要视情况而定。
  
  
  

二.单链表的介绍

• 线性表的链式存储
  线性表中的数据结点在内存中的位置是任意的，即逻辑上是线性的数据元素在物理位置（内存存储的位置）上不一定相邻。
  

结点为什么在内存中是随机存储的呢
因为我们产生一个结点要给他分配内存是动态分配出来的（malloc），而分配的结点的内存的地址是随机的，所以结点的地址是随机的，也就是说结点在内存中的存储是随机的。

单链表的一个结点


我们只要知道一个结构体的指针（地址），就能访问该结构体的成员（如果成员里面又包含下一个结点（结构体）指针，又可以访问下一个结点的成员）

三.单链表的基本操作

不带头结点单向不循序链表：

当链表为空时，头指针指向空，当链表不为空时头指针必须指向第一个结点

打印链表

void SListPrint(SLTNode *phead) { 
    SLTNode *cur = phead; while (cur != NULL) { 
    printf("%d->", cur->data); cur=cur->next; } printf("NULL\n"); } 

清空链表

//清空单链表

void SListClear(SLTNode **pphead) { 
    SLTNode *cur = *pphead; SLTNode *next = NULL; while (cur != NULL) { 
    next = cur->next; free(cur); cur = next; } *pphead = NULL; } 

如果要改变头指针的值，虽然头指针是一个指针，但是指针一样有它的地址，如果在一个函数中要改变它的值，照样要传头指针的地址，在解引用改变头指针的值，如果你只是值传递，则传过去的只是该头指针的临时拷贝，一旦出函数会自动销毁并不会影响头指针本身的值。

创建节点

SLTNode* CreateSListNode(SLTDataType x) { 
    SLTNode* NewNode = (SLTNode*)malloc(sizeof(SLTNode)); NewNode->data = x; NewNode->next = NULL; return NewNode; } 

因为插入元素时都先要创建一个新结点，所以为了避免代码冗余，将创建新结点单独封装成一个函数。

尾插结点

void SListPushBack(SLTNode **pphead, SLTDataType x) { 
    SLTNode*NewNode = CreateSListNode(x); //当链表为空 if (*pphead == NULL) { 
    *pphead = NewNode; } else { 
    SLTNode* tail = *pphead; while (tail->next != NULL) { 
    tail=tail->next; } tail->next = NewNode; } } 

不要写了if不写else，搞得后面又插入一个结点

头插结点

//链表头部插入一个节点 void SListPushFront(SLTNode **pphead, SLTDataType x) { 
    SLTNode*NewNode = CreateSListNode(x); NewNode->next = *pphead; *pphead = NewNode; } 

尾删结点

void SListPopBack(SLTNode **pphead) { 
    //链表为空 if (*pphead == NULL) { 
    return; } //只有一个节点 else if ((*pphead)->next == NULL) { 
    free(*pphead); *pphead = NULL; } //有多个节点 else { 
    SLTNode*prev = NULL; SLTNode*tail = *pphead; while (tail->next != NULL) { 
    prev = tail; tail = tail->next; } free(tail); prev->next = NULL; } } 

有以下几种情况：

• 当链表为空

• 只有一个结点
  
  
• 有多个结点
  
  

头删结点

void SListPopFront(SLTNode **pphead) { 
    if (*pphead == NULL) { 
    return; } SLTNode *next = (*pphead)->next; free(*pphead); *pphead = next; } 

查找值为x的节点

查找值为x的节点并返回节点的指针

//查找值为x的节点并返回节点的指针 SLTNode * SListFind(SLTNode *phead, SLTDataType x) { 
    SLTNode *cur = phead; while (cur != NULL) { 
    if (cur->data == x) { 
    //找到返回该结点指针 return cur; } cur = cur->next; } //找不到返回NULL指针 return NULL; } 

在pos前面插入一个结点

在pos指针指向的结点的前一个位置插入一个结点

 //在pos指针前一个插入一个节点 void SListInsert(SLTNode **pphead, SLTNode *pos, SLTDataType x) { 
    //pos在第一个节点，相当与头插 if (*pphead== pos) { 
    SListPushFront(pphead, x); } else { 
    SLTNode *NewNode = CreateSListNode(x); SLTNode *prev = *pphead; while (prev->next != pos) { 
    prev = prev->next; } prev->next = NewNode; NewNode->next = pos; } } 

如果pos的位置是第一个结点，则在第一个结点前一个插入结点则为头插，直接调用头插的接口函数即可。

pos在其他位置：

删除pos指针指向的结点

void SListErese(SLTNode **pphead, SLTNode *pos) { 
    if (*pphead == pos) { 
    SListPopFront(pphead); } else { 
    SLTNode *prev = *pphead; while (prev->next != pos) { 
    prev = prev->next; } prev->next=pos->next; free(pos); } } 

一样的如果pos的位置是第一个结点，则在第一个结点前一个删除结点则为头删，直接调用头删的接口函数即可。

pos在其他位置：

四.链表结构介绍

• 头指针

头指针是指向链表中第一个结点(存储该节点的地址)。如果链表中有头结点，则头指针指向头结点；若链表中没有头结点，则头指针指向链表中第一个数据结点。

• 头结点
  头结点，链表中第一个结点，一般不存储任何数据，若链表有头结点则头指针一直指向头指针。
  
  头结点本身没有什么作用，头结点就起到一个站岗的作用
  
  
  

链表带头结点的优点：

当链表为空表时，插入，删除结点都是在头结点后面，头结点指向了第一个带数据的结点。

当我们单链表无头结点时当我们头插，头插的时候，我们都需要移动头指针的位置指向新的第一个结点，当链表为空时又要将头结点置NULL，这些操作我们都需要去改变头指针的值，而改变头指针要传头指针的地址的，用二级指针来操作，无疑是增加了编程的难度，如果链表有头结点，而头指针一直指向头结点，不管是头删，头插，都是在头结点后面增加删除，而头指针一直指向头结点不用发生改变，只需要一级指针就搞定

• 循环链表
  循环链表：是一种头尾相接的链表（最后一个结点的指针指向第一个结点）
  
  优点：从表中任意一节点出发可找到表中其他结点
  
  
  

注意：
循环链表中没有NULL指针，故遍历链表时，其终止条件是判断是不是等于头指针。

• 双向链表
  前面我们用单链表如果我们知道一个结点但我们不能直接找到该结点前面的一个结点。
  

所以双向链表：在单链表的每一个结点再增加一个指向其直接前驱的指针域prev，这样链表中就形成了有两个方向不同的链

• 单向不带头不循环
  
  
• 单向带头不循环
  
  
• 单向不带头循环
  
  
• 单向带头循环
  
  
• 双向不带头不循环
  
  prev的值也为空
  
  
• 双向不带头循环
  
  
• 双向带头不循环
  
  prev的值也为空
  
  
• 双向带头循环
  
  

五.双向带头循环链表

创建结点

ListNode*CreateListNode(LTDataType x) { 
    ListNode*NewNode = (ListNode*)malloc(sizeof(ListNode)); NewNode->data = x; NewNode->next = NULL; NewNode->prev = NULL; return NewNode; } 

一个新的结点，先将next，prev置空

链表初始化

//链表初始化 ListNode *ListInit() { 
    ListNode*phead = CreateListNode(0); phead->next = phead; phead->prev = phead; return phead; } 

空表

销毁链表

void ListDestory(ListNode**pphead) { 
    ListNode*cur = (*pphead)->next; while (cur != *pphead) { 
    ListNode* next = cur->next; free(cur); cur = next; } free(*pphead); *pphead = NULL; } 

清空链表

//清空链表 void ListClear(ListNode*phead) { 
    ListNode*cur = phead->next; while (cur != phead) { 
    ListNode* next = cur->next; free(cur); cur = next; } phead->next = phead; phead->prev = phead; } 

只清空的话不需要释放头结点，不过要将头结点的两个指针域都指向自己（回到空表状态）

打印链表

//打印链表 void Listprint(ListNode*phead) { 
    ListNode*cur = phead->next; while (cur != phead) { 
    printf("%d ",cur->data); cur = cur->next; } printf("NULL\n"); } 

遍历是看是否遍历到了头结点才停下来。

尾插结点

//尾插 void ListPushBack(ListNode*phead, LTDataType x) { 
    assert(phead != NULL); ListNode*NewNode = CreateListNode(x); ListNode*tail = phead->prev; tail->next = NewNode; NewNode->prev = tail; NewNode->next = phead; phead->prev = NewNode; } 

可以怎么写：但是这里水太深你可能把握不住

头插结点

我们只要抓住一点：把要操作的结点事先存储起来，不管我们怎么连接结点，我们都找的到要操作的结点

//头插 void ListPushFront(ListNode*phead, LTDataType x) { 
    assert(phead != NULL); ListNode*NewNode = CreateListNode(x); ListNode*first = phead->next; phead->next = NewNode; NewNode->prev = phead; NewNode->next = first; first->prev = NewNode; } 

尾删结点

//尾删 void ListPopBack(ListNode*phead) { 
    assert(phead != NULL); assert(phead->next != phead); ListNode*tail = phead->prev; ListNode*prev = tail->prev; prev->next = phead; phead->prev = prev; free(tail); tail = NULL; } 

头删结点

//头删 void ListPopFront(ListNode*phead) { 
    assert(phead != NULL); assert(phead->next != phead); ListNode*first = phead->next;//除掉头结点第一个结点 ListNode*second = first->next;//除掉头结点第二个结点 phead->next = second; second->prev = phead; free(first); first = NULL; } 

查找节点值为x的结点

查找节点值为x的结点，返回指向节点的指针

//查找节点值为x，返回指向节点的指针 ListNode* ListFind(ListNode*phead, LTDataType x) { 
    ListNode*cur = phead->next; while (cur != phead) { 
    if (cur->data == x) { 
    return cur; } cur = cur->next; } return NULL; } 

在pos前面插入一个结点

//在pos指针指向的节点前插入一个节点 void ListInsert(ListNode*pos, LTDataType x) { 
    assert(pos != NULL); ListNode*NewNode = CreateListNode(x); ListNode*prev = pos->prev; prev->next = NewNode; NewNode->prev = prev; NewNode->next = pos; pos->prev = NewNode; } 

删除pos指针指向的结点

void ListErase(ListNode*pos) { 
    assert(pos !=NULL); ListNode*next = pos->next; ListNode*prev = pos->prev; prev->next = next; next->prev = prev; free(pos); pos = NULL; } 

链表长度

//链表长度 int ListLength(ListNode*phead) { 
    int len = 0; ListNode*cur = phead->next; while (cur != phead) { 
    len++; cur = cur->next; } return len; } 

六.总结

只要搞懂结构体指针，明白链表的概念，直接拿捏，相信很多人学完了链表还是不知道链表会用在什么地方，因为我们平时编程基本上用不到链表，但是链表在操作系统中的使用非常广泛，所以链表是非常重要重要的数据结构，有兴趣的可以看看在实际项目中链表的应用->《FreeRTOS实时操作系统-链表的源码解析》

结束语：
最近发现一款刷题神器，如果大家想提升编程水平，玩转C语言指针，还有常见的数据结构（最重要的是链表和队列）后面嵌入式学习操作系统的时如freerots、RT-Thread等操作系统，链表与队列知识大量使用。
大家可以点击下面连接进入牛客网刷题


点击跳转进入网站(C语言方向)
点击跳转进入网站(数据结构算法方向)