链表的一步步实现（需有一部分c语言基础）

（由于本人上课实在没学懂链表的具体实现步骤，于是写下这篇博客记录学习过程，有兴趣的新手也可以跟着学习

1.认识链表的结构&创建简单静态链表并输出数据

Q：什么是链表？

A：链表是由一系列节点组成，每个节点包含两个域，一个是数据域，用来保存数据，另外一个是指针域，保存下一个节点的地址，链表在内存是非连续的。简单来说，链表就是结构体变量与结构体变量通过指针连接在一起。

[注]：该图中一个大长方形表示为链表中的一个元素，即一个节点；一个大长方形由两个小长方形组成，分别表示节点的数据(图中黄色高亮)，和指向下一个节点的指针(图中红色高亮)。

Q：为什么要使用链表？
A：链表在指定位置插入和删除不像数组那样需要移动大量元素，只需要修改对应位置的指针即可。比如如果我要把一个元素b插入a[10]这个数组的第五位，那么从a[5]开始到a[9]，所有的元素都要向后移动一位，非常麻烦。而链表只需要修改原先第四位和第五位节点的指针变量。

但链表也有缺点（相比较数组）
1.因为地址随机，只能通过遍历来进行查找，查找效率低一些。
2.链表相对于数组来讲，多了指针域空间开销。

按内存存储方式分类，链表可分为静态链表和动态链表。静态链表即为长度固定，可能会造成一定程度上的内存浪费；而动态链表则通过指针实现动态分配内存，可以减少一部分内存的浪费。

按形式分类，链表可分为单向链表、双向链表、循环链表、单向循环列表、双向循环链表。

（图例很清楚故不过多解释）

此外，链表还分为带头与不带头两种。此处的”头“指的是头节点，以下是关于头结点的解释。
（1）数据结构中，在单链表的开始结点之前设立一个节点称之为头节点，头节点的数据域可以不存储任何信息，也可以存储链表的长度等附加信息，头节点的指针域存储指向第一个节点的指针（即第一个节点的存储位置）。
（2）作用：方便链表的操作，减少代码量，举个例子，要知道在链表中插入，删除一个元素是更改这个结点上一个结点的指针域的位置来实现的，那么怎么样来对第一个结点来进行这些操作，有，但是麻烦，不如引入一个头结点来的方便。总之，引入头结点就可以很少的考虑到一些特殊情况，减少代码量。

由于链表通过指针变量串联在一起，所以拿到链表的第一个节点就相当于拿到整个链表。但因为链表不连续，所以寻找某一个节点是一个略显麻烦的事情。

接下来，我们来尝试一步步敲出静态链表。首先，为了实现链表中一个节点包含两个域，我们定义一个结构体。

struct ListNode // 链表节点类型定义
{
    int data;              // 节点数据
    struct ListNode* next; // 指向下一个节点的指针
};

[注]：解释一下为什么此处next的类型为ListNode *，因为next的意义是指向下一个节点，而下一个节点的变量类型是我们定义的结构体ListNode，而next又为指针，所以应为ListNode *。

接下来定义一个函数，对每个节点进行初始化（也可以直接在主函数中进行）

void test()
{
    struct ListNode node1 = {1, NULL};// 定义四个节点
    struct ListNode node2 = {2, NULL};
    struct ListNode node3 = {3, NULL};
    struct ListNode node4 = {4, NULL};
    node1.next = &node2;// 连接节点
    node2.next = &node3;
    node3.next = &node4;
    //注意最后一个节点的next指针要置为NULL
    
    struct ListNode *pHead = &node1;// 链表头节点
}

Q：此时一个静态链表的最重要的结构已经创建完成了，如果我想要输出这个链表每一个节点存储的数据，应该如何实现呢？

A：通过遍历整个链表实现。

接下来我们实现遍历链表输出数据。如何遍历这个链表呢？因为节点之间通过指针连接，因此我们要访问节点，只能通过指针来实现。
于是我们先定义一个辅助指针变量，例如pCurrent，指向下一个节点。

pCurrent = pCurrent->next;

因为能够指向下一个节点，所以辅助指针变量类型应该是节点的指针，即ListNode*型。
[注]: ->是一个整体，它是用于指向结构体、C++中的class等含有子数据的指针用来取子数据。换种说法，如果我们在C语言中定义了一个结构体，然后申明一个指针指向这个结构体，那么我们要用指针取出结构体中的数据，就要用到“->”
具体可参考这篇CSDN博文C语言结构体--箭头运算符(“-＞”)和点运算符(“.”) 应用区分_结构体中.和箭头-CSDN博客

Q：遍历自然需要用循环进行实现，那么循环的条件是什么？
A：我们注意到，创建链表的时候，每个节点之间通过next指针连接，而最后一个节点的next指向NULL，因此，当pCurrent更新到最后时应为NULL，此时循环结束。

while (pCurrent != NULL)// 遍历链表
    {
        printf("%d ", pCurrent->data);// 输出当前节点数据
        // 指针移动到下一个元素的位置地址
        pCurrent = pCurrent->next;
    }

至此，几个关键的部分都已完成，我们整理一些，补充部分代码。以下为该部分完整的代码

#include <stdio.h>
struct ListNode // 链表节点类型定义
{
    int data;              // 节点数据
    struct ListNode *next; // 指向下一个节点的指针
};

void test()
{
    struct ListNode node1 = {1, NULL};// 定义四个节点
    struct ListNode node2 = {2, NULL};
    struct ListNode node3 = {3, NULL};
    struct ListNode node4 = {4, NULL};
    node1.next = &node2;// 连接节点
    node2.next = &node3;
    node3.next = &node4;
    //注意最后一个节点的next指针要置为NULL

    struct ListNode *pHead = &node1;// 链表头指针

    // 如何遍历链表

    // 先定义一个辅助指针变量
    struct ListNode *pCurrent = &pHead;// 辅助指针变量指向头指针
    while (pCurrent != NULL)// 遍历链表
    {
        printf("%d ", pCurrent->data);// 输出当前节点数据
        // 指针移动到下一个元素的位置地址
        pCurrent = pCurrent->next;
    }
}
int main()
{
    test();// 调用test函数
    return 0; // 程序结束
}