链表就是一个元素个数可以实时变大/变小的数组 链表就是被锁链链接起来的表。这里的表指的是一个一个的节点，节点内的一些内存可以用来存储数据；这里的锁链指的是链接各个表的方式，C语言中用指针来链接2块内存
链表是由若干个节点组成的，节点由有效数据和指针组成（节点结构完全类似），有效数据用来存储信息完成任务的，指针区域用于指向链表的下一个节点而构成链表
总结 链表本质上就是用来解决数组的大小不能动态扩展的问题，所以链表其实就是当数组用的。 链表就是用来存储数据的，链表用来存数据相对于数组来说有点就是灵活性，需要多少个动态分配多少个，不占用额外内存。
单链表的实现 定义的struct node只是一个机构体，本身没有变量生成，也不占用内存。结构体定义相当于为链表节点定义了一个模板，但是还没有一个节点，将来在实际创建链表时需要一个节点时用这个模板来赋值一个即可 链表的内存需求比较灵活，只能使用堆内存：malloc申请堆内存，大小为一个节点大小，清理申请到的堆内存，把申请到的堆内存当做一个新节点，填充新节点的有效数据和指定区域
#include<stdio.h> //构建一个链表的节点 struct node { int data; //有效数据 struct node *pnext; //指向下一个节点的指针 }; int main(void) { //定义头指针 struct node *header = NULL; //创建一个链表节点 struct node *p=(struct node*)(malloc(sizeof(struct node)); if(NULL==p) { printf("malloc error.\n"); return -1; } //清理申请到的堆内存 bzero(p,sizeof(struct ndoe)); //填充节点 p->data = 1; p->pnext = NULL; //下一个节点不知道是啥，所以暂时指向NULL （下一个节点的首地址） header = p; //p是第一个节点的首地址，p赋值给header 相当于将头指针和首地址链接起来 return 0 ; };头指针 header 只是一个指针，指向第一个节点的首地址，只占四个字节，头指针的类型是 struct node *
#include<stdio.h> #include<stdlib.h> #include<strings.h> //构建一个链表的节点 struct node { int data; //有效数据 struct node *pnext; //指向下一个节点的指针 }; int main(void) { //定义头指针 struct node *header = NULL; //创建一个链表节点` struct node *p1=(struct node*)(malloc(sizeof(struct node)); if(NULL==p1) { printf("malloc error.\n"); return -1; } //清理申请到的堆内存 bzero(p1,sizeof(struct ndoe)); //填充节点 p1->data = 2; p1->pnext = NULL; //下一个节点不知道是啥，所以暂时指向NULL （下一个节点的首地址） header = p1; //p是第一个节点的首地址，p赋值给header 相当于将头指针和首地址链接起来 //创建一个链表节点 struct node *p2=(struct node*)(malloc(sizeof(struct node)); if(NULL==p2) { printf("malloc error.\n"); return -1; } //清理申请到的堆内存 bzero(p2,sizeof(struct ndoe)); //填充节点 p2->data = 3; p2->pnext = NULL; //下一个节点不知道是啥，所以暂时指向NULL （下一个节点的首地址） p1->pnext = p2; //创建一个链表节点 struct node *p3=(struct node*)(malloc(sizeof(struct node)); if(NULL==p3) { printf("malloc error.\n"); return -1; } //清理申请到的堆内存 bzero(p3,sizeof(struct ndoe)); //填充节点 p3->data = 3; p2->pnext=p3; p3->pnext = NULL; return 0 ; };访问链表第一个节点的有效数据 printf(“node data %d\n”,header->data); //等同于 p1->data 访问链表第二个节点的有效数据 printf(“node data %d\n”,header->pnext->data); //headerp1 p1->pnext->p2 p2->data 访问链表第三个节点的有效数据 printf(“node data %d\n”,header->pnext->pnext->data); //headerp1 p1->pnext->p2 p2->pnext->p3 p3_data
只能通过头指针来访问链表里面的数据，不能直接用各自的指针，因为在程序中我们保存链表是不会保存各个节点的指针的。 前一个节点内部的pnext指针能帮助我们找到下一个节点 单链表算法之插入节点 将创建节点的代码封装成一个函数
简单理解版：
#include<stdio.h> #include<stdlib.h> #include<strings.h> //构建一个链表的节点 struct node { int data; //有效数据 struct node *pnext; //指向下一个节点的指针 }; //作用：创建一个链表节点 返回值：struct node * ,指针指向我们本函数新创建的一个节点的首地址 struct node *creat_node(int data) { struct node *p1=(struct node *)malloc(sizeof(struct node)); if(NULL=p1) { printf("error\n"); return NULL; } bzero(p1,sizeof(struct node)); p1->data=data; p1->pnext=NULL; return p1; } struct node *creat_node2(int data) { struct node *p2=(struct node*)malloc(sizeof(struct node)); if(NULL==p2) { printf("malloc error.\n"); return NULL; } bzero(p2,sizeof(struct ndoe)); //填充节点 p2->data = 2; p2->pnext = NULL; //下一个节点不知道是啥，所以暂时指向NULL （下一个节点的首地址） return p2; } struct node *creat_node3(int data) { struct node *p3=(struct node*)malloc(sizeof(struct node)); if(NULL==p3) { printf("malloc error.\n"); return NULL; } //清理申请到的堆内存 bzero(p3,sizeof(struct ndoe)); //填充节点 p3->data = data; p3->pnext = NULL; return p3; } int main(void) { //定义头指针 struct node *header = NULL; header = creat_node(1); //等同于 header=p1 header->pnext=creat_node2(2); header->pnext->pnext=creat_node3(3); return 0 ; }正常版
#include<stdio.h> #include<stdlib.h> #include<strings.h> //构建一个链表的节点 struct node { int data; //有效数据 struct node *pnext; //指向下一个节点的指针 }; struct node *creat_node(int data) { struct node *p=(struct node *)malloc(sizeof(struct node)); if(NULL=p) { printf("error\n"); return NULL; } bzero(p,sizeof(struct node)); p->data=data; p->pnext=NULL; return p; } int main(void) { struct node *header=NULL; header=creat_node(1); header->pnext=creat_node(2); header->pnext->pnext=creat_node(3); return 0; }在链表尾部插入新节点
#include<stdio.h> #include<stdlib.h> #include<strings.h> //构建一个链表的节点 struct node { int data; //有效数据 struct node *pnext; //指向下一个节点的指针 }; struct node *creat_node(int data) { struct node *p=(struct node *)malloc(sizeof(struct node)); if(NULL=p) { printf("error\n"); return NULL; } bzero(p,sizeof(struct node)); p->data=data; p->pnext=NULL; return p; } void insert_tail(struct node *ph,struct node *new) { //先找到链表中最后一个节点 struct node *p = ph; while (NULL !=p->pnext) { p=p->pnext; } //将最后一个插入尾部 p->pnext = new; } int main(void) { // struct node *header=NULL; struct node *header = creat_node(1); insert_tail(pHeader, create_node(2)); insert_tail(pHeader, create_node(3)); insert_tail(pHeader, create_node(4)); header=creat_node(2); header->pnext=creat_node(3); header->pnext->pnext=creat_node(4); return 0; }在链表头部插入新节点
#include<stdio.h> #include<stdlib.h> #include<strings.h> //构建一个链表的节点 struct node { int data; //有效数据 struct node *pnext; //指向下一个节点的指针 }; struct node *creat_node(int data) { struct node *p=(struct node *)malloc(sizeof(struct node)); if(NULL=p) { printf("error\n"); return NULL; } bzero(p,sizeof(struct node)); p->data=data; p->pnext=NULL; return p; } void insert_head(struct node *ph,struct node *new) { //新节点的pnext指向原来的第一个节点 new->pnext=ph->pnext; //头节点的next指向新节点地址 ph->pnext=new; //头节点的计数+1 ph->data +=1; } int main(void) { struct node *header = creat_node(0); insert_head(pHeader, create_node(1)); insert_head(pHeader, create_node(2)); insert_head(pHeader, create_node(3)); return 0; }