链表 认识链表
//这是定义一个链表的方法
function ListNode(x) {
this.val = x; // 数据
this.next = null; // 指针
}
// 创建新的节点
// 首节点 head；尾节点 tail - 空指针
let head = ListNode(1);
let node2 = ListNode(2);
let tail = ListNode(3);
node1.next = node2;
node2.next = tail;
链表是数据结构之一，其中的数据呈线性排列。在链表中，数据的添加和删除都较为方便，就是访问比较耗费时间
如上图，Blue、Yellow、Red 这 3 个字符串作为数据被存储于链表中，也就是数据域，每个数据都有 1 个指针，即指针域，它指向下一个数据的内存地址，其中 Red 是最后 1 个数据，Red 的指针不指向任何位置，也就是为 NULL，指向 NULL 的指针通常被称为空指针。
- 特点1：在链表中，数据一般都是分散存储于内存中的，无须存储在连续空间内
- 特点2：查找方式：顺序访问，因为数据都是分散存储的，所以如果想要访问数据，只能从第 1 个数据开始，顺着指针的指向一一往下访问
比如，想要找到 Red 这一数据，就得从 Blue 开始访问，这之后，还要经过 Yellow，我们才能找到 Red。
-
特点3：添加/删除非常方便，只需要改变添加位置前后的指针指向就可以，非常简单。
那么对链表的操作所需的运行时间到底是多少呢？
- 我们把链表中的数据量记成 n。访问数据时，我们需要从链表头部开始查找（线性查找），如果目标数据在链表最后的话，需要的时间就是 O（n）。
- 另外，添加数据只需要更改两个指针的指向，所以耗费的时间与 n 无关。如果已经到达了添加数据的位置，那么添加操作只需花费 O（1）的时间，删除数据同样也只需 O（1）的时间。
链表还有一些特殊情况，譬如：
链表的 tail 指向 head 就形成了环形链表；
链表的每一项保存两个指针，分别用于指向前后两个节点，就形成了双向链表；