目录

一，链表与数组

① 定义区别

② 实现区别

二，链表遍历和计算链表中节点数量

① 链表遍历

② 计算节点数量

三，查找链表节点

四，增加节点到链表中

① 在节点后方插入

② 在节点前方插入

● 在头节点前方插入

● 在其他节点前方插入

五，删除链表中指定的节点

① 删除链表头节点

② 删除链表其它节点

六，修改链表中指定的节点

七，动态创建链表

① 头插法创建链表

② 尾插法创建链表

---

一，链表与数组

① 定义区别

数组：数组是在内存中连续存储的具有相同类型的一组数据的集合

      ● 数组中数的类型必须相同；

      ● 数组中数在内存中必须是连续存储的

链表：把它想象成自行车链条，由n个节点组成，可以对这些节点进行“增，删，改，查”等操作，即对数据的操作。

      ● 可以进行动态存储分配；

      ● 可以在节点中定义多种数据类型；

      ● 用NULL来表示空节点；

      ● 链表都有一个头指针，一般以head来表示，存放的是一个地址；

      ● 链表中包含头结点和其它节点两种，头结点是没有数据域的；

      ● 链表中每个节点都分为两个区域，一个数据域，一个是指针域；

② 实现区别

数组：

#include <stdio.h>int main()
{int i;int arr[] = {1,2,3,4,5,6,7,8};int len = sizeof(arr)/sizeof(arr[0]);for(i=0;i<len;i++){printf("%d ",arr[i]);}putchar('\n');printf("number=%d\n",len);return 0;
}

dhw@dhw-virtual-machine:~$ ./a.out
1 2 3 4 5 6 7 8 
number=8

链表：

#include <stdio.h>struct Test{int data;struct Test *next;
};int main()
{struct Test t1 = {1,NULL};struct Test t2 = {2,NULL};struct Test t3 = {3,NULL};struct Test t4 = {4,NULL};t1.next = &t2; //t1节点的下一个节点为&t2，因为struct Test *next,所以要取地址t2.next = &t3; //t2节点的下一个节点为&t3t3.next = &t4; //t3节点的下一个节点为&t4printf("%d %d %d %d\n",t1.data,t1.next->data,t1.next->next->data,t1.next->next->next->data);//此处以结构体的方式打印，用来引入链表主题return 0;
}

dhw@dhw-virtual-machine:~$ ./a.out
1 2 3 4

二，链表遍历和计算链表中节点数量

① 链表遍历

struct Test *p = head;              //定义链表头while(p != NULL){           //如果链表头不为空printf("%d ",p->data);  //就先打印链头的值p = p->next;        //一直链接下一个数的值，不断打印，直到节点值为NULL就停止

#include <stdio.h>struct Test{int data;struct Test *next;
};void printLink(struct Test *head)
{struct Test *p = head;      //定义链表头while(p != NULL){           //如果链表头不为空printf("%d ",p->data);  //就先打印链头的值p = p->next;        //一直链接下一个数的值，不断打印，直到节点值为NULL就停止}putchar('\n');
}
int main()
{struct Test t1 = {1,NULL};struct Test t2 = {2,NULL};struct Test t3 = {3,NULL};struct Test t4 = {4,NULL};t1.next = &t2;t2.next = &t3;t3.next = &t4;printLink(&t1); //此处t1就是链头，要取链表头的地址return 0;
}

dhw@dhw-virtual-machine:~$ ./a.out
1 2 3 4

② 计算节点数量

int cnt = 0;  //接收链表数量       struct Test *p = head;while(p != NULL){  //如果链头不为空，那么cnt++直到链尾出现NULL就停止cnt++;    p = p->next;}return cnt; //返回值取cnt

#include <stdio.h>struct Test{int data;struct Test *next;
};void printLink(struct Test *head)
{struct Test *p = head;while(p != NULL){printf("%d ",p->data);   //遍历链表部分p = p->next;}putchar('\n');
}int numLinkList(struct Test *head)
{int cnt = 0;  //接收链表数量       struct Test *p = head;while(p != NULL){  //如果链头不为空，那么cnt++直到链尾出现NULL就停止cnt++;    p = p->next;}return cnt; //返回值取cnt
}
int main()
{int ret;struct Test t1 = {1,NULL};struct Test t2 = {2,NULL};struct Test t3 = {3,NULL};struct Test t4 = {4,NULL};t1.next = &t2;t2.next = &t3;t3.next = &t4;printLink(&t1); //遍历链表ret = numLinkList(&t1);  //t1为链头，该函数传参就传t1的地址printf("num = %d\n",ret);return 0;
}

dhw@dhw-virtual-machine:~$ ./a.out
1 2 3 4 
num = 4

三，查找链表节点

int searchLinklist(struct Test *head,int n)//定义n为要查找的节点
{struct Test *p = head;while(p != NULL){if(p->data == n){   //如果头节点就是我们要查找的节点return 1;   //那么返回值为1，表示找到}p = p->next;  //否者就继续往下一个节点查找，直到找到或者节点为空就停止}return 0;        //一直没找到就返回0；
}

#include <stdio.h>struct Test{int data;struct Test *next;
};void printLink(struct Test *head)
{struct Test *p = head;while(p != NULL){printf("%d ",p->data); //遍历链表部分p = p->next;}putchar('\n');
}int searchLinklist(struct Test *head,int n)
{struct Test *p = head;while(p != NULL){if(p->data == n){   //如果头节点就是我们要查找的节点return 1;   //那么返回值为1，表示找到}p = p->next;  //否者就继续往下一个节点查找，直到找到或者节点为空就停止}return 0;        //一直没找到就返回0；
}
int main()
{int ret;struct Test t1 = {1,NULL};struct Test t2 = {2,NULL};struct Test t3 = {3,NULL};struct Test t4 = {4,NULL};t1.next = &t2;t2.next = &t3;t3.next = &t4;printLink(&t1);//遍历链表ret = searchLinklist(&t1,3); //查找3这个节点if(ret == 1){    //如果返回值为1printf("have 3\n"); //就查找到3这个节点}else{printf("no 3\n");  //否者就没有3这个节点}ret = searchLinklist(&t1,7); //查找7这个节点if(ret == 1){printf("have 7\n");}else{printf("no 7\n");}return 0;
}

dhw@dhw-virtual-machine:~$ ./a.out
1 2 3 4   //遍历出来的链表节点
have 3    //查找到有3这个节点
no 7      //没有查找到7这个节点

四，增加节点到链表中

① 在节点后方插入

逻辑分析：

● 函数中需要定义新插入的节点new，和在哪个节点后插入n；

● 遍历链表，找到要插入的节点位置；while(p != NULL){p = p->next;}

● 如果链头就是要找的那个节点:p->data == n;

● 新节点的下一个=找的那个节点的下一个：new->next = p->next

● 找的那个节点的下一个节点就是新插入的节点：p->next = new; 

#include <stdio.h>struct Test{int data;struct Test *next;
};void printLink(struct Test *head)   //遍历链表部分
{struct Test *p = head;while(p != NULL){printf("%d ",p->data);p = p->next;}putchar('\n');
}void searchBehindLink(struct Test *head,struct Test *new,int n)
{                                    //new为新节点，n为要在哪个节点后插入节点struct Test *p = head;while(p != NULL){    //需要遍历步骤，找到要在那个节点后方插入节点      if(p->data == n){ //如果链头的值就是要找的那个节点new->next = p->next; //新节点的下一个=找的那个节点的下一个p->next = new; //找的那个节点的下一个就是新插入的节点}p = p->next;}
}
int main()
{int ret;struct Test t1 = {1,NULL};struct Test t2 = {2,NULL};struct Test t3 = {3,NULL};struct Test t4 = {4,NULL};struct Test new = {100,NULL}; //定义要插入的节点，插入的数是100t1.next = &t2;t2.next = &t3;t3.next = &t4;printLink(&t1);//遍历searchBehindLink(&t1,&new,3);//在节点3后面插入新节点100printLink(&t1);//插入新节点后在遍历一次，看是否插入成功return 0;
}

dhw@dhw-virtual-machine:~$ ./a.out
1 2 3 4         //原先的节点数
1 2 3 100 4     //插入成功，在3节点后方插入100

② 在节点前方插入

● 在头节点前方插入

如果在头结点插入新节点，那么头节点的地址就会发生改变，需要定义指针变量来接收新的头结点地址。

#include <stdio.h>struct Test{int data;struct Test *next;
};void printLink(struct Test *head) //遍历链表部分
{struct Test *p = head;while(p != NULL){printf("%d ",p->data);p = p->next;}putchar('\n');
}struct Test *searchFrontLink(struct Test *head,struct Test *new,int n)
{struct Test *p = head;if(p->data == n){  //链表头的前方插入new->next = p; //直接让新节点new->next等于现在的头就行了return new; //返回一个new}
}
int main()
{int ret;struct Test t1 = {1,NULL};struct Test t2 = {2,NULL};struct Test t3 = {3,NULL};struct Test t4 = {4,NULL};struct Test new = {102,NULL}; //插入102struct Test *head = NULL;t1.next = &t2;t2.next = &t3;t3.next = &t4;head = &t1;printLink(head);//遍历链表head = searchFrontLink(head,&new,1);//返回的是new，main函数中的头发生改变，重新用head来接收printLink(head);//添加完成，再次遍历链表，验证是否插入成功return 0;
}

dhw@dhw-virtual-machine:~$ ./a.out
1 2 3 4      //遍历链表
102 1 2 3 4  //在头节点前方插入新节点102，插入成功

● 在其他节点前方插入

struct Test *searchFrontLink(struct Test *head,struct Test *new,int n)
{struct Test *p = head;while(p->next != NULL){ //此时没有在链头的前方插入，所以要定义链头的下一个不为NULLif(p->next->data == n){   //链头的下一个节点就是我们要找的节点new->next = p->next; //插入进来的新节点就是头节点的下一个p->next = new; //头节点的下一个就是新节点return p; //此时要返回到头} p = p->next;}return p; //返回头节点
}

#include <stdio.h>struct Test{int data;struct Test *next;
};void printLink(struct Test *head)
{struct Test *p = head;while(p != NULL){printf("%d ",p->data);p = p->next;}putchar('\n');
}struct Test *searchFrontLink(struct Test *head,struct Test *new,int n)
{struct Test *p = head;while(p->next != NULL){ //此时没有在链头的前方插入，所以要定义链头的下一个不为NULLif(p->next->data == n){   //链头的下一个节点就是我们要找的节点new->next = p->next; //插入进来的新节点就是头节点的下一个p->next = new; //头节点的下一个就是新节点return p; //此时要返回到头} p = p->next;}return p; //返回头节点
}
int main()
{int ret;struct Test t1 = {1,NULL};struct Test t2 = {2,NULL};struct Test t3 = {3,NULL};struct Test t4 = {4,NULL};struct Test new = {102,NULL}; //插入新节点102struct Test *head = NULL;t1.next = &t2;t2.next = &t3;t3.next = &t4;head = &t1;printLink(head);searchFrontLink(head,&new,3); //插在节点3的前面printLink(head);return 0;
}

dhw@dhw-virtual-machine:~$ ./a.out
1 2 3 4 
1 2 102 3 4  //在节点3的前面插入新节点102

五，删除链表中指定的节点

删除节点后，内存中会存在残留的缓存数据，需要使用free()来释放地址空间，而free()一般是需要承接malloc()动态开辟了的地址空间。

① 删除链表头节点

逻辑分析：

● 删除的是头节点，所以不需要遍历；

● 确定头节点就是我们要删除的节点：p->data == n;

● 那么新的头节点就是原来头节点的下一个节点：head = head->next;

● 释放删除节点的内存空间：free()；

● 删除链头，链头地址发生改变，需要返回新的链头

#include <stdio.h>
#include <stdlib.h>struct Test{int data;struct Test *next;
};void printLink(struct Test *head)
{struct Test *p = head;while(p != NULL){printf("%d ",p->data);p = p->next;}putchar('\n');
}struct Test *deletLink(struct Test *head,int n)
{struct Test *p = head;if(p->data == n){  //如果头节点的值就是我们要删除的节点head = head->next; //那么新的头节点就是原来头节点的下一个节点free(p); //删除了节点就要释放删除节点的内存return head;//链头被删除，头发生了改变，就要返回新链头}
}
int main()
{int ret;struct Test t1 = {1,NULL};struct Test t2 = {2,NULL};struct Test t3 = {3,NULL};struct Test t4 = {4,NULL};struct Test *head = NULL;struct Test *p = (struct Test *)malloc(sizeof(struct Test));//动态开辟链头地址空间
//      t1.next = &t2;p->data = 1;//头节点里的值为1p->next = &t2;//头节点的下一个节点为t2t2.next = &t3;t3.next = &t4;//      head = &t1;head = p;printLink(head);head = deletLink(head,1);//头发生该表，需要新的链头来承接链表头printLink(head);return 0;
}

dhw@dhw-virtual-machine:~$ ./a.out
1 2 3 4 
2 3 4     //头结点1被删除

② 删除链表其它节点

逻辑分析：

● 遍历链表，遍历出要删除的其它节点;

● 因为不是删链头，所以循环遍历的条件为：p->next != NULL;

● 找到要删除的节点：p->next->data == n;

● 返回值为链头

#include <stdio.h>struct Test{int data;struct Test *next;
};void printLink(struct Test *head)
{struct Test *p = head;while(p != NULL){printf("%d ",p->data);p = p->next;}putchar('\n');
}struct Test *deletLink(struct Test *head,int n)
{struct Test *p = head;while(p->next != NULL){  //不是删除头节点，所以定义头节点的下一个节点不为NULLif(p->next->data == n){  //如果头节点的下一个节点就是我们要删除的节点p->next = p->next->next; //那么头节点的下一个就是头节点下一个的下一个return head;}p = p->next;}
}
int main()
{int ret;struct Test t1 = {1,NULL};struct Test t2 = {2,NULL};struct Test t3 = {3,NULL};struct Test t4 = {4,NULL};struct Test *head = NULL;t1.next = &t2;t2.next = &t3;t3.next = &t4;head = &t1;printLink(head);head = deletLink(head,2);printLink(head);return 0;
}

dhw@dhw-virtual-machine:~$ ./a.out
1 2 3 4 
1 3 4    //节点2被删除

六，修改链表中指定的节点

int changeLink(struct Test *head,struct Test *new,int n)
{struct Test *p = head;while(p != NULL){   //遍历if(p->data == n){ //如果头结点的data就是我们=要改变的节点np->data = new->data;//那么找到的节点数据就等于要改的数据return 1;//返回1，修改成功}p = p->next;//没有找到那个节点，就一直遍历到NULL节点停止}
}

#include <stdio.h>struct Test{int data;struct Test *next;
};void printLink(struct Test *head)
{struct Test *p = head;while(p != NULL){printf("%d ",p->data);p = p->next;}putchar('\n');
}int changeLink(struct Test *head,struct Test *new,int n)
{struct Test *p = head;while(p != NULL){   //遍历if(p->data == n){ //如果头结点的data就是我们=要改变的节点np->data = new->data;//那么找到的节点数据就等于要改的数据return 1;//返回1，修改成功}p = p->next;//没有找到那个节点，就一直遍历到NULL节点停止}
}
int main()
{struct Test t1 = {1,NULL};struct Test t2 = {2,NULL};struct Test t3 = {3,NULL};struct Test t4 = {4,NULL};struct Test *head = NULL;struct Test new = {9,NULL};//要改成的节点为9t1.next = &t2;t2.next = &t3;t3.next = &t4;head = &t1;printLink(head);changeLink(head,&new,3);//修改节点3为节点9printLink(head);return 0;
}

dhw@dhw-virtual-machine:~$ ./a.out
1 2 3 4 
1 2 9 4  //将节点3改为节点9，如果修改头节点也没有问题 

七，动态创建链表

① 头插法创建链表

每一次创建的新节点插入在上一个头节点之前，再让新创建的节点为链头

#include<stdio.h>
#include<stdlib.h>struct Test//声明结构体类型
{int data;//定义数据域struct Test *next;//定义指针域
};//遍历链表
void printLink(struct Test *head)
{struct Test *p = head;while(p != NULL){//p现在是链表头,会一直遍历链表尾NULL时停止printf("%d ",p->data);//输出p节点中data的值p = p->next;//使p指向下一节点}printf("\n");
}struct Test* insertFromHead(struct Test* head,struct Test* new)
{if(head == NULL){//判断链表是否为空head = new;//如果为空把创建的新节点当作链表头}else{new->next = head;//当链表不为空的时候，让新节点插在链表头的前面(称之为头插法)head = new;//再让新节点成为链表头}return head;
}//动态创建链表(头插法)
struct Test* creatLink(struct Test* head)
{struct Test* new;while(1){new = (struct Test*)malloc(sizeof(struct Test));//不断为新节点开辟空间new->next = NULL;printf("input your ne node data:\n");scanf("%d",&(new->data));//输入节点的数据域(data)if(new->data == 0){//判断每次输入的值是否为0，如果为0，停止创建并退出printf("quit!\n");return head;}head = insertFromHead(head,new);}return head;
}int main()
{struct Test* head = NULL;head = creatLink(head);printLink(head);return 0;
}

dhw@dhw-virtual-machine:~$ ./a.out
input your ne node data:
1
input your ne node data:
2
input your ne node data:
3
input your ne node data:
4
input your ne node data:
5
input your ne node data:
6
input your ne node data:
0     //输入0就退出程序
quit!
6 5 4 3 2 1  //从头插入，每一个新插入的节点都为链表头

② 尾插法创建链表

如果头节点为空，那么创建的第一个节点就当做链表头，后面每次创建的新节点都依次插在链表最后一个节点的后面

#include<stdio.h>
#include<stdlib.h>struct Test
{int data;//定义数据域struct Test *next;//定义指针域
};//遍历链表
void printLink(struct Test *head)
{struct Test *p = head;while(p != NULL){//p现在是链表头,会一直遍历链表尾NULL时停止printf("%d ",p->data);//输出p节点中data的值p = p->next;//使p指向下一节点}printf("\n");
}struct Test* insertBehind(struct Test* head,struct Test* new)
{struct Test* p = head;if(p == NULL){//判断链表是否为空return head = new;//如果为空把创建的新节点当作链表头}while(p->next != NULL){//遍历到最后一个节点p = p->next;//使p指向下一节点}p->next = new;//把新节点插入最后一个节点的指针域(next)中return head;//把链表头传回去
}//动态创建链表(尾插法)
struct Test* creatLink(struct Test* head)
{struct Test* new;while(1){new = (struct Test*)malloc(sizeof(struct Test));//开辟空间new->next = NULL;printf("input your ne node data:\n");scanf("%d",&(new->data));//输入节点的数据域(data)if(new->data == 0){//判断每次输入的值是否为0，如果为0，停止创建并退出printf("quit!\n");return head;//返回到头}head = insertBehind(head,new);}
}int main()
{struct Test* head = NULL;head = creatLink(head);printLink(head);}

dhw@dhw-virtual-machine:~$ ./a.out
input your ne node data:
1
input your ne node data:
2
input your ne node data:
3
input your ne node data:
4
input your ne node data:
5
input your ne node data:
6
input your ne node data:
0      //输入0就退出程序
quit!
1 2 3 4 5 6  //按创建节点的顺序，新节点依次往后排列