[JS数据结构]数组链表篇
数组
说起链表结构的话,不得不提数组结构
先看一下数组的本质是什么
- 通过一段
连续分配
的内存空间 元素在内存中呈线性连续排列
- 每个元素都可以存储
字节相同
的数据(或地址) - 对象的话 存的是
内存地址
此时地址指向的数据被称为卫星数据
数组这样规定有它的好处:
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
实现单向链表:
[转载]原文链接:https://segmentfault.com/a/1190000021180217
本站文章除注明转载外,均为本站原创或编译。欢迎任何形式的转载,但请务必注明出处。
转载请注明:文章转载自 JavaScript中文网 [https://www.javascriptcn.com]
本文地址:https://www.javascriptcn.com/read-80317.html
文章标题:[JS数据结构]数组链表篇