线性数据结构：数组、受限数组（栈、队列）、线性表
1. 数组
数组定义
数组（Array）是有序的元素序列。属于线性结构（有且仅有一个前驱、有且仅有一个后继）。
数组特点
数组的关键在于在内存中的物理地址对应的是一段连续的内存。这意味着如果想要在任意位置删除/新增一个元素，那么该位置往后的所有元素，都需要往前挪/往后挪一个位置。假设数组的长度是 n，那么因增加/删除操作导致需要移动的元素数量，就会随着数组长度 n 的增大而增大，呈一个线性关系。所以说数组增加/删除操作对应的时间复杂度就是 O(n)。
在js中的数组比较特殊，如果我们在一个数组中只定义了一种类型的元素，比如：
const arr = [1,2,3,4]它是一个纯数字数组，那么对应的确实是连续内存。
但如果我们定义了不同类型的元素：const arr = ['haha', 1, {a:1}]它对应的就是一段非连续的内存。此时，JS 数组不再具有数组的特征，其底层使用哈希映射分配内存空间，是由对象链表来实现的。
谨记“JS 数组未必是真正的数组”
2. 栈和队列（操作受限的数组）
栈
栈是一种后进先出(LIFO，Last In First Out)的数据结构。——只用 pop 和 push 完成增删的“数组”
- 只允许从尾部添加元素
- 只允许从尾部取出元素
队列
队列（Queue）是一种先进先出（FIFO，First In First Out）的数据结构。——只用 push 和 shift 完成增删的“数组”。在栈元素出栈时，我们关心的是栈顶元素（数组的最后一个元素）；队列元素出队时，我们关心的则是队头元素（数组的第一个元素）。
3. 链表
链表和数组相似，线性结构（有且仅有一个前驱、有且仅有一个后继），不同点在于，链表中，数据单位的名称叫做“结点”，而结点和结点的分布，在内存中可以是离散的。
一个内容为1->2->3->4->5的链表，在内存中的形态可以是散乱如下的：
在链表中，每一个结点的结构都包括了两部分的内容：数据域和指针域。JS 中的链表，是以嵌套的对象的形式来实现的：
{
// 数据域
val: 1,
// 指针域，指向下一个结点
next: {
val:2,
next: ...
}
}
数据域存储的是当前结点所存储的数据值，而指针域则代表下一个结点（后继结点）的引用。
创建链表:
function ListNode(val) {
this.val = val;
this.next = null;
}
const node = new ListNode(1)
node.next = new ListNode(2)
链表元素的添加和删除操作，本质上都是在围绕 next 指针做文章，例如在节点1和节点2之间插入节点3：
// 如果目标结点本来不存在，那么记得手动创建
const node3 = new ListNode(3)
// 把node3的 next 指针指向 node2（即 node1.next）
node3.next = node1.next
// 把node1的 next 指针指向 node3
node1.next = node3
删除节点3：
node1.next = node3.next
在涉及链表删除操作的题目中，重点不是定位目标结点，而是定位目标结点的前驱结点。做题时，完全可以只使用一个指针（引用），这个指针用来定位目标结点的前驱结点。
总结：链表的插入/删除效率较高，而访问效率较低；数组的访问效率较高，而插入效率较低。