概述：
由于顺序表插入和删除元素需要移动大量数据，导致运行效率下降。因此引入了另一种数据结构 —— 链表。链表又分为单链表和双链表。单链表结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
一. 单链表的定义
单链表通过一组任意的存储单元来存储线性表中的数据元素，不需要使用地址连续的存储单元，因此它不要求在逻辑上相邻的两个元素在物理位置上也相邻。
构成：
单链表由一系列节点组成，每个节点包含两个部分：数据域（存储数据元素）和指针域（存储下一个节点地址）。
typedef int SLTDateType; typedef struct SListNode { SLTDateType date;//数据域 struct SListNode* next;//指针域 }SLTNode;
特点：
- 单链表的节点是离散分布在内存中的，通过指针将它们串联起来。
- 单链表可以动态地分配内存空间，可以根据需要灵活地插入、删除节点。
二. 单链表的创建
typedef int SLTDateType; typedef struct SListNode { SLTDateType date;//数据域 struct SListNode* next;指针域 }SLTNode;
首先创建一个结构体struct SListNode用来存储数据和指针。
考虑到后续数据类型修改的方便性，我们将struct SListNode 用typedef重命名为SLNode。
同时为方便以后调用接口实现不同数据类型链接，我们将数据域的类型int重命名为SLDateType。(后续存储不停数据只需修改此处即可)
三、单链表各种接口实现
1. 动态申请一个结点
后续要插入新节点时，首先要创建一个节点来存储相关信息，在连接到单链表合适位置。
代码实现：
SLTNode* BuySListNode(SLTDateType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL) { perror("malloc"); exit(-1); } newnode->date = x; newnode->next = NULL; return newnode; }
2. 单链表打印
打印单链表，我们只需记录头节点，然后遍历访问，依次打印即可。
代码实现：
void SLTPrint(SLTNode* phead) { SLTNode* cur = phead; while (cur) { printf("%d->", cur->date); cur = cur->next; } printf("NULL\n"); }
3. 尾插
尾插分两种情况：没有节点和有节点。
①：没有节点：创建一个新节点，然后头指针指向新节点。
②：有节点：遍历找到最后一个节点，然后将其下一个节点指向新节点
代码实现：
//由于尾插第一种情况需要改变结构体指针，所以我们要传结构体二级指针 void SLTPushBack(SLTNode** pphead, SLTDateType x) { assert(pphead); SLTNode* newnode = BuySListNode(x); if (*pphead == NULL)//没有节点 { *pphead = newnode; } else { //有节点 SLTNode* tail = *pphead; while (tail->next)//遍历找到最后一个节点 { tail = tail->next; } //尾插 tail->next = newnode; } }
4. 头插
头插就相对简单。不管原链表有无节点，只需插入新节点即可。
代码实现：
//由于头插会改变头指针，所以我们传二级指针 void SLTPushFront(SLTNode** pphead, SLTDateType x) { assert(pphead); SLTNode* newnode = BuySListNode(x);//新节点 //头插 newnode->next = *pphead; *pphead = newnode; }
5. 尾删
尾删分3中情况：
①：首先要判断链表中是否还有节点可删。
②：链表中只有一个节点。一个节点比较简单，将头指针置空，然后释放头节点即可。
③：链表中有多个节点。多个节点，首先要遍历找到尾节点的前一个节点。然后将其指针域置空，并释放尾节点。
代码实现：
void SLTPopBack(SLTNode** pphead) { assert(pphead); //1.空 assert(*pphead); if ((*pphead)->next == NULL)//2.一个节点 { (*pphead)->next = NULL; } else { //3.多个节点 SLTNode* tail = *pphead; 遍历找到尾节点的前一个节点 while (tail->next->next) { tail = tail->next; } free(tail->next); tail->next = NULL; } }
6. 头删
头删分两种情况：
①：首先判断链表中是否还有节点可删。
②：链表还有节点可删。首先保存第二个节点，在释放头节点。并将头指针指向第二个节点。
代码实现：
void SLTPopFront(SLTNode** pphead) { assert(pphead); //空 assert(*pphead); //非空 SLTNode* newnode = (*pphead)->next;//保存第二个节点 free(*pphead);//释放头节点 *pphead = newnode; }
7、查找
查找和打印一样，直接遍历访问即可。找到了返回地址，没有找打返回空指针。
代码实现：
SLTNode* SLTFind(SLTNode* phead, SLTDateType x) { SLTNode* cur = phead; while (cur) { if (cur->date == x) return cur; cur = cur->next; } return NULL; }
8、在pos之前插入x
链表中，不管是单链表还是双链表在某处插入新节点，一般默认前插。
前插分两种情况：
①：pos位置为第一个节点。可以复用前面头插接口实现。
②: 遍历访问链表找到pos前一个节点prev，然后将pos、prev、新节点连接起来。
代码实现：
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x) { assert(pphead); assert(*pphead); if (*pphead == pos) { SLTPushFront(pphead, x);//头插 } else { SLTNode* prev = *pphead; //遍历找到pos前一个节点 while (prev->next != pos) { prev = prev->next; } SLTNode* newnode = BuySListNode(x); //prev,newnode,pos三个节点链接 prev->next = newnode; newnode->next = pos; } }
9、在pos后插入x
在pos之前插入x，相对来所比较复杂。所以如果没有特殊要求，可以采用pos后插。所以我们在这提供pos后插接口。
代码实现：
void SLTInsertAfter(SLTNode* pos, SLTDateType x) { assert(pos); SLTNode* newnode = BuySListNode(x); //后插 newnode->next = pos->next; pos->next = newnode; }
10、删除pos位置的值
删除pos位置的值一样分两种情况：
①：如果pos为头节点，复用头删接口。
②：遍历找到pos前一个节点prev。然后将pos前一个节点和后一个节点链接起来，并释放pos即可。
代码实现：
void SLTErase(SLTNode** pphead, SLTNode* pos) { assert(pphead); assert(pos); if (*pphead == pos) { SLTPopFront(pphead); } else { SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; //free(pos); } }
11、删除pos位置之后的值
要删除pos位置之后的值，我们首先将pos和pos后两个节点指针链接起来，并释放pos后一个节点即可。（要判断pos是否为尾节点）
代码实现：
void SLTEraseAfter(SLTNode* pos) { assert(pos); //检查pos是否为尾节点 assert(pos->next); SLTNode* posNext = pos->next; pos->next = posNext->next; free(posNext); posNext = NULL; }
12、销毁
代码实现：
void SLTDestory(SLTNode** pphead) { assert(pphead); SLTNode* cur = *pphead; while (cur) { SLTNode* next = cur->next; free(cur); cur = next; } *pphead = NULL; }
四、所有代码展示
List.h:
#pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> typedef int SLTDateType; typedef struct SListNode { SLTDateType date; struct SListNode* next; }SLTNode; void SLTPrint(SLTNode* phead); SLTNode* BuySListNode(SLTDateType x); void SLTPushBack(SLTNode** pphead, SLTDateType x); void SLTPushFront(SLTNode** pphead, SLTDateType x); void SLTPopBack(SLTNode** pphead); void SLTPopFront(SLTNode** pphead); SLTNode* SLTFind(SLTNode* phead, SLTDateType x); //在pos之前插入x void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x); //在pos之后插入x void SLTInsertAfter(SLTNode* pos, SLTDateType x); //删除pos位置的值 void SLTErase(SLTNode** pphead, SLTNode* pos); //删除pos位置之后的值 void SLTEraseAfter(SLTNode* pos); //销毁 void SLTDestory(SLTNode** pphead)
List.h:
include "SList.h" void SLTPrint(SLTNode* phead) { SLTNode* cur = phead; while (cur) { printf("%d->", cur->date); cur = cur->next; } printf("NULL\n"); } SLTNode* BuySListNode(SLTDateType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL) { perror("malloc"); exit(-1); } newnode->date = x; newnode->next = NULL; return newnode; } void SLTPushBack(SLTNode** pphead, SLTDateType x) { assert(pphead); SLTNode* newnode = BuySListNode(x); if (*pphead == NULL) { *pphead = newnode; } else { SLTNode* tail = *pphead; while (tail->next) { tail = tail->next; } tail->next = newnode; } } void SLTPushFront(SLTNode** pphead, SLTDateType x) { assert(pphead); SLTNode* newnode = BuySListNode(x); newnode->next = *pphead; *pphead = newnode; } void SLTPopBack(SLTNode** pphead) { assert(pphead); //1.空 assert(*pphead); //2.一个节点 //3.多个节点 if ((*pphead)->next == NULL) { (*pphead)->next = NULL; } else { SLTNode* tail = *pphead; while (tail->next->next) { tail = tail->next; } free(tail->next); tail->next = NULL; } } void SLTPopFront(SLTNode** pphead) { assert(pphead); //空 assert(*pphead); //非空 SLTNode* newnode = (*pphead)->next; free(*pphead); *pphead = newnode; } SLTNode* SLTFind(SLTNode* phead, SLTDateType x) { SLTNode* cur = phead; while (cur) { if (cur->date == x) return cur; cur = cur->next; } return NULL; } void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x) { assert(pphead); assert(*pphead); if (*pphead == pos) { SLTPushFront(pphead, x); } else { SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } SLTNode* newnode = BuySListNode(x); prev->next = newnode; newnode->next = pos; } } void SLTInsertAfter(SLTNode* pos, SLTDateType x) { assert(pos); SLTNode* newnode = BuySListNode(x); newnode->next = pos->next; pos->next = newnode; } void SLTErase(SLTNode** pphead, SLTNode* pos) { assert(pphead); assert(pos); if (*pphead == pos) { SLTPopFront(pphead); } else { SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; //free(pos); } } void SLTEraseAfter(SLTNode* pos) { assert(pos); //检查pos是否为尾节点 assert(pos->next); SLTNode* posNext = pos->next; pos->next = posNext->next; free(posNext); posNext = NULL; } void SLTDestory(SLTNode** pphead) { assert(pphead); SLTNode* cur = *pphead; while (cur) { SLTNode* next = cur->next; free(cur); cur = next; } *pphead = NULL; }
