链表

1. 在链表中，数据的添加和删除都较为方便，就是访问比较耗费时间。

存储

1. 在链表中，数据一般都是分散存储于内存中的，无须存储在连续空间内。
2. 因为数据都是分散存储的，所以如果想要访问数据，只能从第1个数据开始，顺着指针的指向一一往下访问（这便是顺序访问）。

链表的时间复杂度

1. 访问：O (n)
2. 删除：O(1)
3. 添加：O(1)

循环链表

1. 通常用于保存数量固定的最新数据。

双向链表

1. 双向链表会增加存储空间。
2. 双向链表可以从后往前遍历数据。
3. 添加和删除数据时需要改变更多指针的指向。

链表的定义

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
}