对于顺序表我们发现，在此基础上仍存在了些许不足：
1.中间或头部的插入时间复杂度为O(n)，有点浪费时间。
2.增容需要申请空间，拷贝数据，释放空间，会有不小的消耗。
3.增容一般是呈2倍增容的，势必会造成空间浪费。
如何解决以上问题，我们又了解到了一种新的数据结构-“链表”
1.什么是链表。
链表顾名思义，由一条链子连接表中各成员。实则链表是由每一块独立的空间组成，每一个空间里存放着数据和一个指针，每一个指针指向下一块空间的地址，依次指向，我们可以想象成为用链条串联起类，故叫链表，链表是一种物理存储结构上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链次序实现的。
就像火车一样
我们一般将这一块空间称为一个节点，链表的末尾节点的指针是空指针。
2.链表的优点
相较于顺序表：
1.因为链表是由一块块空间构成，所以链表不存在容量不够要扩容的问题
2.根据需求申请释放空间
3.较好地解决了在头部或中间插入删除挪动数据的问题
3.单链表的实现
这里还是以存放整形数据为例：
1.单链表的结构体
如何来实现这样的结构呢？
typedef int SLdatatype; typedef struct seqlist { SLdatatype data; struct seqlist* next; }SLnode;
可以看到这里的结构体里存放了本结构体的指针，每一个结构体里都有一个自身的指针，而这个自身的指针就代表下一个结构体的首地址，依次下去，直至到末尾next尾空。
用单链表的话来说，就是每一个节点存放着指向下一个节点地址的指针，故此我们可以创建所需的节点个数存放数据，用指针连接起来。
2.节点的创建
SLnode* SLcreatnode(SLdatatype x) { SLnode* newnode = (SLnode*)malloc(sizeof(SLnode)); if (newnode == NULL) { perror("开辟错误\n"); } newnode->data = x; newnode->next = NULL; return newnode; }
每创建一个节点，就是在堆区申请一块空间用来存放数据，利用malloc开辟该结构体大小的空间，之后返回该节点，也就是这片空间。
3.参数的调用
这里强调下参数，因为我们需要改变链表，定义链表变量的时候是指针，函数的参数应设计为二级指针。
对于一个函数我们在其中定义的变量生命周期只在该作用域中，出了作用域就会被销毁，而有的函数需要去改变实参，只是简单的改变形参，是不会影响实参的，但若为实参的地址，我们可通过解引用形参来改变实参，比如：
int swap(int* x, int* y) { int tmp = *x; *x = *y; *y = tmp; } int main() { int x = 10; int y = 20; swap(&x, &y); printf("%d %d", x, y); return 0; }
因此，这里要想通过形参改变实参，参数设计为二级指针：这里以头插为例
4.头插
void SLpushfront(SLnode** p, SLdatatype x)//传参用二级指针 { SLnode* newnode = SLcreatnode(x); newnode->next = *p; *p = newnode; }
可以看到头插是先malloc一个节点赋值给newnode,之后在将该newnode 存放到目前的头节点的next中，然后赋值给头节点，即实现头部插入。
5.尾插
void SLpushback(SLnode** p, SLdatatype x)//尾插 { SLnode* newnode = SLcreatnode(x); //链表为空的话 if (*p == NULL) { *p = newnode; (*p)->data = x; } else { //找尾巴(前提：链表不为空) SLnode* tail = *p; while (tail ->next!= NULL) { tail = tail -> next; } tail->next = newnode; (*p)->data = x; } }
尾插需要我们找到最后一个节点，之后先改变末尾的next，（因为保证是连接的）然后再插入。
7.头删
void SLpopfront(SLnode** p)//头删 { assert(*p); if ((*p) ->next== NULL) { free(p); *p = NULL; } else { SLnode* top = *p; *p = (*p) -> next;//指向下一个 free(top); top = NULL; } }
头删需要分情况
8.尾删
void SLpopback1(SLnode** p)//尾删 { SLnode* pre = NULL; SLnode* tail = *p; while (tail->next != NULL) { pre = tail;//找到尾节点前一个 tail = tail->next; } free(tail);//释放最后的空间 pre->next = NULL;//同时前一个的next为空 }
或者
void SLpopback2(SLnode** p) { SLnode* tail = *p; while(tail->next->next)//找倒数第二个节点 { tail = tail->next; } free(tail->next);//释放 tail->next = NULL;//倒数第二个next置空 }
主要找到最后一个节点或者最后一个的前一个节点（这里的两种方法），在释放掉最后一个同时，前一个节点next为NULL。可以看到第二种直接释放掉前一个的next空间，即指向最后一个结点的空间，在置空。
8.在pos节点前插入x
void SLinsert(SLnode** p, SLnode* pos, SLdatatype x)//插在pos位置前 { SLnode* newnode = SLcreatnode(x); if (pos == *p) { SLpushfront(p, x); } SLnode* prev=*p; while (prev->next != pos) { prev = prev->next; } prev->next = newnode; newnode->next = pos; }
在这里需要注意在遍历找到pos位置前的一个节点时，我们都是prev->next==pos这样去寻找，但忽略了当头节点就是pos位置时的节点，故在开始我们还需要判断是否头节点等于pos节点，如何果实就直接调用头插
9.在pos节点前插入x
//pos节点后插 void SLinsertafter(SLnode** p, SLnode* pos, SLdatatype x) { SLnode* newnode = SLcreatnode(x); SLnode* prev = pos->next; pos->next = newnode; newnode->next = prev; }
10.删除pos位置节点
void SLerase(SLnode** p, SLnode* pos)//删除pos位置的节点 { SLnode* prev = *p; if (*p == pos) { SLpopfront(p); } else { while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); } }
