链表（静态/动态创建，遍历，计数，查找，在节点的前/后方插入新节点，头插法，尾插法）
目录
一、前言
二、链表的静态创建和遍历
三、链表统计节点，查找节点是否存在
四、从指定节点的后方插入新节点
五、从指定节点的前方插入新节点
六、动态创建链表&尾插法
七、头插法
八、删除节点
一、前言
链表本质是一个结构体，结构体里不仅包含不同类型的数据，最重要的是定义了一个指向相同结构体类型的指针（必须是相同类型的结构体），通过这个指针我们就可以将一个又一个的结构体链接（指针存放下一个结构体的地址）起来，每一个结构体就是链表的其中一个节点。
掌握以上概念，只要结合代码，相信手撕链表也不是什么难事，无非就是指针和地址的一些操作罢了。
二、链表的静态创建和遍历
我们使用链表的时候可以和数组类比，但两者还是有区别，数组是内存中连续的空间；而链表不一定在内存中连续。
我们遍历数组时，要把数组的所有元素都打印出来，一个for循环就能搞定，而链表的遍历也类似
struct test
{int id;//存放节点的编号struct test *next;//链接下一个节点的地址
};/*静态创建链表*/
struct test n1 = {1,NULL};
struct test n2 = {2,NULL};
struct test n3 = {3,NULL};/*我们先手动建立链接,n3.next为空*/
n1.next = &n2;
n2.next = &n3;void printLink(struct test *head)
{while(head != NULL){printf("%d ",head->id);//打印每个节点的idhead = head->next;//把下个节点的地址给head，head从指向n1变成指向n2}
}
以上就是链表的最最基本的操作，看一下步骤： head指向n1，打印1；
head->next是n2的地址，head指向n2，打印2；
head->next是n3的地址，head指向n3，打印3；
head->next为NULL，不进入while，结束。
遍历的核心就是 head = head->next 这个操作。
三、链表统计节点，查找节点是否存在
统计节点就很简单了，看得懂遍历就会：
int getLinkNodeNum(struct test *head)
{int cnt = 0;while(head != NULL){cnt++;head = head->next;//关键}return cnt;
}查找节点，我这里演示代码实现的功能就只是检查是否存在该id的节点，原理也是遍历：
int searchLink(struct test *head, int data)//data传入你想要找的id
{while(head != NULL){if(head->id == data);return 1;//找到了直接退出该函数head = head->next;//遍历}return 0;//失败返回0
}四、从指定节点的后方插入新节点
在指定节点的后方插入，首先还是要遍历链表，那么函数要传入头节点的地址；还要传入指定节点的id；接着传入新节点的地址（因为我们这里还是使用静态创建的方法，每一个节点都要手动初始化）。来看代码：
int insertFromBehind(struct test *head, int data, struct test *new)
{while(head != NULL){if(head->id == data)//指定id{new->next = head->next;//让新节点的next指向指定节点的nexthead->next = new;//指定节点的next指向新节点，完成插入return 1;}head = head->next;//遍历}return 0;
}自己画图理解一下最好，你的next存的是谁的地址，就相当于你指向它，只要能理解这句话，链表的任何操作都不难。
五、从指定节点的前方插入新节点
从节点前方插入新节点，有可能是在头节点插入，而链表最重要的就是链表头的地址，那么函数的返回值就是结构体指针，需要返回头节点的地址（头节点可能会改变）
struct test* insertFromFront(struct test *head, int data, struct test *new)
{struct test *p = head;if(p->id == data)//表示想在头节点前面添加新节点{new->next = head;//新节点的next是原先的头节点return new;}while(p->next != NULL){/*如果当前遍历到的节点的下一个节点是我们要找的*/if(p->next->id == data){/*新节点的下一个节点是当前遍历到的节点的下一个节点*/new->next = p->next;/*当前遍历到的节点的下一个节点是新节点*/p->next = new;/*头节点不变，原样返回*/return head;}p = p->next;//遍历}printf("no this id\n");return head;
}从指定节点前方插入新节点分两种情况：
（1）从头节点前插入新节点：
直接让新节点的下一个节点为原先的头节点，返回新节点的地址。（一般一个链表的头节点head会定义成全局变量，如果头节点不知道，那就无从下手）
（2）除头节点外的其他节点前插入新节点：
遍历链表，假设我们要在节点3前插入，那么遍历到节点2时：node2->next->id=3，new-> = node2->next，运行到这里，新节点的下一个节点就是节点3，但这时节点2和新节点都指向节点3，把节点2指向新节点即可。思路清晰就很简单。
六、动态创建链表&尾插法
静态创建链表还要自己一个个定义，手动建立链接，非常麻烦，而且删除节点的时候，被删除的节点无法释放内存空间，可能会造成溢出等情况，所以要动态创建链表，之前静态创建是为了方便理解一些基础操作。
/*head全局变量*/
struct test *head = NULL;/*动态创建链表*/
struct test* createLink(struct test *head)
{struct test *new;struct test *p = head;while(1){/*给新节点分配内存空间*/new = (struct test*)malloc(sizeof(struct test));/*用户键盘输入新节点id*/scanf("%d",&(new->id));/*id为0结束创建,返回头节点地址*/if(new->id == 0){printf("0 quit\n");free(new);//释放最后建立的新节点的内存空间return head;}/*初始化新节点的next指针*/new->next = NULL;/*建立连接*/if(head == NULL)//如果头节点为NULL{/*创建头节点*/head = new;}else{// 遍历到最后一个节点p = head;while(p->next != NULL){p = p->next;}// 将新节点添加到最后p->next = new;}}
}使用malloc函数来为每一个新节点分配内存，如果输入的节点id为0代表结束创建，free函数释放最后建立的节点，并返回head头节点的地址。
七、头插法
struct test* insertFromHead(struct test *head)
{struct test *new;while(1){/*和尾插法一样*/new = (struct test*)malloc(sizeof(struct test));scanf("%d",&(new->id));if(new->id == 0){printf("0 quit\n");free(new);return head;} new->next = head;head = new;}return head;
}原本我在插入节点的时候判断了head是否为空，后来发现没必要，如果不为空，直接插在头节点前面，然后更新头节点即可；如果为空，那new就是尾巴节点，new->next为NULL，这也合理，然后更新头节点。
八、删除节点
struct test* deleteNode(struct test *head, int data)
{struct test *p = head;if(p->id == data){head = head->next;free(p);return head;}while(p->next != NULL){if(p->next->id == data){struct test *temp = p->next;/*关键操作*/p->next = p->next->next;free(temp);return head;}p = p->next;//遍历}return head;
}操作和从指定节点前方插入节点类似，判断当前p指向的节点的 next->id ，也就是下一个节点是否为要删除的节点，如果是：p->next->next 是要删除的节点的下一个，将它赋值给 p->next 就是跳过要删除的节点，要删除的节点的前一个节点指向要删除的节点的后一个节点。
至此链表的基础操作都讲完了，如果自己用画图的方式，跟着代码一步步走，手撕链表也不在话下，后面我会更新贪吃蛇小游戏，他的核心就是链表的操作，用来锻炼链表的使用能力。