1、什么是链表？

链表是由一系列连接在一起的结点构成，其中的每个结点都是一个数据结构。

链表的结点通常是 动态分配、使用和删除 的，允许链表在程序运行时增大或缩小。如果需要将新信息添加到链表中，则程序只需分配另一个结点并将其插入到系列中。

2、链表的优点

对于数组：链表可以容易地扩大或缩小；

对于矢量：链表插入节点或删除的速度更快（要将值插入矢量的中间，需要将插入点之后的所有元素朝矢量的末尾移动一个位置，从而为新值腾出空间。同样，从矢量中删除一个值需要将删除点之后的所有元素都朝矢量的开始方向移动一个位置。而当一个结点插入链表或从链表中删除结点时，其他结点都不必移动。）

3、链表的结构

链表中的每个结点都包含一个或多个保存数据的成员，还有一个后继指针指向链表中的下一个结点。单个节点的组成示意图如下：

节点组成图

非空链表的 第一个结点称为链表的头 。要访问链表中的结点，需要有一个 指向链表头的指针 。从链表头开始，可以按照存储在每个结点中的后继指针访问链表中的其余节点。最后一个结点中的后继指针被设置为 nullptr 以指示链表的结束。 指向链表头的指针也可以把它看作是代表了整个链表。

链表结构图如下：

链表结构图

注意，上图的链表结点彼此非常接近，排列整齐。实际上，链表结点可能散布在内存的各个部分。

4、链表的C++表示

为了使用C++ 表示链表，需要有一个 表示链表中单个结点的数据类型 。这样一个数据类型不但需要包含 要存储的数据结构 ，还要有一个 指向另一个相同类型结点的指针 。

①声明以下数据类型来表示节点：

//声明结构体 ListNode是要存储在链表中的节点的类型
struct ListNode           
{

    //节点将要存储的类型为double的数据项 value是节点的数据部分
    double value;

    //next被声明为ListNode的指针，他是指向下一个节点的后继指针
    ListNode *next;
};

②定义一个初始为空的链表，方法是定义一个用作链表头的指针并将其初始化为 nullptr，示例如下：

ListNode *head = nullptr;

③创建一个链表，其中包含一个结点，存储值为 77.7，如下所示：

head = new ListNode; //分配新结点
head->value = 77.7; //存储值
head->next = nullptr; //表示链表的结尾

④创建一个新结点，在其中存储 777.7 的值，并将其作为链表中的第二个结点。可以使用第二个指针来指向新分配的结点（其中将存储 777.7 的值），示例如下：

ListNode *secondPtr = new ListNode;
secondPtr->value = 777.7;
secondPtr->next = nullptr; //第二个结点是链表的结尾(通过将其后继指针 secondPtr->next 设置为 nullptr，可以使第二个结点成为链表的结尾)
head->next = secondPtr; //第一个结点指向第二个(通过 head->next = secondPtr; 语句将链表头的后继指针改为指向第二个结点。)

创建一个简单的链表示例程序：

// This program illustrates the creation || of linked lists.
#include <iostream>
using namespace std;
struct ListNode
{
    double value;
    ListNode *next;
};

int main()
{
    ListNode *head = nullptr;

    // 创建第一个节点 存储77.7
    head = new ListNode;         // 配置新节点
    head->value = 77.7;          // 存储数据
    head->next = nullptr; 

    // 创建第二个节点存储 777.7
    ListNode *secondPtr = new ListNode;
    secondPtr->value = 777.7;
    secondPtr->next = nullptr; 
    head->next = secondPtr; 

    // 打印这个简单的链表
    cout << "First item is " << head->value << endl;
    cout << "Second item is " << head->next->value << endl;

    return 0;
}

程序输出结果为：
First item is 77.7
Second item is 777.7