单链表
- 单链表的优点
1.头部和中间插入或删除数据效率高，无需挪动。
2.按照需求申请释放空间，无需担心空间不够用。
- 单链表的缺点
1.不可以进行下标随机访问。
2.复杂度是O(n)
3.反向遍历困难
单链表是线性表的一种，单链表是链式存储的线性表，不同于单链表，链表在内存空间中不连续，而是由结构体内的next指针下一条数据进行链接🧐
PS:需要源码直接通过目录跳转到最后
单链表主体结构
默认大小与扩容大小还有类型都可以是任意大小或类型
typedef int LLDataType; //数据类型 typedef struct LinkedList { LLDataType data; //用于存放数据 struct LinkedList* next; //指向下一个数据 }LinkedList;
单链表操作函数介绍
void printLL(LinkedList* Phead); //打印单链表
void LLPushBack(LinkedList** PPhead, LLDataType x); //尾插
void LLPushFront(LinkedList** PPhead, LLDataType x); //头插
void LLPopBack(LinkedList** PPhead); //尾删
void LLPopFront(LinkedList** PPhead); //尾插
LinkedList* LListFind(LinkedList* phead, LLDataType x); //查找
void SListInsertAfter(LinkedList* pos, LLDataType x); //在指定位置后插入
void SListEraseAfter(LinkedList* pos); //删除指定位置后的一个表
void SListDestroy(LinkedList** Phead); //销毁单链表
void SListInsertFront(LinkedList** Phead, LinkedList* pos, LLDataType x); //在指定位置前插入
void SListErase(LinkedList** PPhead, LinkedList* pos); //删除指定位置数据
为了代码方便阅读，讲单链表操作函数全部放在LinkedList.c文件中，将头文件放在LinkedList.h，测试文件test.c 😮
单链表操作函数实现
为了方便调试，建议每写完1-2个函数就进行测试，初始化之后，首先实现print函数可以方便我们进行调试。
单链表的初始化：
LinkedList *Phead = NULL; //未进行插入之前，头结点指针指向NULL
必须先进性初始化，讲链表指向NULL避免野指针问题。
打印函数
写完插入立马写打印，方便进行调试
void printLL(LinkedList* Phead) { while (Phead!=NULL) { printf("%d->", Phead->data); Phead = Phead->next; } printf("NULL"); }
单链表插入函数：
头插
头插将新结点插入到头结点
1.如果头结点不为空，头结点改为新插入的结点，原本的第一个位置的结点需要连接到新结点的next。
2.如果头结点为空，那么直接将新结点给到头结点指针phead
- 既然有插入就一定会有空间不够用的问题，这里用到检查空间是否够用的一个函数
LinkedList* BuyNewNode(LLDataType x) //申请一个新结点并将next指向空 { LinkedList* ret = (LinkedList*)malloc(sizeof(LinkedList)); if (ret == NULL) { perror("Malloc:"); return NULL; } ret->data = x; ret->next = NULL; return ret; } void LLPushFront(LinkedList** PPhead, LLDataType x) // 使用二级指针是因为我们要改变头结点，所有必须要使用头结点的指针来改变。 { assert(PPhead); LinkedList* NewNode = BuyNewNode(x); if (*PPhead == NULL) { *PPhead = NewNode; } else { NewNode->next = *PPhead; *PPhead = NewNode; } }
头结点为空
- 如果头结点为空，那么直接将新结点给到头结点指针phead
头结点不为空
- 如果头结点不为空，头结点改为新插入的结点，原本的第一个位置的结点需要连接到新结点的next。
尾插
从最后一个结点后面插入新结点
- 尾插也会用到申请新结点的函数，这里不重复了
void LLPushBack(LinkedList** PPhead, LLDataType x) // 使用二级指针是因为我们要改变头结点，所有必须要使用头结点的指针来改变。 { assert(PPhead); LinkedList* NewNode = BuyNewNode(x); //也用到了上面的BugNode不重复了 if (*PPhead == NULL) { *PPhead = NewNode; } else { LinkedList* tail = *PPhead; while (tail->next != NULL) { tail = tail->next; } tail->next = NewNode; } }
头结点不为空
- 如果头结点不为空，先找到最后一个结点（指向NULL的就是最后一个结点），然后将新结点插入到最后一个结点的后面
头结点为空
- 如果头结点为空，那么直接将新结点给到头结点指针phead(与上面头插头结点为空相同)
指定结点后插入和查找函数
相对上面两个简单，下面插入函数都需搭配查找结点函数使用，查找函数就是遍历，找到返回地址，比较简单，就不多描述了。
LinkedList* LListFind(LinkedList* phead, LLDataType x) { assert(phead); LinkedList *ret = phead; while (ret->data != x) { if (ret == NULL) { return NULL; } ret = ret->next; } return ret; } void SListInsertAfter(LinkedList* pos, LLDataType x) { assert(pos); LinkedList *newnode = BuyNewNode(x); newnode->next = pos->next; pos->next = newnode; }
单链表结点之前插入数据
void SListInsertFront(LinkedList** PPhead, LinkedList* pos, LLDataType x) { assert(pos); assert(PPhead); if (*PPhead == NULL||*PPhead==pos) { LLPushFront(PPhead, x); } else { LinkedList* cur = *PPhead; while (cur->next != pos) { cur = cur->next; } LinkedList* newnode = BuyNewNode(x); newnode->next = cur->next; cur->next = newnode; } }
- 头结点为空或插入结点就是头结点指向的结点，直接复用头插函数即可
