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

数组

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

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

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

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

1 - 访问索引比较方便

内存地址0xA0000xA0080xA0100xA0180xA0200xA0280xA0300xA038
序数0123456...
其他数据数据 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数组操作时间复杂度
pushO(1)
pop(删除最后一个元素并返回删除的元素)O(1)
shift(删除第一个元素并返回删除的元素)O(n)
unshift (在数组的首位添加一个元素)O(n)
slice(截取)O(n)
splice(从数组中添加/删除项目,然后返回被删除的项目)O(n)
concatO(n)
findO(n)
filterO(n)
everyO(n)

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

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

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

单向链表

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

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

  • 链表节点包括 keynext 指针

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

  • 尾指针指向null

实现单向链表:

原文链接:segmentfault.com

上一篇:全球 43 亿 IPv4 地址已耗尽!IPv6,刻不容缓
下一篇:gulp插件解读 - gulp-util(gulp4.0建议弃用)

相关推荐

  • 🙋Hanjst汉吉斯特改进+enSafeExpression安全表达式等

    Hanjst汉吉斯特模版语言及模版引擎,近期持续改进升级。 这次改进主要是增加了对安全输出表达式兼容,由于涉及到对软件开发过程中的效率和软件运行效率的平衡和取舍,所以多写了几句,以描述这个权衡利弊对...

    1 个月前
  • 🙋Hanjst汉吉斯特升级:+showImageAsync及性能改进等

    自2019年元旦🙋Hanjst汉吉斯特 模板语言及其编译引擎发布,已经过去一年多了。 这期间随着 🙋Hanjst汉吉斯特 的推广应用,我们也陆续发布了如下一些更新内容: 🛠️Hanjst/汉吉...

    2 个月前
  • 🙋Hanjst汉吉斯特优化+JsonDataFromScript等

    近日继续对 🙋Hanjst汉吉斯特优化改进。这次的改进思考是从服务器端返回的 HanjstJsonData的容器设计问题。目前的做法是服务器端的HanjstJsonData放入终端页面的一个Div元...

    25 天前
  • 😉我用 Nuxt.js 仿了个掘金

    前言 首先肯定是要夸夸掘金啦,最开始从 CSDN 到 博客园 再到 掘金,个人感觉掘金的技术氛围非常的nice,真是个宝藏社区👏。技术文章大多以前端为主,对前端开发者非常友好,质量也是歪瑞古的。

    2 个月前
  • 😀一个原生js弹幕库

    danmujs 😀一个原生js弹幕库,基于 CSS3 Animation 地址、核心代码 本项目基于 rcbullets,项目约70%的代码基于rcbullets,首先要感谢这个项目的作者,如...

    5 个月前
  • 🕵️‍♀️由原型到JS中的“模拟类”

    讲述了有关 JavaScript 中原型相关知识,又引出了 JavaScript 中的“类“究竟是什么?,以及一系列相关问题。 一、前置知识 1、JavaScript 的面向对象(OOP) ​ 面向...

    3 个月前
  • 🔥《吊打面试官》系列 Node.js 必知必会必问!

    (/public/upload/f204a3b224d986128f1b4d9b8d06cd17) 前言 codeing 应当是一生的事业,而不仅仅是 30 岁的青春🍚 本文已收录 Git...

    4 个月前
  • 💖CSS + JS 送学妹满屏幕小爱心

    故事开始 午饭时间,暗恋已久的学妹拉着我的衣袖:“学长学长,你能不能让这些爱心变成五颜六色的吗~”。 我在旁边笑开了花~~~ image.png(/public/upload/04aaa24e...

    2 个月前
  • (vuejs学习)2、使用ElementUI(*)

    1.element安装 开发环境是win10,一到node官网下载node的.msi包(https://npm.taobao.org/mirrors/node/v10.16.0/nodev10.16....

    1 年前
  • (vuejs学习)1、Vue初上手(*)

    参考《官方(https://cli.vuejs.org/zh/guide/installation.html)》官方: Node 版本要求: Vue CLI 需要 Node.js 8.9 或更高...

    1 年前

官方社区

扫码加入 JavaScript 社区