单链表的定义什么是单链表
单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。
单链表的各个数据元素在物理上可以是离散存放的，每个结点除了存放数据元素外，还要存储指向下一个节点的指针。而顺序表是连续存放的，每个结点中只存放数据元素。
单链表的优点：不要求大片连续空间，改变容量方便，只需在内存单元中随便找个位置作为新节点的区域；缺点：不可随机存储，要耗费一定空间存放指针。
顺序表的优点：可随机存储，存储密度高；缺点：要求大片连续空间，改变容量不方便，要在内存中再申请一片连续空间。
先理解并记住专业术语 ：
首节点：第一个有效节点。
尾节点：最后一个有效节点。
头节点：头节点的数据类型和首节点的类型一样，没有存放有效数据，最最前面的，是在首节点之前的，主要是为了方便对链表的操作（不理解的话，先记住）。
头指针：指向头节点的指针变量。
尾指针：指向尾节点的指针。
确定一个链表需要几个参数：（或者说如果期望一个函数对链表进行操作，我们至少需要接收链表的那些信息？？？）
只需要一个参数:头指针，因为通过它我们可以推出链表的所有信息。
用代码定义一个单链表
大概思路：由一个个节点组成一个单链表，所以从定义节点出发，来创建单链表。那节点里都有什么呢？每个节点里不光有存放的数据元素，还要有一个指向下一个节点的指针。这两个也称为数据域和指针域。为什么要有指针域呢？因为单链表的每个节点在物理上是离散存放的，有了一个节点后，那下一个节点就需要通过这个节点找到，这个节点的指针域可以理解为起着连接的作用。需要注意的是指针域的类型是我们此时定义的节点类型。之后为了方便写代码和区分，用typedef 起了节点和节点指针的别名。单链表的英文单词是LinkList，LNode是简写了单链表节点的英文单词 LinkNode。
1 typedef struct LNode{ //定义单链表结点类型 //这种方式代码可读性更强2 int data;//每个节点存放一个数据元素3 struct LNode *next;//指针指向下一个节点4 }LNode, *LinkList; //LNode 是struct LNode 的别名，LinkList是struct LNode *的别名，指针指向整个结构体
在后续代码中 ，使用LinkList，强调这是一个单链表； 使用LNode，强调这是一个节点。
1 void test()2 {3 LinkList L; // //声明一个指向单链表的指针,强调声明了一个单链表4 }初始化单链表
大概思路：在初始化的过程中，给单链表分配好一个头节点，让头节点的指向下一个节点的指针域指向空，因为在整个单链表中，此时还是空表，也就是没有有效节点，头节点虽然起着节点的名字，并且在写专业术语的时候说过，它只是为了便于操作，注意不要混淆了。
1 bool InitList(LinkList &L) //初始化一个单链表（带头结点） 2 { 3 L = (LNode *)malloc(sizeof(LNode)); //分配一个头节点，malloc函数强调返回是一个节点（LNode *)，如果单链表有头节点，则头指针指向头节点，即 LinkList L = (LNode *)malloc(sizeof(LNode)); 等号有指向作用 4 if(L == NULL) //内存不足，分配失败，就没有创建出单链表，因为已经分配了一个节点，所以只能内存不足的原因，空表是没有节点 5 return false; 6 L->next = NULL;//目前只有一个头节点，头节点之后暂时还没有节点 7 return true; 8 } 9 void test()10 {11 LinkList L; //声明一个指向单链表的指针12 InitList(L); //初始化一个空表13 // .......后续代码......14 }如果要判断带头节点的单链表是否为空，代码如下：
1 bool Empty(LinkList L) //判断单链表是否为空（带头节点） 头节点不存储数据，只有指针域，且表内没有有效节点2 {3 if(L->next == NULL)4 return true;5 else6 return false;7 }带头结点的单链表的插入操作
InsertList(&L,i,e)：插入操作。在表 L 中的第 i 个位置上插入指定元素 e，刚开始建议看b站的动画，再来理解代码 。
利用while循环找到第 i – 1 个结点，将新结点插入其后，头结点可以看作 “ 第0个” 结点。
1 bool InsertList(LinkList &L, int i, ElemType e) //在第 i 个位置插入元素 e （带头结点） 2 { 3 if(i < 1) //只能在头结点之后插入，头结点是第0个,之后是第1个 4 return false; 5 LNode *p; //LNode * 强调这是一个结点，声明一个结点，表示指针p指向当前找到的结点 6 p = L; //L是指向头结点的头指针，再把刚开始的指针p指向L，表示目前的指针p指向头结点 7 int j = 0;//记录当前p指向的是第几个结点，从头结点0开始 8 while(p!= NULL && j < i - 1) //循环找到第 i-1 个结点，j = i-1，不进入循环，内存满了，不进入循环 9 {10 p = p->next; //p指向下一个结点11 j++;12 }13 if(p==NULL) //i值不合法，如果有4个结点，那i不能等于6，因为 p = p->next,在第5个位置之后满了，p指向NULL，下一步p->next出错了，根本找不到表的某个位置14 return false;15 LNode *s = (LNode *)malloc(sizeof(LNode));//创建一个节点，这个节点的数据域就是e16 s->data = e;17 s->next = p->next; //自己画图理解，一开始p后的节点不是s，这里让p的下一个节点变成了在s的下一个节点18 p->next = s; //将结点s连到p之后19 return true; //插入成功20 }
带头结点的单链表的删除操作
DeleteList(&L,i,&e)：删除操作。删除表L中第 i 个位置的元素，并用e返回删除元素的值。
利用while循环找到第 i – 1 个结点，将其指针指向 第 i + 1个结点，并释放第 i 个结点。
1 bool DeleteList(LinkList &L, int i, ElemType &e) 2 { 3 if(i < 1) 4 return false; 5 LNode *p; 6 p = L; 7 int j = 0; 8 while(p != NULL && j < i - 1) //循环找第 i-1 个节点 9 {10 p = p->next;11 j++;12 }13 if(p == NULL) //i值不合法，导致第 i-1 个节点根本在表中找不到14 return false;15 if(p->next == NULL) //第 i-1 个节点能找到，但是刚好第 i-1 个节点之后已无其他节点（第i个结点和第i+1个节点没有了），那就没有办法把第 i-1 个节点的指向下一个节点的指针指向第 i+1 个节点16 return false;17 LNode *q = p->next; //p是第 i-1 个节点，p->next是之后的节点，也是第 i 个节点，令q指向被删除节点18 e = q->data; //用e返回元素的值19 p->next = q->next; //将*q 节点从链中断开，重新更改指针p的指向，指向第 i + 1个节点20 free(q); //释放节s点的存储空间21 return true;22 }带头结点的单链表的修改操作
UpdateList(&L, i, num)：修改操作，把第i个位置的数修改为num
1 int UpdateList(LinkList &L, int i, int num)//把第i个位置的数修改为num 2 { 3 if(i < 0)//有头节点，头节点是第0个节点，所以查找元素i不能小于0 4 return 0; 5 LNode *p; 6 int j = 0; 7 p = L; 8 while(p != NULL && j < i) //找的是第i个节点，插入那里找的是第i-1 个节点 9 { //如果i大于表的长度，那循环找到的p会指向NULL，不会进入循环体，最后返回NULL10 p = p->next;11 j++;12 }13 p->data = num;14 return p->data; 15 }带头结点的单链表的查找操作
GetList(L,i)：按位查找操作。获取表L中第 i 个位置的元素的值。
1 int GetList(LinkList L, int i)//按位查找，返回第 i 个元素（带头节点） 2 { 3 if(i < 0)//有头节点，头节点是第0个节点，所以查找元素i不能小于0 4 return NULL; 5 LNode *p; 6 int j = 0; 7 p = L; 8 while(p != NULL && j < i) //找的是第i个节点，插入那里找的是第i-1 个节点 9 { //如果i大于表的长度，那循环找到的p会指向NULL，不会进入循环体，最后返回NULL10 p = p->next;11 j++;12 }13 return p->data;14 } //平均时间复杂度为O(n)带头结点的单链表的销毁操作
利用while循环把头节点之后的有效节点free掉。
1 void Destroy(LinkList &L) 2 { 3 LNode *p; 4 while(L != NULL) 5 { 6 p = L; 7 L = L->next; 8 free(p); 9 }10 }完整的增删改查操作的代码，我自己一开始全写在main函数里，只能调用成功一个函数，我也不知道为啥，所以就用了switch选择结构来分别实现这些功能。这些代码理解了，就不难，建议多敲几遍！
1 #include 2 #include <malloc.h> 3 typedef struct LNode{ //定义单链表结点类型 //这种方式代码可读性更强 4 int data;//每个节点存放一个数据元素 5 struct LNode *next;//指针指向下一个节点 6 }LNode, *LinkList; //LNode 是struct LNode 的别名，LinkList是struct LNode *的别名，指针指向整个结构体 7 bool InitList(LinkList &L) //初始化一个单链表（带头结点） 8 { 9 L = (LNode *)malloc(sizeof(LNode)); //分配一个头节点，malloc函数强调返回是一个节点（LNode *)，如果单链表有头节点，则头指针指向头节点，即 LinkList L = (LNode *)malloc(sizeof(LNode)); 等号有指向作用 10 if(L == NULL) //内存不足，分配失败，就没有创建出单链表，因为已经分配了一个节点，所以只能内存不足的原因，空表是没有节点 11 return false; 12 L->next = NULL;//目前只有一个头节点，头节点之后暂时还没有节点 13 return true; 14 } 15 bool InsertList(LinkList &L, int i, int e) //在第 i 个位置插入元素 e （带头结点） 16 { 17 if(i < 1) //只能在头结点之后插入，头结点是第0个,之后是第1个 18 return false; 19 LNode *p; //LNode * 强调这是一个结点，声明一个结点，表示指针p指向当前找到的结点 20 p = L; //L是指向头结点的头指针，再把刚开始的指针p指向L，表示目前的指针p指向头结点 21 int j = 0;//记录当前p指向的是第几个结点，从头结点0开始 22 while(p!= NULL && j < i - 1) //循环找到第 i-1 个结点，j = i-1，不进入循环，内存满了，不进入循环 23 { 24 p = p->next; //p指向下一个结点 25 j++; 26 } 27 if(p==NULL) //i值不合法，如果有4个结点，那i不能等于6，因为 p = p->next,在第5个位置之后满了，p指向NULL，下一步p->next出错了，根本找不到表的某个位置 28 return false; 29 LNode *s = (LNode *)malloc(sizeof(LNode));//创建一个节点，这个节点的数据域就是e 30 s->data = e; 31 s->next = p->next; //自己画图理解，一开始p后的节点不是s，这里让p的下一个节点变成了在s的下一个节点 32 p->next = s; //将结点s连到p之后 33 return true; //插入成功 34 } 35 void ShowList(LinkList L) //显示 36 { 37 if(L->next == NULL) 38 printf("这是一个空表\n"); 39 while(L != NULL) 40 { 41 L = L->next; 42 printf("%d ",L->data); 43 } 44 45 } 46 bool DeleteList(LinkList &L, int i, int &e)//删除表L中第 i 个位置的元素，并用e返回删除元素的值。 47 { 48 if(i < 1) 49 return false; 50 LNode *p; 51 p = L; 52 int j = 0; 53 while(p != NULL && j < i - 1) //循环找第 i-1 个节点 54 { 55 p = p->next; 56 j++; 57 } 58 if(p == NULL) //i值不合法，导致第 i-1 个节点根本在表中找不到 59 return false; 60 if(p->next == NULL) //第 i-1 个节点能找到，但是刚好第 i-1 个节点之后已无其他节点（第i个结点和第i+1个节点没有了），那就没有办法把第 i-1 个节点的指向下一个节点的指针指向第 i+1 个节点 61 return false; 62 LNode *q = p->next; //p是第 i-1 个节点，p->next是之后的节点，也是第 i 个节点，令q指向被删除节点 63 e = q->data; //用e返回元素的值 64 p->next = q->next; //将*q 节点从链中断开，重新更改指针p的指向，指向第 i + 1个节点 65 free(q); //释放节s点的存储空间 66 return true; 67 } 68 int GetList(LinkList &L, int i)//按位查找，返回第 i 个元素（带头节点） 69 { 70 if(i < 0)//有头节点，头节点是第0个节点，所以查找元素i不能小于0 71 return 0; 72 LNode *p; 73 int j = 0; 74 p = L; 75 while(p != NULL && j < i) //找的是第i个节点，插入那里找的是第i-1 个节点 76 { //如果i大于表的长度，那循环找到的p会指向NULL，不会进入循环体，最后返回NULL 77 p = p->next; 78 j++; 79 } 80 return p->data; 81 } //平均时间复杂度为O(n) 82 int UpdateList(LinkList &L, int i, int num) 83 { 84 if(i < 0)//有头节点，头节点是第0个节点，所以查找元素i不能小于0 85 return 0; 86 LNode *p; 87 int j = 0; 88 p = L; 89 while(p != NULL && j < i) //找的是第i个节点，插入那里找的是第i-1 个节点 90 { //如果i大于表的长度，那循环找到的p会指向NULL，不会进入循环体，最后返回NULL 91 p = p->next; 92 j++; 93 } 94 p->data = num; 95 return p->data; 96 } 97 void Destroy(LinkList &L) //销毁单链表 98 { 99 LNode *p;100 while(L != NULL)101 {102 p = L;103 L = L->next;104 free(p);105 }106 }107 void ShowMenu()108 {109 printf("************************\n");110 printf("***** 1,添加数据 *****\n");111 printf("***** 2,删除数据 *****\n");112 printf("***** 3,查找数据 *****\n"); 113 printf("***** 4,修改数据 *****\n");114 printf("***** 5,显示数据 *****\n");115 printf("***** 0,销毁并退出 ***\n");116 }117 int main()118 {119 LinkList L;//声明一个单链表 120 InitList(L);//初始化函数调用 121 122 int select = 0; //创建选择输入的变量123 while (true)124 {125 //菜单调用126 ShowMenu();127 printf("请输入你的选择\n");128 scanf("%d", &select);129 switch (select)130 {131 case 1: //1,添加数据132 InsertList(L,1,1);133 InsertList(L,2,2); 134 InsertList(L,3,3);135 InsertList(L,4,4);136 InsertList(L,5,5);137 printf("数据添加成功！\n");138 getchar();139 break;140 case 2: //2,删除数据141 int e;142 if(DeleteList(L,4,e))143 {144 printf("删除的数是：%d\n",e);145 }146 getchar();147 break;148 case 3: //3,查找数据149 printf("查找的元素是：%d\n",GetList(L,1));150 getchar();151 break;152 case 4: //4,修改数据153 UpdateList(L,1,0);154 printf("修改成功！\n"); 155 getchar();156 break; 157 case 5: //4,显示数据158 printf("单链表的数据有："); 159 ShowList(L);160 getchar();161 break;162 case 0: //0,退出163 Destroy(L);164 printf("单链表已销毁！");165 printf("欢迎下次使用");166 return 0;167 break;168 169 default:170 break;171 }172 }173 return 0;174 } 运行结果如下：
在单链表中添加数据并显示数据成功：
在单链表中删除数据并显示数据成功：
在单链表中查找数据并显示数据成功：
在单链表中修改数据并显示数据成功：
