[JS数据结构]数组链表篇

2019-12-03 admin
数组

说起链表结构的话,不得不提数组结构

先看一下数组的本质是什么

  • 通过一段连续分配的内存空间 元素在内存中呈线性连续排列
  • 每个元素都可以存储字节相同的数据(或地址)
  • 对象的话 存的是内存地址 此时地址指向的数据被称为卫星数据

数组这样规定有它的好处:

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)

所以在这个时候 就体现了链表的优势。

链表
  • 通过一段离散的内存空间 元素在内存中通过指针的形式也呈线性排列
  • 因为有指针 在内存中可以离散的分配
  • 头指针 指向链表的第一个节点

链表和数组的一个最大不同就是链表在内存空间中的表现是离散的(当然也可以连续) 所以 链表的某些操作就不会影响到链表中的其他元素 从而可以减少操作的复杂度

单向链表

除了上述的链表特点外 单向链表还有自身的特点:

  • 因为是单向 所有只有一个方向

  • 链表节点包括 keynext 指针

    key 可以是数据或卫星数据的地址 next 指针指向下一个链表节点

  • 尾指针 指向null

实现单向链表:

[转载]原文链接:https://segmentfault.com/a/1190000021180217

本站文章除注明转载外,均为本站原创或编译。欢迎任何形式的转载,但请务必注明出处。

转载请注明:文章转载自 JavaScript中文网 [https://www.javascriptcn.com]

本文地址:https://www.javascriptcn.com/read-80317.html

文章标题:[JS数据结构]数组链表篇

相关文章
Vue.js组件tab实现选项卡切换
本文实例为大家分享了vue插件tab选项卡的具体代码,供大家参考,具体内容如下 效果图: 代码如下: <!DOCTYPE html> <html lang="en"> <head> ...
2017-03-13
React.js编程思想
JavaScript框架层出不穷,在很多程序员看来,React.js是创建大型、快速的Web应用的最好方式。这一款由Facebook出品的JS框架,无论是在Facebook还是在Instagram中,它的表现都非常出色。 使用React.j...
2015-11-12
从2014年的发展来展望JS的未来将会如何
<font face="寰�杞�闆呴粦, Arial, sans-serif ">2014骞达紝杞�浠惰�屼笟鍙戝睍杩呴€燂紝鍚勭�嶈��瑷€灞傚嚭涓嶇┓锛屼互婊¤冻鐢ㄦ埛涓嶆柇鍙樺寲鐨勯渶姹傘€傝繖浜涜��...
2015-11-12
three.js实现围绕某物体旋转
话不多说,请看代码: 可以拖动右上角观察变化 <!DOCTYPE html> <html lang="en" style="width: 100%; height:100%;"&gt...
2017-02-17
JS中的语音合成——Speech Synthesis API
JS中的语音合成——Speech Synthesis API 简介 HTML5中和Web Speech相关的API实际上有两类,一类是“语音识别(Speech Recognition)”,另外一个就是“语音合成(Speech Synthes...
2018-05-17
JavaScript教程:JS中的原型
Keith Peters 几年前发表的一篇博文,关于学习没有“new”的世界,其中解释了使用原型继承代替构造函数。两者都是纯粹的原型编码。 标准方法(The Standard Way) 一直以来,我们学习的在 JavaScript 里创建对...
2015-11-12
NodeJS参考手册pdf版
下载地址:Nodejs参考手册PDF版下载 ...
2015-11-12
使用axios发送post请求,body传送数据格式form和json区别
先来看看这两个种传送格式的写法 1.form格式,将Content-Type类型设置为application/x-www-form-urlencode,POST请求时将data序列化,提交的数据会按照 key1=val1&key2=...
2018-07-25
使用jspdf生成pdf报表
由于前台html已经动态生成报表,而且,前台有一个功能,一个date range组件,当你拖动的时候,报表会在不提交到后台的情况下动态变化。 因此需要用到js生成生报表: 用到的组件: jquery.js jspdf.js canvg.js...
2017-03-25
Node.js学习(1)----HTTP服务器与客户端
Node.js 标准库提供了 http 模块,其中封装了一个高效的 HTTP 服务器和一个简易的HTTP 客户端。http.Server 是一个基于事件的 HTTP 服务器,它的核心由 Node.js 下层 C++部分实现,而接口由 Jav...
2015-11-12
回到顶部