一文解决用C语言实现一个链表（全都是细节）_c语言实现链表

前言

链表是指数据使用一个一个的结点连接起来的数据结构，这样的数据结构中不像顺序表一样，顺序表中不同的数据在内存中的存储空间是相邻的，链表中的相邻结点在内存中的存储位置是没有任何关系的，每一个链表都是由许多的结点组成的，而一个链表，我们需要一个对应的头指针来管理这个链表，也就是说，如果我们拥有一个链表的头指针，那么我们就可以拿到这个链表中的所有的结点，在此基础上，如果我们还学会对链表中的结点进行一些常见的操作（增删查改），那么我们就可以熟练使用链表来解决现实中的问题了

单链表

1.链表中的结点

我们知道，链表是一种数据结构，那么所谓的数据结构就是用来存放数据的，因此，一个链表中的结点肯定需要一块空间来存储数据，再者，链表中不同的结点在内存中的存放位置是没有关系的，所以，我们需要想办法能够使相邻的链表结点之间能够建立一定的关系，那么这个就是通过指针来实现的。每一个链表的结点中，都会有一个数据域，和一个指针域，数据域就是用来存放数据的，指针域是用来存放逻辑上的下一个结点在内存中的存储地址。综上，一个结点需要解决的问题就是存放数据和记录下一个结点的地址，因此，需要一个**复杂的对象（结构体）**才能够解决这样的问题。为了方便表示结点中存放的数据的类型，通常我们会将存储的数据类型进行重定义，这样，在改变存放的数据类型的时候，就只需要改变这个重定义的位置就可以了，而不需要改变其他位置，相当于加入刚开始链表存储的数据类型是int类型，后面想存放的数据类型是double,那么我们只需要将代码中下面这行代码的int改成double即可，不需要改变其他位置的代码内容，代码实现如下：

• 重定义数据类型
  
• 结点类型（结构体）
  
• 在C语言中，要注意一个细节：类型是struct ListNode,而不是ListNode。为了每次使用struct ListNode这个类型的时候不用加上struct，我们通常会对这个类型进行重定义，如下：
  

上面这个代码还需要注意一个细节：typedef出来的ListNode是在这个typedef之后才能够使用的，因为代码只会向上进行查找，不会向下进行查找，就像前置声明一样：在使用定义在当前行下面的函数接口的时候，通常是会报错的，那么这种情况下我们需要在前面对定义在下面的函数接口进行前置声明，告诉编译器当前文件中已经定义该函数。

2.链表中的常见操作

对一个链表的常见操作包括：打印链表中的所有结点存储的值，对一个链表进行初始化，申请一个新节点，在链表的尾部进行插入，在链表尾部进行删除，在链表头部进行插入，在链表头部进行删除，销毁链表。

（1）相关声明格式

在上面的函数声明中，我们发现，在传参的时候，有些接口传的是ListNode* head（链表头指针的内容即对应结点的地址）,有些接口传的是ListNode** phead（头指针的地址，二级指针）。其实本质都是我们要对一个链表进行操作，所以需要将对应链表的头指针传给函数，对应的函数才能够拿到这个链表的所有结点，主要的区别在于这个接口中是否需要改变头指针的值，如果需要改变这个链表的头指针，那么就需要将头指针的地址传给函数接口，函数接口中才能够通过头指针的地址将头指针的值进行改变，如果传的是头指针的内容，那么在函数中的变量是形式参数，我们知道形式参数其实是实际参数的一份拷贝，也就是说对形式参数的改变是不会影响实际参数的值的，所以如果我们传的是ListNode* head,那么在函数接口中的head就是实际参数（链表头指针）的一份拷贝，我们在函数中对形式参数的改变不会影响实际参数的值的，下面我们一一分析上面各个函数中是否需要改变头指针的值的情况：

1. 打印链表
   打印链表本质就是遍历链表中的所有结点，从而访问每一个结点中存储的数据，显然并不需要改变链表头指针的值，因此在传参的时候，我们只需要传头指针的内容传给函数，找到这个链表，从而遍历这个链表的结点即可。
2. 初始化链表
   初始化链表的本质就是要将传入的链表头指针置成空指针，显然是需要改变头指针的，因此传的是链表头指针的地址
3. 链表尾插
   链表的尾插本质就是将新结点连接到链表最后一个结点之后，但是这里需要注意进行分类讨论，当插入第一个结点的时候（链表为空），显然刚开始的头指针是空指针，我们需要将第一个结点连接到头指针，因此需要改变头指针的值，当尾插的不是第一个结点（链表非空），那么就不需要改变头指针，只需要将新结点连接到链表最后一个结点的后面即可。综上，显然尾插过程中可能**需要改变头指针的值，**因此，尾插需要传头指针的地址
4. 链表尾删
   链表尾删的本质就是将链表中的最靠后的一个结点删除，但是尾删同样需要进行分类讨论，如果尾删的时候，链表只剩下一个结点，那么这个时候尾删是需要改变头指针的值的，如果尾删的时候，链表不是剩下一个结点，那么这个时候是不需要改变头指针的值的，因此在链表的尾删过程中同样存在改变头指针的值，所以需要传头指针的地址
5. 链表头插
   链表的头插本质就是将新节点连接到头指针和原来链表的第一个结点之间，从而新节点成为链表的第一个结点，原来链表中的第一个结点成为现在链表的第二个结点，显然在每次进行头插的时候都需要将链表的头指针修改成为新节点的地址，将头指针指向新节点，因此需要传头指针的地址
6. 链表头删
   链表头删的本质就是删除链表的第一个结点，显然每次都需要将链表的头指针指向原来链表第一个结点的下一个位置（可能为空，当头删前链表中只剩下一个结点的时候），所以每次都需要改变链表的头指针，因此需要传链表头指针的地址
7. 销毁链表
   销毁链表的本质就是将链表中的每一个结点释放之后，最后需要将链表的头指针置成空指针，显然需要改变链表头指针，所以传链表头指针的地址

（2）常见操作的实现（定义）

1. 打印链表（链表的遍历方法）
   打印链表本质就是要我们学习链表的遍历方法：使用一个cur指针从头开始记录每一个结点的地址，依次往后，直到空就结束，注意：循环判断条件中的cur本身是一个指针，当cur还在遍历链表中的结点的时候，此时cur指向的是链表中的结点，是有效的结点，此时cur不为空，循环条件为真，当cur遍历完链表时，cur会走到链表最后一个结点指向的NULL,此时cur就是空指针，循环判断条件为假，循环结束。
   

2. 初始化链表
   初始化链表本质就是将链表的头指针置成空指针即可，一般情况下可能不需要这个初始化函数，因为我们在定义链表的头指针的时候通常会习惯将头指针的值置成空指针，表示刚开始链表为空。
   

3. 申请一个新节点
   在对链表进行各种插入的时候通常都需要定义一个新节点，因此，为了避免代码冗余，我们可以将这个定义链表的行为重新封装成一个新函数，当需要使用定义新节点这个行为的时候就可以调用了，基本的思路就是使用malloc开辟空间，对结点中的内容进行处理
   

在使用malloc申请空间的时候需要注意以下问题：

• 申请的空间返回的地址是void*类型的，所以我们需要对其进行强转成我们自己想要的类型
• 返回的地址我们需要检查其是否是空指针，如果是空指针，则说明申请空间失败

5. 链表尾插
   
   链表的尾插中注意有插入第一个结点的特殊情况（链表为空），链表非空的时候，插入之前是需要找尾的，这里也需要重点学习如何找到链表中的尾结点，这个操作在OJ题中也是非常常见的。
6. 链表尾删
   
   注意：在链表的尾删中，需要进行分类讨论，分为三种情况：链表为空，链表只剩下一个结点，链表存在多个结点。当链表为空的时候，此时不需要进行删除了，直接return即可，当链表中只剩下一个结点时，此时需要将头指针的值置成空指针表示链表已经删除为空，当链表存在多个结点的时候，此时我们需要找的是倒数第二个结点，而不是最后一个结点，找倒数第二个结点和找倒数第一个结点的区别在于循环条件中的不同，找倒数第一个结点循环条件是while(cur->next);找倒数第二个结点的循环条件是while(cur->next->next);
7. 链表头插
   
   上面的代码是分布进行的，其实头插中上面两步是可以合并的，不管链表是否为空，都是同一个逻辑：先保存头指针指向的结点的地址，即头指针（原来链表中的第一个结点），再将头指针指向新节点，使新节点成为头插后的第一个结点，新节点再指向原先保存的头指针指向的内容，如果原来链表为空，则之前保存的就是空指针，那么此时新节点就是指向空指针，如果原来链表不为空，保存的就是头插后的第二个结点，也就是让新节点指向现在的第二个结点。
8. 链表头删

头删我们需要注意的是，一定要注意链表是否为空，如果链表为空，此时是不需要删除的，因为没有内容可以删除，如果链表不为空，要删除的是第一个结点，先保存第一个结点的下一个位置（可能为空，可能不为空），当我们保存了第一个结点的下一个位置之后，再删除第一个结点（地址保存在头指针），再让头指针指向原来链表的第一个结点的下一个位置，如果原来链表只剩下一个结点，也就是第一个结点的下一个位置是空指针，那么此时就是头指针指向空指针，此时链表就为空，也就是这个头删完成链表最后一个结点的删除。如果原来链表剩下多个结点，那么原先保存的第一个结点的下一个位置就不为空，也就是原来链表中的第二个结点，那么此时就是删除头指针指向的链表（第一个结点），再让头指针指向保存的第二个结点即可。
9. 销毁链表

销毁链表一定要注意需要先将链表中的每一个结点free之后，才free头指针，一定不能只free头指针，如果只free头指针，就会造成链表中的结点没有被释放，此时就会造成严重的内存泄露。所以正确的做法就是使用一个记录指针，记录遍历每一个结点，挨个删除释放，注意，在删除之前，一定要先保存删除结点的下一个结点，如果先删除不保存下一个结点的画，删除释放该结点之后，就找不到该结点的下一个结点了。
注意：在上面的代码中，phead保存的是链表头指针的地址，我们对phead进行断言，原因是下面我们需要通过phead进行解引用找到链表的头指针，因此，这个phead是一定不能为空的，如果为空，那么我们对其进行解引用就相当于对空指针进行解引用了，那么肯定就会导致程序崩溃

（5）测试

1. 测试初始化，尾插，打印链表
   
2. 测试初始化，尾插，尾删，打印链表
   
3. 测试初始化，头插，打印链表
   
4. 测试初始化，头插，头删，打印链表