一.简介

上一篇文章，我们介绍了线性表中的顺序表。

而顺序表拥有一些缺陷

1.空间不够时需要增容，增容需要付出代价

2.为避免重复扩容，我们进行指数扩容，可能会造成空间浪费

3.顺序表从开始位置连续存储，插入删除数据需要移动，效率不高

而这篇文章，我们来介绍一下链表中的单链表

链表

概念

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

结构

当存储数据时，我们需要在堆上申请空间，因而每个数据都会有相应的地址。

而我们将这个地址存储在一个指针变量中与上一个数据放在一起，便可以将众多数据链接在一起。

分类

链表拥有多种结构，可以分为三类

单向/双向

带头/不带头 

 head：哨兵位

循环/非循环

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

无头单向非循环链表

有头双向循环链表

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

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

而我们要介绍的便是无头单项非循环链表

二.结构体与初始化

我们将数据与指针变量作为结构成员构建一个结构体，并像顺序表一样进行类型的重命名

typedef int SLTDateType;typedef struct SListNode
{SLTDateType data;struct SListNode* next;
}SLTNode;

不同于结构体，单链表是一种非常简单的结构，因此不需要进行初始化，只需要设立一个结构体空指针。

SLTNode* plist = NULL;

三.功能实现

1.打印

显然，我们应该使用循环来进行打印，每次打印完该结构体的data变量时，通过next指针变量前往下一个结构体。而循环的终止条件（即链表走到尾部），应当是结构体的next指针变量为空指针。

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

2.销毁

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

3.尾插

不同于顺序表，我们无须扩容，而是每次插入时开辟一块空间

要进行尾插，需要找到链表中尾部的结构体（tail），将新的结构体的地址赋给next变量。

（注意：由于要对链表进行改变，我们要进行传址调用，由于phead本身就是指针，所以我们要用 到二级指针进行传参）

void SListPushBack(SLTNode** pphead, SLTDateType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){exit(-1);}newnode->data = x;newnode->next = NULL;if (*pphead == NULL)//由于无哨兵位，若链表为空只需要赋值{*pphead = newnode;}else{SLTNode* tail = *pphead;//找尾while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}SListPrint(*pphead);
}

4.头插

 当我们进行头插时，需要将phead作为指针变量存储在新创建的结构体的next中，之后将新创建的结构体的地址作为新的phead

void SListPushFront(SLTNode** pphead, SLTDateType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){exit(-1);}newnode->data = x;newnode->next = *pphead;//当链表中没有数据时，为NULL，同样成立*pphead = newnode;SListPrint(*pphead);
}

5.尾删

当链表中只有一个数据时，我们只需要将其至为空指针

而当拥有多个数据时

我们不止是需要释放尾部的结构体（tail），还需要找到尾部的结构体的前一个（tailPrev），将其中的next置为NULL。 

void SListPopBack(SLTNode** pphead)
{assert(*pphead != NULL);if ((*pphead)->next != NULL){SLTNode* tailPrev = *pphead;while (tailPrev->next->next != NULL){tailPrev = tailPrev->next;}free(tailPrev->next);tailPrev->next = NULL;}else{*pphead = NULL;}SListPrint(*pphead);
}

6.头删

 若我们先将第二个结构体的地址赋给phead，会找不到第一个结构体，无法进行释放

而若我们先进行释放，会无法找到第二个结构体的地址并将其赋给phead

因此我们需要一个中间变量next

void SListPopFront(SLTNode** pphead)
{assert(*pphead != NULL);SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;SListPrint(*pphead);
}

7.查找数据地址

主要是与插入删除配合使用，没啥好说的，自己看吧。

SLTNode* SListFind(SLTNode* phead, SLTDateType x)
{SLTNode* cur = phead;while (cur != NULL){if (cur->data == x){return cur;}else{cur = cur->next;}}return NULL;
}

8.pos地址前后的插入

后插

void SListInsertAfter(SLTNode* pos, SLTDateType x)
{assert(pos);SLTNode* newnode = BuyListNode(x);newnode->next = pos->next;pos->next = newnode;
}

前插

void SListInsertBefore1(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){exit(-1);}newnode->data = x;if (*pphead == pos){newnode->next = *pphead;*pphead = newnode;}else{SLTNode* posPrev = *pphead;while (posPrev->next != NULL){if (posPrev->next==pos){newnode->next = pos;posPrev->next = newnode;break;}posPrev = posPrev->next;}}SListPrint(*pphead);
}

9.删除

void SListErase(SLTNode** pphead, SLTNode* pos)
{assert(*pphead != NULL);if (pos == *pphead){SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;}else{SLTNode* posPrev = *pphead;while (posPrev->next!= pos){posPrev = posPrev->next;}posPrev->next = pos->next;free(pos);}SListPrint(*pphead);
}

四.优缺点

优点

1.按需申请空间，不用了就释放空间，更合理的使用空间

2.插入删除数据不需要进行挪动

3.不存在空间浪费

缺点

1.每次存一个数据，都要存一个指针链接下一个数据

2.不支持随机访问

（二分查找、优化的快排都需要随机访问）