数组
说起链表结构的话，不得不提数组结构
先看一下数组的本质是什么
- 通过一段
连续分配的内存空间 元素在内存中呈线性连续排列 - 每个元素都可以存储
字节相同的数据(或地址) - 对象的话 存的是
内存地址此时地址指向的数据被称为卫星数据
数组这样规定有它的好处：
1 - 访问索引比较方便
| 内存地址 | 0xA000 | 0xA008 | 0xA010 | 0xA018 | 0xA020 | 0xA028 | 0xA030 | 0xA038 |
|---|---|---|---|---|---|---|---|---|
| 序数 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | ... |
| 其他数据 | 数据 1 | 数据 2 | 数据 3 | 数据 4 | 数据 5 | 数据 6 | ...预留区域 | 其他数据 |
- arr = 0xA000
- a[3] = 0xA000 + 3 * 8(字节) = 0xA018
可以看到 因为数组是连续排序的元素，所以可以很方便的通过下标/索引去访问到目标元素，时间复杂度仅为O(1)
2 - 追加元素也比较方便
因为数组在申请内存空间时， 会多预留一部分空闲区域，以便之后的各种操作。 所以在预留区域追加元素十分简单 时间复杂度也是O(1)有个问题就是， 如果预留区域小于追加元素的个数怎么办？ 其实也不难，根据大致的分配算法可以大致理解为
数组的元素为n， 预留区域是N， 其中 N = 2n。 如果要追加n+1个元素，对于前n个元素，每个追加的也是常数时间，仅在预留区域内正常追加即可。那么最后一个超过预留区域的元素的追加怎么办？为什么避免溢出内存大小，会将整个2n个元素拷贝到新的内存空间，再对最后一个元素在新的内存预留空间进行追加，那么时间复杂度也就是：
2n + (n+1) / n也就是 3n+1 / n大致等于 3所以它也是常数级的操作 比较简单
但对于数组的其他操作就较复杂
因为其他操作 都会影响到数组中的所有元素
| JS数组操作 | 时间复杂度 |
|---|---|
| push | O(1) |
| pop(删除最后一个元素并返回删除的元素) | O(1) |
| shift(删除第一个元素并返回删除的元素) | O(n) |
| unshift (在数组的首位添加一个元素) | O(n) |
| slice(截取) | O(n) |
| splice(从数组中添加/删除项目，然后返回被删除的项目) | O(n) |
| concat | O(n) |
| find | O(n) |
| filter | O(n) |
| every | O(n) |
所以在这个时候 就体现了链表的优势。
链表
- 通过一段
离散的内存空间 元素在内存中通过指针的形式也呈线性排列 - 因为有
指针在内存中可以离散的分配 头指针指向链表的第一个节点
链表和数组的一个最大不同就是链表在内存空间中的表现是离散的(当然也可以连续) 所以 链表的某些操作就不会影响到链表中的其他元素 从而可以减少操作的复杂度
单向链表
除了上述的链表特点外 单向链表还有自身的特点：
因为是单向 所有只有
一个方向链表节点包括
key和next 指针key可以是数据或卫星数据的地址next指针指向下一个链表节点尾指针指向null
实现单向链表：
