基本概念

定义：一种通过指针串联在一起的线性结构，由节点组成。
节点：包含数据域、指针域两部分。数据域用于存放数据，指针域用于存放指向下一个节点的指针，最后一个节点的指针域指向null。

链表的长度可以是不固定的，并且可以动态增删， 适合数据量不固定，频繁增删，较少查询的场景。

链表分类

根据节点的连接情况，链表可以分为单链表、双链表和循环链表。

单链表

单链表中的节点只能指向下一个节点，只能够顺序查找。
单链表的入口称为头结点，即head。

双链表

双链表中每个节点包含两个指针域，一个指向下一个节点，另一个指向上一个节点。
双链表中可以实现双向查找。

循环链表

循环链表中，头尾相连。

链表的存储方式

链表中的节点散乱的分布在内存中，其分布机制取决于操作系统的内存管理。

c++中链表的操作

链表的定义

以单链表为例，链表采用结构体的方式进行定义。

// 单链表
struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};

删除节点

需要删除链表某个节点时，只需要修改前一个节点的指针域即可。
注意，在c++中需要手动释放被删除链表的内存。

添加节点

与删除节点相同，只需要修改前一个节点的指针域，并将添加节点的指针域指向下一个节点即可

链表性能对比

链表与数组的性能对比如下。