链表的概念和结构

1. 链表的概念

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

2. 链表的分类

类别的分类主要由以下几种情况组合起来的，一共合计8种：

1）单向或者双向链表

2）带头或不带头链表

3）循环或者非循环链表

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

1）无头单向非循环链表

它的结构简单，一般不会单独用来存数据，实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等

2）带头双向循环链表

它的结构最复杂，一般用在单独存储数据，实际中使用的链表数据结构，都是带头双向循环链表。它的结构复杂但会带来很多优势，实现反而简单了。

3. 单向不带头非循环链表

下面将其分为3个模块进行实现SList.h，SList.c，test.c

3.1 接口设计（SList.h）

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int SLNDataType;//单链表
typedef struct SListNode
{SLNDataType val;		//存储值struct SListNode* next;	//下一个结点
}SLNode;//打印创建
void SLTPrint(SLNode* phead);
SLNode* CreateNode(SLNDataType x);//头尾插入删除
void SLTPushBack(SLNode** pphead, SLNDataType x);
void SLTPushFront(SLNode** pphead, SLNDataType x);
void SLTPopBack(SLNode** pphead);
void SLTPopFront(SLNode** pphead);//查找插入
SLNode* SLTFind(SLNode** pphead, SLNDataType x);
//在pos前面、后面插入
void SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x);
void SLTInsertAfter(SLNode* pos, SLNDataType x);//删除当前或后面一个结点
void SLTErase(SLNode** pphead, SLNode* pos);
void SLTEraseAfter(SLNode* pos);void SLTDestroy(SLNode** pphead);

3.2 接口实现（SList.c）

1）打印和创建结点

打印操作不需要改变链表，因此不需要二级指针。

void SLTPrint(SLNode* phead)
{SLNode* cur = phead;while (cur != NULL){printf("%d -> ", cur->val);cur = cur->next;}printf("NULL\n");
}SLNode* CreateNode(SLNDataType x)
{SLNode* newNode = (SLNode*)malloc(sizeof(SLNode));if (newNode == NULL){perror("malloc fail\n");exit(-1);}newNode->val = x;newNode->next = NULL;return newNode;
}

2）头尾插入删除

这样要对链表进行操作，存在结点的指向问题。需要明确的是：对于函数传参问题，不在当前函数的都是外面的，要改变外面的就要用更高一级指针；所以改变外面结构体指针SLNode*，要用二级指针SLNode**

在free时，是将空间都释放完毕了，因此要注意free之前完成涉及的操作，释放空间后，如果再次使用该结构体，会发生内存泄漏或者野指针等问题。

void SLTPushBack(SLNode** pphead, SLNDataType x)
{assert(pphead);SLNode* newNode = CreateNode(x);if (*pphead == NULL){*pphead = newNode;}else{//next指向newNode改变的是结构体（结构体中的next）//即改变外面结构体Node，要用一级指针Node*SLNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newNode;}
}void SLTPushFront(SLNode** pphead, SLNDataType x)
{assert(pphead);SLNode* newNode = CreateNode(x);newNode->next = *pphead;*pphead = newNode;
}void SLTPopBack(SLNode** pphead)
{assert(pphead);assert(*pphead);//一个结点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}//多个结点else{//找尾//1/*SLNode* prev = NULL;SLNode* tail = *pphead;while (tail->next != NULL){prev = tail;tail = tail->next;}free(tail);tail = NULL;prev->next = NULL;*///2SLNode* tail = *pphead;while (tail->next->next != NULL){tail = tail->next;}free(tail->next);tail->next = NULL;}
}void SLTPopFront(SLNode** pphead)
{assert(pphead);assert(*pphead);//不管是一个还是多个结点SLNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}

3）查找和插入

严格限制pos一定是链表里的一个有效结点

//查找插入
SLNode* SLTFind(SLNode** pphead, SLNDataType x)
{assert(pphead);SLNode* cur = *pphead;while (cur != NULL){if (cur->val == x){return cur;}cur = cur->next;}return NULL;
}//在pos前面、后面插入
void SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x)
{//严格限制pos一定是链表里的一个有效结点assert(pphead);assert(*pphead);assert(pos);if ((*pphead) == pos){//头插SLTPushFront(pphead, x);}else{SLNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}SLNode* newNode = CreateNode(x);prev->next = newNode;newNode->next = pos;}
}void SLTInsertAfter(SLNode* pos, SLNDataType x)
{assert(pos);SLNode* newNode = CreateNode(x);newNode->next = pos->next;pos->next = newNode;
}

4）删除和销毁

务必保证删除的结点是属于链表里的一个有效结点

//删除当前或后面一个结点
void SLTErase(SLNode** pphead, SLNode* pos)
{assert(pphead);assert(*pphead);assert(pos);if ((*pphead) == pos){//头删SLTPopFront(pphead);}else{SLNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}void SLTEraseAfter(SLNode* pos)
{assert(pos);assert(pos->next);SLNode* tmp = pos->next;pos->next = pos->next->next;free(tmp);tmp = NULL;
}void SLTDestroy(SLNode** pphead)
{assert(pphead);SLNode* cur = *pphead;while (cur){SLNode* next = cur->next;free(cur);cur = NULL;cur = next;}*pphead = NULL;
}

3.3 完整代码

SList.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int SLNDataType;//单链表
typedef struct SListNode
{SLNDataType val;struct SListNode* next;
}SLNode;//打印创建
void SLTPrint(SLNode* phead);
SLNode* CreateNode(SLNDataType x);//头尾插入删除
void SLTPushBack(SLNode** pphead, SLNDataType x);
void SLTPushFront(SLNode** pphead, SLNDataType x);
void SLTPopBack(SLNode** pphead);
void SLTPopFront(SLNode** pphead);//查找插入
SLNode* SLTFind(SLNode** pphead, SLNDataType x);
//在pos前面、后面插入
void SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x);
void SLTInsertAfter(SLNode* pos, SLNDataType x);//删除当前或后面一个结点
void SLTErase(SLNode** pphead, SLNode* pos);
void SLTEraseAfter(SLNode* pos);void SLTDestroy(SLNode** pphead);

SList.c

#include "SList.h"//打印，不改变phead，所以不需要二级指针
void SLTPrint(SLNode* phead)
{SLNode* cur = phead;while (cur != NULL){printf("%d -> ", cur->val);cur = cur->next;}printf("NULL\n");
}SLNode* CreateNode(SLNDataType x)
{SLNode* newNode = (SLNode*)malloc(sizeof(SLNode));if (newNode == NULL){perror("malloc fail\n");exit(-1);}newNode->val = x;newNode->next = NULL;return newNode;
}//头尾插入删除
//不在当前函数的都是外面的，要改变外面的就要用更高一级指针
//传址问题：改变外面结构体指针Node*，要用二级指针Node**
//尾结点指向问题
void SLTPushBack(SLNode** pphead, SLNDataType x)
{assert(pphead);SLNode* newNode = CreateNode(x);if (*pphead == NULL){*pphead = newNode;}else{//next指向newNode改变的是结构体（结构体中的next）//即改变外面结构体Node，要用一级指针Node*SLNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newNode;}
}void SLTPushFront(SLNode** pphead, SLNDataType x)
{assert(pphead);SLNode* newNode = CreateNode(x);newNode->next = *pphead;*pphead = newNode;
}void SLTPopBack(SLNode** pphead)
{assert(pphead);assert(*pphead);//一个结点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}//多个结点else{//找尾//1/*SLNode* prev = NULL;SLNode* tail = *pphead;while (tail->next != NULL){prev = tail;tail = tail->next;}free(tail);tail = NULL;prev->next = NULL;*///2SLNode* tail = *pphead;while (tail->next->next != NULL){tail = tail->next;}free(tail->next);tail->next = NULL;}
}void SLTPopFront(SLNode** pphead)
{assert(pphead);assert(*pphead);//不管是一个还是多个结点SLNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}//查找插入
SLNode* SLTFind(SLNode** pphead, SLNDataType x)
{assert(pphead);SLNode* cur = *pphead;while (cur != NULL){if (cur->val == x){return cur;}cur = cur->next;}return NULL;
}//在pos前面、后面插入
void SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x)
{//严格限制pos一定是一个有效结点assert(pphead);assert(*pphead);assert(pos);if ((*pphead) == pos){//头插SLTPushFront(pphead, x);}else{SLNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}SLNode* newNode = CreateNode(x);prev->next = newNode;newNode->next = pos;}
}void SLTInsertAfter(SLNode* pos, SLNDataType x)
{assert(pos);SLNode* newNode = CreateNode(x);newNode->next = pos->next;pos->next = newNode;
}//删除当前或后面一个结点
void SLTErase(SLNode** pphead, SLNode* pos)
{assert(pphead);assert(*pphead);assert(pos);if ((*pphead) == pos){//头删SLTPopFront(pphead);}else{SLNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}void SLTEraseAfter(SLNode* pos)
{assert(pos);assert(pos->next);SLNode* tmp = pos->next;pos->next = pos->next->next;free(tmp);tmp = NULL;
}void SLTDestroy(SLNode** pphead)
{assert(pphead);SLNode* cur = *pphead;while (cur){SLNode* next = cur->next;free(cur);cur = NULL;cur = next;}*pphead = NULL;
}

test.c

#include "SList.h"void SLNTest()
{SLNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushFront(&plist, 5);SLTPushFront(&plist, 6);SLTPushFront(&plist, 7);SLTPushFront(&plist, 8);printf("头尾插入各4个：\n");SLTPrint(plist);SLNode* find1 = SLTFind(&plist, 5);SLTInsert(&plist, find1, 9);SLTInsertAfter(find1, 10);printf("找5的结点，并在前后分别插入9和10：\n");SLTPrint(plist);SLNode* find2 = SLTFind(&plist, 2);SLTEraseAfter(find2);SLTErase(&plist, find2);printf("删除2后面的结点，再删除2的结点：\n");SLTPrint(plist);SLTDestroy(&plist);printf("销毁全部结点：\n");SLTPrint(plist);
}int main()
{SLNTest();return 0;
}

运行效果

4. 带头双向循环链表

下面将其分为3个模块进行实现List.h，List.c，test.c

4.1 接口设计（List.h）

因为有哨兵位的存在，对头结点的插入删除时不需要改变外部链表，只需要改变结构体内部，因此这里的设计传参采用一级指针的方式

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int LTDataType;typedef struct ListNode
{LTDataType val;struct ListNode* next;struct ListNode* prev;
}LTNode;LTNode* LTInit();
void LTPrint(LTNode* phead);
LTNode* CreateLTNode(LTDataType x);void LTPushBack(LTNode* phead, LTDataType x);
void LTPushFront(LTNode* phead, LTDataType x);
void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);LTNode* LTFind(LTNode* phead, LTDataType x);
//在pos前插入
void LTInsert(LTNode* pos, LTDataType x);
//删除pos位置
void LTErase(LTNode* pos);
void LTDestroy(LTNode* phead);

4.2 接口实现（List.c）

1）创建结点

LTNode* CreateLTNode(LTDataType x)
{LTNode* newNode = (LTNode*)malloc(sizeof(LTNode));if (newNode == NULL){perror("malloc fail\n");exit(-1);}newNode->val = x;newNode->next = NULL;newNode->prev = NULL;return newNode;
}

2)初始化和打印

初始化将利用创建结点函数初始化，并返回指针。打印从哨兵位下一个结点开始，cur与哨兵位指针地址相同则结束

LTNode* LTInit()
{LTNode* phead = CreateLTNode(-1);phead->next = phead;phead->prev = phead;return phead;
}void LTPrint(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;printf("head <-> ");while (cur != phead){printf("%d <-> ", cur->val);cur = cur->next;}printf("head\n");
}

3）头尾插入删除

这里将展示3种办法实现，最重要的是要复用函数，这样可以在短时间内容快速手撕带头双向链表

第一种办法是不引入其他指针，要先设置好newNode；

第二种办法是引入多一个指针

第三种办法是复用 LTInsert() 和 LTErase()

void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);//1 不引入其他指针，要先设置好newNode//LTNode* newNode = CreateLTNode(x);//newNode->next = phead;//newNode->prev = phead->prev;//phead->prev->next = newNode;//phead->prev = newNode;//2 引入多一个指针//LTNode* newNode = CreateLTNode(x);//LTNode* tail = phead->prev;//phead->prev = newNode;//newNode->prev = phead;//newNode->next = tail;//tail->next = newNode;//3 复用插入LTInsert(phead, x);
}void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);//1//LTNode* newNode = CreateLTNode(x);引入多一个指针//LTNode* next = phead->next;//phead->next = newNode;//newNode->prev = phead;//newNode->next = next;//next->prev = newNode;//2 复用插入LTInsert(phead->next, x);
}void LTPopBack(LTNode* phead)
{assert(phead);//空的情况assert(phead->next != phead);//1 引入多一个//LTNode* tail = phead->prev;//LTNode* tailPrev = tail->prev;//free(tail);//tail = NULL;//tailPrev->next = phead;//phead->prev = tailPrev;//2 复用删除LTErase(phead->prev);
}void LTPopFront(LTNode* phead)
{assert(phead);//空的情况assert(phead->next != phead);//1//LTNode* tmp = phead->next;//phead->next = phead->next->next;//phead->next->prev = phead;//free(tmp);//tmp = NULL;//2LTErase(phead->next);
}

4）查找插入删除销毁

这里的插入删除是实现头尾插入删除部分函数复用的关键

需要明确的是插入为在pos前面插入

LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->val == x){return cur;}cur = cur->next;}return NULL;
}//在pos前插入
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newNode = CreateLTNode(x);LTNode* posPrev = pos->prev;posPrev->next = newNode;newNode->next = pos;newNode->prev = posPrev;pos->prev = newNode;
}//删除pos位置
void LTErase(LTNode* pos)
{assert(pos);LTNode* posPrev = pos->prev;LTNode* posNext = pos->next;posPrev->next = posNext;posNext->prev = posPrev;free(pos);pos = NULL;		//这个代码可有可无，因为pos改变不了外部
}void LTDestroy(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* tmp = cur;cur = cur->next;free(tmp);tmp = NULL;}free(phead);phead = NULL;	//和LTErase一致
}

4.3 完整代码

List.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int LTDataType;typedef struct ListNode
{LTDataType val;struct ListNode* next;struct ListNode* prev;
}LTNode;LTNode* LTInit();
void LTPrint(LTNode* phead);
LTNode* CreateLTNode(LTDataType x);void LTPushBack(LTNode* phead, LTDataType x);
void LTPushFront(LTNode* phead, LTDataType x);
void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);LTNode* LTFind(LTNode* phead, LTDataType x);
//在pos前插入
void LTInsert(LTNode* pos, LTDataType x);
//删除pos位置
void LTErase(LTNode* pos);
void LTDestroy(LTNode* phead);

List.c

#include "List.h"//创建
LTNode* CreateLTNode(LTDataType x)
{LTNode* newNode = (LTNode*)malloc(sizeof(LTNode));if (newNode == NULL){perror("malloc fail\n");exit(-1);}newNode->val = x;newNode->next = NULL;newNode->prev = NULL;return newNode;
}//初始化和打印
LTNode* LTInit()
{LTNode* phead = CreateLTNode(-1);phead->next = phead;phead->prev = phead;return phead;
}void LTPrint(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;printf("head <-> ");while (cur != phead){printf("%d <-> ", cur->val);cur = cur->next;}printf("head\n");
}//头尾插入删除
//第一种方法都是正常的实现，包括使用3个指针简化
//第二种方法是复用，从而快速实现
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);//1 不引入其他指针，要先设置好newNode//LTNode* newNode = CreateLTNode(x);//newNode->next = phead;//newNode->prev = phead->prev;//phead->prev->next = newNode;//phead->prev = newNode;//2 引入多一个指针//LTNode* newNode = CreateLTNode(x);//LTNode* tail = phead->prev;//phead->prev = newNode;//newNode->prev = phead;//newNode->next = tail;//tail->next = newNode;//3 复用插入LTInsert(phead, x);
}void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);//1//LTNode* newNode = CreateLTNode(x);引入多一个指针//LTNode* next = phead->next;//phead->next = newNode;//newNode->prev = phead;//newNode->next = next;//next->prev = newNode;//2 复用插入LTInsert(phead->next, x);
}void LTPopBack(LTNode* phead)
{assert(phead);//空的情况assert(phead->next != phead);//1 引入多一个//LTNode* tail = phead->prev;//LTNode* tailPrev = tail->prev;//free(tail);//tail = NULL;//tailPrev->next = phead;//phead->prev = tailPrev;//2 复用删除LTErase(phead->prev);
}void LTPopFront(LTNode* phead)
{assert(phead);//空的情况assert(phead->next != phead);//1//LTNode* tmp = phead->next;//phead->next = phead->next->next;//phead->next->prev = phead;//free(tmp);//tmp = NULL;//2LTErase(phead->next);
}//查找插入删除销毁
//上面提及的第二种办法就是复用插入和删除的函数
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->val == x){return cur;}cur = cur->next;}return NULL;
}//在pos前插入
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newNode = CreateLTNode(x);LTNode* posPrev = pos->prev;posPrev->next = newNode;newNode->next = pos;newNode->prev = posPrev;pos->prev = newNode;
}//删除pos位置
void LTErase(LTNode* pos)
{assert(pos);LTNode* posPrev = pos->prev;LTNode* posNext = pos->next;posPrev->next = posNext;posNext->prev = posPrev;free(pos);pos = NULL;		//这个代码可有可无，因为pos改变不了外部
}void LTDestroy(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* tmp = cur;cur = cur->next;free(tmp);tmp = NULL;}free(phead);phead = NULL;	//和LTErase一致
}

test.c

#include "List.h"void ListTTest()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPushFront(plist, 5);LTPushFront(plist, 6);LTPushFront(plist, 7);LTPushFront(plist, 8);printf("头尾各插入4个元素：\n");LTPrint(plist);LTPopBack(plist);LTPopBack(plist);LTPopFront(plist);LTPopFront(plist);printf("头尾各删除2个元素：\n");LTPrint(plist);printf("查找1的位置并在前面插入10：\n");LTNode* pos = LTFind(plist, 1);if (pos != NULL){LTInsert(pos, 10);}LTPrint(plist);printf("查找5的位置并将其删除：\n");pos = LTFind(plist, 5);if (pos != NULL){LTErase(pos);pos = NULL;}LTPrint(plist);printf("删除全部结点：\n");LTDestroy(plist);plist = NULL;LTPrint(plist);
}int main()
{ListTTest();return 0;
}

运行效果

5. 顺序表和链表的优缺点

不同点	顺序表	链表
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
随机访问	支持O(1)	不支持：O(N)
任意位置插入或者删除元素	可能需要搬移元素，效率低O(N)	只需修改指针指向
插入	动态顺序表，空间不够时需要扩容	没有容量的概念
应用场景	元素高效存储+频繁访问	任意位置插入和删除频繁
缓存利用率	高	低

总结：

1）链表（双向）

优势：a.任意位置插入和删除都是O(1)；b.按需申请释放，合理利用空间，不存在浪费

问题：下标访问不方便O(N)

2)顺序表

优势：支持下标随机访问O(1)

问题： a.头部或者中间插入删除效率低O(N)；b.空间不够需要扩容，扩容有一定消耗且存在一定空间浪费；c.只适合尾插尾删除