链表
链表和数组相似，都是有序的列表，都是线性结构（有且仅有一个前驱，有且仅有一个后续）。
不同点在于：链表中，数据单位的名称叫做“结点”，而结点和结点的分布，在内存中可以是离散的。
这个“离散”是相对于数组的“连续”来说的。
数组在内存中最为关键的一个特征，我在之前介绍数组的文章里有介绍，它一般是对应一段位于自己上界和下界之间的、一段连续的内存空间。元素和元素之间，紧紧相连。
而链表中的结点，则允许散落在内存空间的各个角落里。一个内容为1->2->3->4->5的链表，在内存中的形态可以是散乱的：
由于数组中的元素是连续的，每个元素的内存地址可以根据其索引距离数组头部的距离来计算出来。
因此对数组来说，每一个元素都可以通过数组的索引下标直接定位。对链表来所，元素与元素之间似乎毫无内存上的瓜葛。
这种各据山头，我们又该如何遍历呢？
在链表中，每一个结点都包含了两部分内容：数据域和指针域。
JS中的链表，是以嵌套的对象的形式来实现的：
{ // 数据域
val: 1,
// 指针域，指向下一个结点
next: { val:2, next: ... }
}
数据域：存储的是当前结点所存储的数据值
指针域：代表下一个结点（后续结点）
把这个关系简化一下：
要想访问链表中的任何一个元素，我们都得从起点结点开始，逐个访问next，一直访问到目标结点为止。
为了确保起点结点是可抵达的，我们有时还会设定一个head指针（dummy结点）来专门指向链表的开始位置：
链表结点的创建：
function ListNode(val) {
this.val = val;
this.next = null;
}
在使用构造函数创建结点是，传入val（数据域），指定next（下一个链表结点）即可：
const node = new ListNode(1)
node.next = new ListNode(2)
// 这就创建了一个数据域为1，next结点数据域为2的链表1->2
链表的操作：
添加
在尾部添加，改变一个next指针就行。
在两个结点间插入一个结点（这也是链表基础中的一个关键考点）：
要想完成这个操作，我们需要变更的是前驱结点和目标结点的next指针指向。如图：
// 如果目标结点本来不存在，那么记得手动创建
const node3 = new ListNode(3)
// 把node3的 next 指针指向 node2（即 node1.next）
node3.next = node1.next
// 把node1的 next 指针指向 node3
node1.next = node3
删除
删除的标准：在链表的遍历过程中，无法再遍历到某个结点的存在。
按照这个标准，要想遍历不到 node3，我们直接让它的前驱结点 node1 的 next 指针跳过它、指向 node3 的后继即可：
node1.next = node3.next
在涉及链表删除操作的题目中，重点不是定位目标结点，而是定位目标结点的前驱结点。
做题时，完全可以只使用一个指针（引用），这个指针用来定位目标结点的前驱结点。比如说咱们这个题里，其实只要能拿到 node1 就行了：
// 利用 node1 可以定位到 node3
const target = node1.next
node1.next = target.next
高效的增删操作
在链表中，添加和删除操作的复杂度是固定的——不管链表里面的结点个数 n 有多大，只要我们明确了要插入/删除的目标位置，那么我们需要做的都仅仅是改变目标结点及其前驱/后继结点的指针指向。 因此我们说链表增删操作的复杂度是常数级别的复杂度，用大 O 表示法表示为 O(1)。
麻烦的访问操作
但是链表也有一个弊端：当我们试图读取某一个特定的链表结点时，必须遍历整个链表来查找它。
随着链表长度的增加，我们搜索的范围也会变大、遍历其中任意元素的时间成本自然随之提高。这个变化的趋势呈线性规律，用大 O 表示法表示为 O(n)。
但在数组中，我们直接访问索引、可以做到一步到位，这个操作的复杂度会被降级为常数级别(O(1))：
对数组还不清楚的可以看我的另外一篇对数组讲解的文章。
链表的插入/删除效率较高，而访问效率较低；数组的访问效率较高，而插入效率较低。
树
理解树结构
在理解计算机世界的树结构之前，大家不妨回忆一下现实世界中的树有什么特点：一棵树往往只有一个树根，向上生长后，却可以伸展出无数的树枝、树枝上会长出树叶。由树根从泥土中吸收水、无机盐等营养物质，源源不断地输送到树枝与树叶的那一端。一棵树往往呈现这样的基本形态：
数据结构中的树，首先是对现实世界中树的一层简化：
树根——>根节点
树枝——>边
树枝的两端——>结点
树叶——>叶子结点
树的关键特性和重点概念：
1.树的层次计算规则：根节点所在的那一层为第一层，其子结点所在的就是第二层，以此类推。
2.结点和树“高度”计算规则：叶子结点高度记为1，每往上一层高度就加1，逐层向上累加至目标结点时，所得到的值就是目标结点的高度。树中结点的最大高度，称为“树的高度”。
3.“度”的概念：一个结点开叉出去多少个子树，被称为结点的“度”。比如我们上图中，根节点的“度”就是3。
4."叶子结点"：叶子结点就是度为0的结点。
这里我们着重了解二叉树。
二叉树
满足二叉树的条件：
1.可以没有根节点，作为一棵空树存在
2.如果它不是空树，那么必须由根节点，左子树和右子树组成，且左右子树都是二叉树。
TIps：二叉树不能被简单定义为每个结点的度都是2的树。
普通的树并不会区分左子树和右子树，但在二叉树中，左右子树的位置是严格约定，不能交换的。
二叉树JS编码实现
在JS中，二叉树使用对象来定义。
1.数据域
2.左侧子结点的引用
3.右侧子结点的引用
在定义二叉树构造函数时，我们需要把左侧子结点和右侧子结点都预置为空：
// 二叉树结点的构造函数
function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
以这个结点为根结点，我们可以通过给 left/right 赋值拓展其子树信息，延展出一棵二叉树。因此从更加细化的角度来看，一棵二叉树的形态实际是这样的：
关于二叉树的遍历，由于内容较多，决定在下一篇文章里再做详细讲解。
以上均为阅读掘金小册的《前端算法与数据结构面试：底层逻辑解读与大厂真题训练》所获。富有的朋友们值得购买一读。
