目录
零.前言
单链表在实际应用中有着非常大的作用，弥补了顺序表的不足，在空间存储，内存占用上有着巨大的优势。本文将介绍单链表的基本操作，文末有已经测试过的完整代码。
1.链表与顺序表
1.顺序表的缺陷和优点
优点
顺序表支持随机访问，有一些算法的结构需要进行随机访问，比如二分查找和优化的快速排序。这里的随机访问只可以同过下标来获得数据。
缺点
1.顺序表要求数据进行顺序存储，所以当插入或者删除数据的时候就需要挪动大量数据，代价过大。
2.当空间不够时，顺序表需要进行扩容，为了避免频繁扩容通常扩为原来的二倍，但扩容时并不知道还要存储多少数据，所以有可能造成空间的浪费。
2.链表的优缺点
优点
我们根据顺序表的缺陷设计出了链表。
1.按需申请空间，不使用就释放空间，不存在空间浪费。
2.插入删除时不需要移动数据。
缺点
1.每存储一个数据就需要存储一个指向下一个结构体的指针。
2.不支持随机访问。
2.链表的逻辑结构与物理结构
1.逻辑结构
逻辑结构是抽象出来的，方便我们理解的结构
左边是数据域，右边是指针域。
2.物理结构
物理结构是计算机中实际存储的结构
每一个结构体中除了存储数据之外，还存储了下一个结构体的地址。
3.单链表的基本操作
1.定义单链表节点
typedef struct SListNode {
DataType data;
struct SListNode* next;
}SLTNode;定义了一个结构体变量作为单链表的节点，包括数值data和指向下一个结构体的指针next两部分。
2.创建单链表节点
SLTNode* BuyListNode(DataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//为新节点开辟空间
assert(newnode);//判断返回的指针是否为空
newnode->data = x;
newnode->next = NULL;//将新节点进行赋值
return newnode;
}首先新建立一个节点newnode，并为其开辟空间，将其data值记为x，next值暂时记为NULL。
3.打印单链表
void print(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}//遍历整个链表，当cur为空的时候停止打印
printf("NULL\n");
}从头节点开始遍历，直到cur变成空，打印所有data值，最后加上最后一个节点指向的NULL。
4.销毁单链表
void SListDestroy(SLTNode** pphead)
{
SLTNode* cur = *pphead;
while (cur)
{
SLTNode* next = cur->next;
free(cur);//释放cur的空间
cur = next;//将cur置为它的下一个节点
}
pphead = NULL;
}还是从头结点开始，定义一个遍历链表的指针cur，每一次使cur=cur->next，同时需要定义一个next，因为我们每一次释放cur之后，还需要释放它的下一个节点，也就是cur->next，如果不用next事先接收cur->next的话，在cur释放之后就无法找到其下一个元素了。
在书写单链表的代码时，我们要注意一个原则，即找前不找后，因为后可以通过一次或者多次next修改，在用cur遍历的时候，只需要最后将cur置为第一个发生变化的元素即可。
4.尾删与尾插
1.尾插
void SListPushBack(SLTNode** pphead, DataType x)
{
assert(*pphead);
SLTNode* newnode= BuyListNode(x);
SLTNode* cur = *pphead;
while (cur->next)
{
cur = cur->next;
}//寻找最后一个节点
cur->next = newnode;
}尾插的前提是首先找到尾结点，我们依然要建立一个遍历链表的cur来寻找最后一个节点，然后再对其进行插入。注意我们需要传入的是指针的地址，虽然如果只传递指针的话，也可以修改链表的值，但如果链表中没有元素，即phead=NULL时，我们需要将phead置为新节点，此时如果直接赋值的话是无法完成的，所以尽量使用二级指针进行赋值。
2.尾删
void SListPopBack(SLTNode** pphead)
{
assert(*pphead);//判断是否有节点
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;//当只有一个节点时，将头指针赋值为NULL
}
else
{
SLTNode* cur = *pphead;
while (cur->next->next != NULL)
{
cur = cur->next;
}//寻找最先改变的节点，也就是倒数第二个节点，为了将其next值赋值为NULL
free(cur->next);
cur->next = NULL;
}
}尾删的思路同理，首先找到通过cur遍历找到最后一个元素，然后释放掉它，因为最后一个元素的next为NULL，而我们释放掉最后一个元素之后还需要把指向该元素的next置为空，所以我们需要拿到这个元素，当只使用一个遍历节点cur时，我们就希望cur最后遍历到倒数第二个节点的位置，从而修改其next指针。所以我们通过cur->next来找到最后的节点。
5.头删与头插
1.头插
void SListPushFront(SLTNode** pphead, DataType x)
{
SLTNode* newnode = BuyListNode(x);
newnode->next= *pphead;
*pphead = newnode;//修改头结点，因此需要使用到二级指针
}建立一个新结点使它的next指向原来的头结点，然后将头结点指针指向新节点即可。
2.头删
void SListPopFront(SLTNode** pphead)
{
assert(*pphead);
SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;//只要头结点发生了改变，就需要使用二级指针
}首先需要判断链表是否为空，若为空则程序异常退出，若不为空，首先用一个指针next保存头节点的下一个位置，然后再释放头结点，在书写链表的时候同时也要注意保存由于某一个元素发生改变而发生改变，且该元素发生改变后无法再找到的元素。
6.定向插入
1.在pos前插入
void SListInsertFront(SLTNode**pphead,SLTNode* pos, DataType x)
{
assert(pphead);
assert(pos);
if (*pphead == pos)
{
SListPushFront(pphead, x);//判断pos是否是第一个元素，如果是则变为头插
}
else
{
SLTNode*newnode=BuyListNode(x);
SLTNode* cur = *pphead;
while (cur->next != pos)
{
cur = cur->next;
}
cur->next = newnode;
newnode->next = pos;//在pos前插入newnode
}
}在pos前插入，秉持着找前不找后的原则，pos的前一个元素也发生了改变（->next）发生了改变，所以最终的cur要指向pos的前一个元素，使得cur->next指向新建立的节点，新节点的next指向pos。
2.在pos后插入
void SListInsertBack(SLTNode** pphead,SLTNode* pos,DataType x)
{
assert(pos);//判断pos是否为空
SLTNode* newnode = BuyListNode(x);
newnode->next = pos->next;
pos->next = newnode;//在pos后插入newnode
}在pos后插入，最先发生改变的是pos，而pos节点我们已经得到了，所以就不需要再进行遍历，直接将pos的next指向新建立的节点，新建立节点的next指向pos->next即可。
7.定向删除
1.删除pos
void SListErase(SLTNode** pphead, SLTNode* pos)
{
assert(pos);//pos不存在则报错
if (pos == *pphead)
{
SListPopFront(pphead);//如果pos是第一个节点则变为头删
}
else
{
SLTNode* cur = *pphead;
while (cur->next != pos)
{
cur = cur->next;
}
cur->next = pos->next;
free(pos);
}
}删除pos同样需要找到pos的前一个节点，即遍历之后将cur置为pos的前一个节点，使cur->next=pos->next然后再释放pos的空间。
2.删除pos后的结点
void SListEraseBack( SLTNode* pos)
{
assert(pos->next);//判断pos后的节点是否合法
SLTNode* next = pos->next;//记录pos后的节点的下一个节点，方便为pos的next赋值
pos->next = next->next;
free(next);
}此时不需要遍历因为第一个改变的节点（pos）我们已经拿到了直接将pos->next=pos->next->next即可，然后释放pos->next，由于pos节点已经被删除，所以在此之前我们需要新建立一个next节点来存储pos->next。
8.查找
SLTNode* SListFind(SLTNode* pphead, DataType x)
{
SLTNode* cur = pphead;
while (cur)
{
if (cur->data == x)
{
return cur;//找到返回该节点
}
cur = cur->next;
}
return NULL;//没找到返回空
}遍历所有节点，若找到则返回该节点，若没找到则返回NULL。
9.全部代码及测试结果
1.SList.h文件
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#define DataType int
typedef struct SListNode {
DataType data;
struct SListNode* next;
}SLTNode;
void print(SLTNode* phead);//打印
SLTNode* BuyListNode(DataType x);//建立链表节点
void SListDestroy(SLTNode** pphead);//销毁链表
void SListPushBack(SLTNode** pphead, DataType x);//尾插
void SListPopBack(SLTNode** pphead);//尾删
void SListPushFront(SLTNode** pphead, DataType x);//头插
void SListPopFront(SLTNode** pphead);//头删
void SListInsertFront(SLTNode**pphead,SLTNode* pos, DataType x);//固定前插
void SListInsertBack(SLTNode** pphead, SLTNode* pos, DataType x);//固定后插
void SListErase(SLTNode** pphead, SLTNode* pos);//定点删除
void SListEraseBack(SLTNode* pos);//删除定点后一个节点
SLTNode* SListFind(SLTNode* pphead, DataType x);//查找2.SList.c文件
#include "SList.h"
SLTNode* BuyListNode(DataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
assert(newnode);
newnode->data = x;
newnode->next = NULL;
return newnode;
}
void print(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
void SListDestroy(SLTNode** pphead)
{
SLTNode* cur = *pphead;
while (cur)
{
SLTNode* next = cur->next;
free(cur);
cur = next;
}
pphead = NULL;
}
void SListPushBack(SLTNode** pphead, DataType x)
{
assert(*pphead);
SLTNode* newnode= BuyListNode(x);
SLTNode* cur = *pphead;
while (cur->next)
{
cur = cur->next;
}
cur->next = newnode;
}
void SListPopBack(SLTNode** pphead)
{
assert(*pphead);
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* cur = *pphead;
while (cur->next->next != NULL)
{
cur = cur->next;
}
free(cur->next);
cur->next = NULL;
}
}
void SListPushFront(SLTNode** pphead, DataType x)
{
SLTNode* newnode = BuyListNode(x);
newnode->next= *pphead;
*pphead = newnode;
}
void SListPopFront(SLTNode** pphead)
{
assert(*pphead);
SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
void SListInsertFront(SLTNode**pphead,SLTNode* pos, DataType x)
{
assert(pphead);
assert(pos);
if (*pphead == pos)
{
SListPushFront(pphead, x);
}
else
{
SLTNode*newnode=BuyListNode(x);
SLTNode* cur = *pphead;
while (cur->next != pos)
{
cur = cur->next;
}
cur->next = newnode;
newnode->next = pos;
}
}
void SListInsertBack(SLTNode** pphead,SLTNode* pos,DataType x)
{
assert(pos);
SLTNode* newnode = BuyListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
void SListErase(SLTNode** pphead, SLTNode* pos)
{
assert(pos);
if (pos == *pphead)
{
SListPopFront(pphead);
}
else
{
SLTNode* cur = *pphead;
while (cur->next != pos)
{
cur = cur->next;
}
cur->next = pos->next;
free(pos);
}
}
void SListEraseBack( SLTNode* pos)
{
assert(pos->next);
SLTNode* next = pos->next;
pos->next = next->next;
free(next);
}
SLTNode* SListFind(SLTNode* pphead, DataType x)
{
SLTNode* cur = pphead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}3.test.c文件
#include"SList.h"
void menu()
{
printf("****1.打印链表****2.尾插****\n");
printf("****3.尾删********4.头插****\n");
printf("****5.头删********6.固定前插\n");
printf("****7.固定后插****8.固定删除\n");
printf("****9.固定后删****0.删除链表\n");
}
int main()
{
int input = 0;
SLTNode* phead = (SLTNode*)malloc(sizeof(SLTNode));
phead->data = 0;
phead->next = NULL;
SListPushBack(&phead, 1);
SListPushBack(&phead, 2);
SListPushBack(&phead, 3);
SListPushBack(&phead, 4);
SListPushBack(&phead, 5);
SListPushBack(&phead, 6);
print(phead);
do {
menu();
scanf("%d", &input);
int x;
int y;
SLTNode* pos;
switch (input)
{
case 1: print(phead);
break;
case 2:scanf("%d", &x);
SListPushBack(&phead, x);
print(phead);
break;
case 3:SListPopBack(&phead);
print(phead);
break;
case 4:scanf("%d", &x);
SListPushFront(&phead, x);
print(phead);
break;
case 5:SListPopFront(&phead);
print(phead);
break;
case 6:scanf("%d", &x);
scanf("%d", &y);
pos=SListFind(phead, x);
SListInsertFront(&phead, pos, y);
print(phead);
break;
case 7:scanf("%d", &x);
scanf("%d", &y);
pos = SListFind(phead, x);
SListInsertBack(&phead, pos, y);
print(phead);
break;
case 8:scanf("%d", &x);
pos = SListFind(phead, x);
SListErase(&phead, pos);
print(phead);
break;
case 9:
scanf("%d", &x);
pos = SListFind(phead, x);
if (pos == NULL)
{
printf("can't find!\n");
continue;
}
SListEraseBack(pos);
print(phead);
break;
case 0:SListDestroy(&phead);
break;
default:printf("wrong input!\n");
break;
}
} while (input);
return 0;
}4.测试结果
1.尾插：成功
2.尾删：尾删至没有元素报错，成功
3.头插：成功
4.头删：头删至没有元素报错，成功
5.定向头插：在第一个元素前头插以及在其他元素前头插，以及在不存在元素位置插入报错，成功
6.定向尾插：在其他元素插入，以及在不存在元素后插入报错，成功
7.固定删除：将链表删空报错，删除不存在元素报错，成功
8.固定后删：在最后一个元素后删报错，删除不存在元素报错，将链表删空报错，成功
9.查找：在定向中验证，成功
0.删除链表：成功
10.总结
书写单链表的代码时，我们要注意的点也恰恰是单链表的缺点，即无法通过下标来查找数据。所以单链表的大部分操作都需要进行遍历，在遍历的同时我们要找到最先变化的元素然后记录下来，在可以改变它的同时，可以根据它来寻找它之后的元素。在进行一些删除操作时，为了防止断链，也同样需要在删除前记录它的后一个元素的位置。我觉得再遍历和删除时，这两点原则是十分重要的。在很多OJ题中我们使用的大部分都是没有头节点的单链表，所以这里也没有写头节点，需要的可以自取呀，如果对你有帮助的话~别忘了点个关注或者赞啊~。