前言
数据结构之顺序表中我们有讲到顺序表有一些问题和缺点，为了能解决顺序表的问题，我们引入一个新的线性表——链表
一、链表
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表 中的指针链接次序实现的 。
链表与顺序表的不同
1.链表是按需申请空间的
2.链式结构在逻辑上是连续的但是在物理结构上不一定是连续的；两次申请的空间可能是连续的，也可能是不连续的。
注意：链表和顺序表所申请的空间都是在堆上申请的。（动态开辟的空间都是在堆上申请的）
二、链表的八种结构
1.单向或者双向
2.带头或者不带头（头：哨兵位）
3.循环或者不循环
以上三种类型，两两组合就能得到链表的八种结构，虽然有这么多种链表，但是我们最常用的还是两种：
1.无头单向非循环链表；
2.有头双向循环链表。
1.无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单。
我们今天主要介绍的是无头单向非循环链表（单链表）。
三、单链表
1.单链表的声明及接口的声明
typedef int SLTDataType; typedef struct SListNode { SLTDataType data; struct SListNode* next; }SLTNode; //动态申请一个新的节点 SLTNode* BuySLTNode(SLTDataType x); //打印单链表中的数据 void SLTPrint(SLTNode* phead); //单链表的头插 void SLTPushFront(SLTNode** pphead, SLTDataType x); //单链表的尾插 void SLTPushBack(SLTNode** pphead, SLTDataType x); //单链表的头删 void SLTPopFront(SLTNode** pphead); //单链表的尾删 void SLTPopBack(SLTNode** pphead); //单链表的查找 SLTNode* SLTFind(SLTNode* phead, SLTDataType x); // 单链表在pos位置之前插入x void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x); // 单链表在pos位置之后插入x void SLTInsertAfter(SLTNode* pphead, SLTNode* pos, SLTDataType x); // 单链表删除pos位置的节点 void SLTEarse(SLTNode** pphead, SLTNode* pos); // 单链表删除pos位置之后的节点 void SLTEarseAfter(SLTNode* pos);
2.接口的实现
1.开辟一个新的节点
（单链表是由一个节点一个节点链接起来的）
//开辟一个新的节点 SLTNode* BuySLTNode(SLTDataType x) { SLTNode* p = (SLTNode*)malloc(sizeof(SLTNode)); p->data = x; p->next = NULL; return p;
1.打印单链表
（方便调试观察）
//打印单链表中的数据 void SLTPrint(SLTNode* phead) { SLTNode* cur = phead; while(cur != NULL) { printf("%d ", cur->data); cur = cur->next; } printf("\n"); }
2.头插
//单链表的头插 void SLTPushFront(SLTNode** pphead, SLTDataType x) { SLTNode* NewNode = BuySLTNode(x); NewNode->next = *pphead; *pphead = NewNode; }
3.尾插
//单链表的尾插 void SLTPushBack(SLTNode** pphead, SLTDataType x) { SLTNode* NewNode = BuySLTNode(x); //单链表为空 if ((*pphead) == NULL) { NewNode->next = *pphead; *pphead = NewNode; } //单链表不为空 else { SLTNode* tail = *pphead; while (tail->next) { tail = tail->next; } tail->next = NewNode; } }
4.头删
//单链表的头删 void SLTPopFront(SLTNode** pphead) { assert(*pphead);//如果链表为空再继续删除就会报警告 SLTNode* cur = *pphead; *pphead = (*pphead)->next; free(cur); }
5.尾删
//单链表的尾删 void SLTPopBack(SLTNode** pphead) { assert(*pphead);//如果链表为空再继续删除就会报警告 SLTNode* cur = *pphead; if ((cur->next) != NULL) { SLTNode* prev = cur->next; while (prev->next != NULL) { prev = prev->next; cur = cur->next; } free(prev); cur->next = NULL; } else { free(cur); *pphead = NULL; } }
6.单链表的查找
//单链表的查找（找到了返回该节点的地址） SLTNode* SLTFind(SLTNode* phead, SLTDataType x) { SLTNode* p = phead; while (p) { if (p->data == x) { return p; } p = p->next; } assert(p); }
