当我们学完顺序表的时候，我们发现了好多问题如下：
- 中间/头部的插入删除，时间复杂度为O(N)
- 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
- 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们
再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。如何解决上面的问题呢？？今天就跟着小张一起学习单链表吧！！
链表的概念及结构
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
注意：1.链式结构在逻辑上是连续的，但是在物理上不一定连续
2.结点一般都是在堆上申请出来的（malloc）
3.从堆上申请的空间，是按照一定策略来分配的，两次申请的空间可能连续，也可能不连续
单链表
单链表的接口实现
void printdata(info* phead)//打印单链表 info* BuySListNode(int x)//创建新结点 void pushback(info** pphead, int x)//尾插 void pushFront(info** pphead, int x)//头插 void popFront(info** pphead)//头删 void popBack(info** pphead)//尾删 info* SListFind(info* pphead, int x)//单链表查找 SeqListInsert(info** pphead,info* pos,int x)//pos指针指向结点的地址的前一个位置前插插入 void SeqListErase(info** pphead, info* pos)//删除pos位置的值 void SListInsertAfter(info* pos, int x)//单链表在pos位置之后插入x void SListEraseAfter(info* pos)//删除pos的后一个位置
0.结构体定义单个结点
typedef struct info { int data;//data存数据 struct info* next;//info*next存放下一个结点的地址 }info;
1.创建新结点
info* BuySListNode(int x) { info* newnode = (info*)malloc(sizeof(info));//空间申请 assert(newnode);//断言，新结点是否申请到了 newnode->data = x;//数据赋值 newnode->next = NULL;//指向的地址赋值 return newnode;//将申请好的空间首地址返回回去 }
断言，如果没申请到空间，mallo返回空指针，断言newnode就会报错
为什么要用二级指针传参在尾插，头插，尾删，头删中
分析：
2.尾插
void pushback(info** pphead, int x)//尾插 { info* newnode = BuySListNode(x);//将创建好的新结点的地址保存在newnode变量中 if (*pphead == NULL)//链表无结点 { *pphead = newnode;// 将创建好的头节点的地址给给*pphead，作为新头节点的地址 } else { info* tail = *pphead;//定义一个指针，先指向头结点的地址 while (tail->next != NULL)//循环遍历找尾结点 { tail = tail->next;//指针指向下一个结点 } tail->next = newnode;//找到尾结点，将尾结点的next存放新接结点的地址 } }
分析：
文字解释：大体上就是直接将最后一个结点的next存入新结点的地址，然后将新结点的next存入空（NULL)。
申请新的结点，如果pphead为空地址，链表还没有结点，将新结点的地址传给pphead,新结点的地址就是头结点的地址，如果该链表中已经存在结点，定义一个指针先存放头节点的地址，然后遍历整个链表，循环寻找哪个结点的next为NULL，不是的话就将tail指向下一个结点，对应操作为tail = tail->next;结点的next为NULL，那个结点就是尾结点，找到尾结点之后将尾结点的next存入要插入新结点的地址，新结点的next已经在 BuySListNode(int x)置为空地址
3.打印链表
void printdata(info* phead) { info* cur = phead; while (cur != NULL) { printf("%d->", cur->data); cur = cur->next; } printf("NULL"); }
分析
文字描述：定义一个指针cur指向头结点，使用这个指针循环遍历，这个指针指向的不为空的话就继续循环，在循环中打印cur->data，对应的操作是printf(“%d->”, cur->data);打印%d后面加->是为了方便观察;然后将cur指针移动到下一个结点的位置对应操作是cur = cur->next;，继续打印。
4.头插
void pushFront(info** pphead, int x)//头插 { info* newnode = BuySListNode(x);//创建新结点，将新结点的地址存放在newnode指针变量中 newnode->next = *pphead;//新结点的下一个结点应该为旧头结点的地址 *pphead = newnode;//新头结点的地址更新为newnode指针所指向的地址 }
分析
文字描述：将创建的新结点的地址存放在newnode指针变量中，pphead为原先头结点的地址，头插一个新结点后，应该将新结点的next存放原先头结点的地址，对应操作为newnode->next = pphead;然后保存在pphead应该为新的头结点的地址，也就是newnode所指向的地址，对应操作为pphead = newnode;
5.头删
void popFront(info** pphead) { info* p =(*pphead)->next;//定义指针存放头结点的下一个结点的地址 free(*pphead);//释放头结点 *pphead = p;//头结点地址更新为原先头结点的下一个结点的地址 }
分析：
6.尾删
void popBack(info** pphead) { info* tailprev = NULL; info* tail = *pphead; if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else {while (tail->next != NULL) { tailprev = tail; tail = tail->next; } free(tail); tailprev->next = NULL; } }
分析：
7.修改
info* SListFind(info* pphead, int x) { info* cur = pphead;//cur指针保存pphead指针接收的地址 while (cur) { if (cur->data == x) { //cur->data==y可以将查找出来的值修改为y,不用单独写修改函数，传参也要多一个y return cur;//找到的话返回该结点的地址 } cur = cur->next;//cur指向下一个结点的地址 } return NULL; }
分析：
8.pos指针指向结点的地址的前一个位置前插插入（随便插）
SeqListInsert(info** pphead,info* pos,int x)//pos指针指向结点的地址的前一个位置前插插入 { assert(pphead);//头结点地址不能为空 if (pos == *pphead)//pos指针指向结点的地址为头结点，相当于头插 { pushFront(*pphead, x);//调用头插函数 } else { info* prev = *pphead;//定义一个prev指针，先让他保存头结点的地址 while (prev->next != pos)//循环遍历找pos指针指向结点的前一个结点 { prev = prev->next; } info* newnode=BuySListNode(x);//申请新结点，将申请好的结点地址存放在newnode指针变量里面 prev->next = newnode;//使之前pos指针指向的结点的前一个结点的next存入插入新结点的地址， newnode->next = pos;//然后新结点的next存入pos指向结点的地址 } }
分析：
9.删除pos位置的值
void SeqListErase(info** pphead, info* pos) { if (pos == *pphead)//删除结点是否为头结点 { popFront(*pphead);//头删 } else { info* prev = *pphead;//定义一个prev指针，先让他存放头结点的地址 while (prev->next != pos)//循环遍历寻找哪个结点的next存放的是pos指针指向的结点的地址 { prev = prev->next;//prev指针指向下一个结点 } prev->next = pos->next;//pos指针指向的结点的上一个结点的next存放pos指针指向的结点的下一个结点的地址 free(pos);//释放掉pos指针指向的那块空间 } }
分析：
10.单链表在pos位置之后插入x
void SListInsertAfter(info* pos, int x) { assert(pos);//防止在空指针 info* newnode=BuySListNode(x);//申请新结点 newnode->next = pos->next; pos->next = newnode; }
分析：
那么1，2是否可以反过来
pos->next = newnode; newnode->next = pos->next;
不行，d3的地址会丢失
出现下图的情况：
11.删除pos的后一个位置
void SListEraseAfter(info* pos) { assert(pos);//防止pos指向空地址 if (pos->next == NULL)//如果pos指针指向最后一个结点 return;//直接退出，不往下执行 info* del = pos->next;//保存pos指针指向结点的下一个结点的地址 pos->next = del->next;//更新pos指针指向的结点的下一个结点为pos指针指向结点下下一个结点的地址 free(del);//释放掉保存pos指针指向结点的下一个结点的地址的空间。 }
分析：
12.完整源码
#include<stdio.h> #include <stdlib.h> #include <assert.h> typedef struct info { int data; struct info* next; }info; void printdata(info* phead) { info* cur = phead; while (cur != NULL) { printf("%d->", cur->data); cur = cur->next; } printf("NULL"); } info* BuySListNode(int x) { info* newnode = (info*)malloc(sizeof(info)); assert(newnode); newnode->data = x; newnode->next = NULL; return newnode; } void pushback(info** pphead, int x)//尾插 { info* newnode = BuySListNode(x); if (*pphead == NULL) { *pphead = newnode; } else { info* tail = *pphead; while (tail->next != NULL) { tail = tail->next; } tail->next = newnode; } } void pushFront(info** pphead, int x)//头插 { info* newnode = BuySListNode(x); newnode->next = *pphead; *pphead = newnode; } void popFront(info** pphead)//头删 { info* p =(*pphead)->next; free(*pphead); *pphead = p; } void popBack(info** pphead)//尾删 { info* tailprev = NULL; info* tail = *pphead; if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { while (tail->next != NULL) { tailprev = tail; tail = tail->next; } free(tail); tailprev->next = NULL; } } info* SListFind(info* pphead, int x)//查找 { info* cur = pphead; while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } SeqListInsert(info** pphead,info* pos,int x)//pos指针指向结点的地址的前一个位置前插插入 { assert(*pphead); if (pos == *pphead) { pushFront(*pphead, x); } else { info* prev = *pphead; while (prev->next != pos) { prev = prev->next; } info* newnode=BuySListNode(x); prev->next = newnode; newnode->next = pos; } } void SeqListErase(info** pphead, info* pos) { if (pos == *pphead) { popFront(*pphead); } else { info* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); } } void SListInsertAfter(info* pos, int x) { assert(pos); info* newnode=BuySListNode(x); newnode->next = pos->next; pos->next = newnode; } void SListEraseAfter(info* pos) { assert(pos); if (pos->next == NULL) return; info* del = pos->next; pos->next = del->next; free(del); } int main() { info* n1 = (info*)malloc(sizeof(info)); info* n2 = (info*)malloc(sizeof(info)); info* n3 = (info*)malloc(sizeof(info)); info* n4 = (info*)malloc(sizeof(info)); assert(n1 && n2 && n3 && n4); n1->data = 1; n2->data = 2; n3->data = 3; n4->data = 4; n1->next = n2; n2->next = n3; n3->next = n4; n4->next = NULL; printf("原链表:"); printdata(n1); printf("\n"); printf("尾插:"); pushback(&n1, 5); pushback(&n1, 6); pushback(&n1, 7); pushback(&n1, 8); printdata(n1); printf("\n"); printf("头插:"); pushFront(&n1, 10); pushFront(&n1, 20); printdata(n1); printf("\n"); printf("头删:"); popFront(&n1); printdata(n1); printf("\n"); printf("尾删:"); popBack(&n1); popBack(&n1); printdata(n1); printf("\n"); printf("查找到并修改:"); SListFind(n1, 3)->data = 80; printdata(n1); printf("\n"); printf("pos指针指向结点的地址的前一个位置前插插入:"); SeqListInsert(&n1, n4, 100); printdata(n1); printf("\n"); printf("删除pos位置的值:"); SeqListErase(&n1, n4); printdata(n1); printf("\n"); printf("单链表在pos位置之后插入x:"); SListInsertAfter(n2, 1000); printdata(n1); printf("\n"); printf("删除pos的后一个位置:"); SListEraseAfter(n1); printdata(n1); printf("\n"); }
