1.链表
目录
1.链表
1.1链表的概念及结构
1.2 链表的分类
2.单链表的实现(不带哨兵位）
2.1接口函数
2.2函数的实现
3.双向链表的实现（带哨兵位）
3.1接口函数
3.2函数的实现
1.1链表的概念及结构
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
现实中 数据结构中
1.2 链表的分类
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
1. 单向或者双向
2. 带头或者不带头
3. 循环或者非循环
1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。
2.单链表的实现(不带哨兵位）
2.1接口函数
// 1、无头+单向+非循环链表增删查改实现
typedef int SLTDateType;
typedef struct SListNode
{
SLTDateType data;
struct SListNode* next;
}SListNode;
// 动态申请一个结点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置？
void SListEraseAfter(SListNode* pos);
//销毁单链表
void SLTDestroy(SLNode** pphead);2.2函数的实现
1. 动态申请一个结点
SListNode* BuySListNode(SLTDateType x) { SListNode* new = (SListNode*)malloc(sizeof(SListNode)); if (new == NULL) { perror(malloc); exit(-1); } new->data =x; new->next = NULL; return new; }动态申链表，并给新malloc出的空间传值。
2.单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x) { assert(pphead); SListNode* newlist = BuySListNode(x); if (*pplist == NULL) { *pplist = newlist; } else { SListNode* tail = NULL; tail = *pplist; while (tail->next != NULL) { tail = tail->next; } tail->next = newlist; } }1. 创建一个新节点，并为其分配内存空间。 2. 将新节点的数据赋值为要插入的数据。 3. 将新节点的指针域（next）设置为NULL，表示它是链表的最后一个节点。 4. 如果链表为空，将头指针指向新节点；否则，找到链表的最后一个节点，将其指针域指向新节点。
3.单链表的尾删
void SListPopBack(SListNode** pplist) { assert(pphead); assert(*pplist); if ((*pplist)->next == NULL) { free(*pplist); *pplist = NULL; } else { SListNode* tail = *pplist; SListNode* prve = NULL; while (tail->next != NULL) { prve = tail; tail = tail->next; } free(tail); tail = NULL;//不置空也没问题，出作用域自动销毁 prve->next = NULL; } }1. 如果链表为空，直接返回空链表。 2. 如果链表只有一个节点，释放该节点的内存空间，并将头指针指向NULL。 3. 遍历链表，找到倒数第二个节点。 4. 将倒数第二个节点的指针域设置为NULL，表示它是链表的最后一个节点。 5. 释放最后一个节点的内存空间。
3.单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x) { assert(pphead); SListNode* newlist = BuySListNode(x); newlist->next = *pplist; *pplist = newlist; }1. 创建一个新节点，并为其分配内存空间。 2. 将新节点的数据赋值为要插入的数据。 3. 将新节点的指针域指向当前的头节点。 4. 将头指针指向新节点。
4.单链表头删
void SListPopFront(SListNode** pplist) { assert(pphead); assert(*pplist); SListNode* tmp = (*pplist)->next; free(*pplist); *pplist = tmp; }1. 如果链表为空，直接返回空链表。 2. 将头指针指向第二个节点。 3. 释放第一个节点的内存空间。
5.单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x) { SListNode* find = plist; while (find != NULL) { if (find->data == x) { return find; break; } find = find->next; } return NULL; }1. 如果链表为空，返回NULL。 2. 遍历链表，逐个比较节点的数据与目标值。 3. 如果找到匹配的节点，返回该节点的指针；否则，返回NULL。
6.在pos节点后插入
void SListInsertAfter(SListNode* pos, SLTDateType x) { assert(pphead); if (pos == NULL) { return; } SListNode* newlist = BuySListNode(x); newlist->next = pos->next; pos->next = newlist; }1.判断了指定位置是否为NULL，如果为NULL，则直接返回，不进行插入操作。2.我们创建一个新节点，并将新节点的数据赋值为要插入的数据。3.我们将新节点的指针域指向指定位置节点原来的下一个节点，然后将指定位置节点的指针域指向新节点，完成插入操作。
7.删除pos节点后的值
void SListEraseAfter(SListNode* pos) { assert(pphead); if (pos == NULL || pos->next == NULL) { return; } SListNode* temp = pos->next; pos->next = temp->next; free(temp); }1.判断了指定位置是否为NULL或者指定位置的下一个节点是否为NULL，如果是，则直接返回，不进行删除操作。2.我们创建一个临时指针temp，指向指定位置节点的下一个节点。3.我们将指定位置节点的指针域指向temp节点的下一个节点，然后释放temp节点的内存空间，完成删除操作。
8.销毁单链表
先保存下一个的地址，在销毁当前节点。void SLTDestroy(SLNode** pphead) { assert(pphead); SLNode* cur = *pphead; while (cur) { SLNode* next = cur->next; free(cur); cur = next; } *pphead = NULL; }
9.分析思考为什么不在pos位置之前插入？为什么不删除pos位置？
这是因为单链表的节点只有一个指针指向下一个节点，没有指向前一个节点的指针。那该如何解决呢？请看后面双向链表的实现。
3.双向链表的实现（带哨兵位）
3.1接口函数
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int LTDataType;
typedef struct ListNode
{
struct ListNode* next;
struct ListNode* prev;
LTDataType data;
}LTNode;
LTNode* BuyLTNode(LTDataType x);
LTNode* LTInit();
void LTPrint(LTNode* phead);
void LTPushBack(LTNode* phead, LTDataType x);
void LTPopBack(LTNode* phead);
void LTPushFront(LTNode* phead, LTDataType x);
void LTPopFront(LTNode* phead);
int LTSize(LTNode* phead);
LTNode* LTFind(LTNode* phead, LTDataType x);
// pos֮ǰx
void LTInsert(LTNode* pos, LTDataType x);
// ɾposλ
void LTErase(LTNode* pos);
3.2函数的实现
我们可以注意到，在单链表和双线链表出参的不同，单链表传的是二级指针，而双向链表传的是一级指针。实际上这是有无哨兵位造成的，当没有哨兵位时，我们需要用二级指针去保存链表第一个节点的地址，此时改变的是结构体的指针，因此需要用结构体的二级指针，而带哨兵位，我们只需要改变哨兵位后面的节点（结构体），此时改变的是结构体，因此只需要用结构体的一级指针。
双向链表相较于单链表实际上就多了头指针域，这样就能找到当前节点的上一个节点，也就是可以轻松的做到在任意节点前插入。双向链表做到了“首尾呼应”，自然为节点不用指向NULL。
这样很多操作就变的简单，快捷，高效。
1.动态申请一个结点
LTNode* BuyLTNode(LTDataType x) { LTNode* node = (LTNode*)malloc(sizeof(LTNode)); if (node == NULL) { perror("malloc fail"); exit(-1); } node->data = x; node->next = NULL; node->prev = NULL; return node; }
2.头节点（哨兵位）的初始化
LTNode* LTInit() { LTNode* phead = BuyLTNode(0); phead->next = phead; phead->prev = phead; return phead; }
这里涉及到改变结构体的值的操作，当然也可以写成接收二级指针的形式，档期当前的方式当然也是可行的。这里的操作就是对哨兵位的初始化，我们可以看到，我们将头节点的前，后指针域都指向了自己，这样就保持了循环的效果。
3.双向链表尾插
void LTPushBack(LTNode* phead, LTDataType x) { assert(phead); LTNode* tail = phead->prev; LTNode* newnode = BuyLTNode(x); newnode->prev = tail; tail->next = newnode; newnode->next = phead; phead->prev = newnode; }
双向链表要实现尾删是非常便捷的，不用循环找到尾节点，因为头节点的前指针域就指向了尾节点，所以我们只需要一步就能找到尾了。然后我们只需尾节点 指向新节点，然后让新节点指向尾节点，之后再让新节点指向头节点，最后让头节点指向新节点就好了。
4.尾删
void LTPopBack(LTNode* phead) { assert(phead); assert(phead->next != phead); LTNode* tail = phead->prev; LTNode* tailPrev = tail->prev; free(tail); tailPrev->next = phead; phead->prev = tailPrev; }要删除尾节点，首先要找到尾节点和尾节点的前一个节点，然后释放掉尾节点，让新的尾节点指向头，再让头指向尾。
5.打印双向链表
void LTPrint(LTNode* phead) { assert(phead); assert(phead->next!=phead); printf("phead<=>"); LTNode* cur = phead->next; while (cur != phead) { printf("%d<=>", cur->data); cur = cur->next; } printf("\n"); }
当我们打印双向链表时，只存在头节点就不要打印了，所以我们可以加上第二句断言。
打印的时候我们从头节点的下一个节点开始打印，最后走一圈遍历到头的时候就停止打印。
这里我就省略头插，头删，求节点个数和查找了，因为操作大同小异，十分简单，最后会奉上完整代码。
6.pos节点前插入
void LTInsert(LTNode* pos, LTDataType x) { assert(pos); LTNode* posPrev = pos->prev; LTNode* newnode = BuyLTNode(x); posPrev->next = newnode; newnode->prev = posPrev; newnode->next = pos; pos->prev = newnode; }
想要在pos节点的前面插入，那么只需要找到pos节点和pos节点前面的节点就可以了，找pos节点我们可以配合查找函数来使用，找到想要的pos节点就可以了。
7.删除pos节点
void LTErase(LTNode* pos) { assert(pos); LTNode* posPrev = pos->prev; LTNode* posNext = pos->next; free(pos); posPrev->next = posNext; posNext->prev = posPrev; }
想要删除pos节点，只需要找到pos节点的前一个和pos节点的后一个，free掉pos节点，然后让pos节点的前一个和pos节点的后一个连接就好了。
这就是链表的全部内容了，希望对各位老铁有帮助，接下来我会更新链表的OJ题目，希望各位老铁，多多支持！！！
