说起链表结构的话，不得不提数组结构
先看一下数组的本质是什么
连续分配的内存空间 元素在内存中呈线性连续排列字节相同的数据(或地址)内存地址 此时地址指向的数据被称为卫星数据数组这样规定有它的好处：
1 - 访问索引比较方便
| 内存地址 | 0xA000 | 0xA008 | 0xA010 | 0xA018 | 0xA020 | 0xA028 | 0xA030 | 0xA038 |
|---|---|---|---|---|---|---|---|---|
| 序数 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | … |
| 其他数据 | 数据 1 | 数据 2 | 数据 3 | 数据 4 | 数据 5 | 数据 6 | …预留区域 | 其他数据 |
可以看到 因为数组是连续排序的元素，所以可以很方便的通过下标/索引去访问到目标元素，时间复杂度仅为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
实现单向链表：
[转载]原文链接：https://segmentfault.com/a/1190000021180217
本站文章除注明转载外，均为本站原创或编译。欢迎任何形式的转载，但请务必注明出处。
转载请注明：文章转载自 JavaScript中文网 [https://www.javascriptcn.com]
本文地址：https://www.javascriptcn.com/read-80317.html
文章标题：[JS数据结构]数组链表篇
微信公众号搜索： FedJavaScript ，选择关注，与十万前端开发者一起探讨前端学习
