JavaScript真的需要链表吗?
javaScript可以原生提供的数据类型的确有限,但是并不代表不需要。
从一开始只有Object、Array到现在增加的Map和Set也确实证明前端也在不断发展自己的数据结构。
下边就有些没有的数据结构进行模拟实现。
java中链表的必要性
Java内部有自己的链表结构的数据类型LinkedList
为什么要有链表这种存储结构呢?
因为在java中,java数组存在弊端,ArrayList倒是解决了部分弊端(支持动态自动扩容)。
但是 LinkedList则以链表的形式进行存储,会有其它好处,以下是对比
链表 | 数组 | |
---|---|---|
内存占用 | 不需要连续的内存空间 | 需要连续的内存空间 |
大小可变 | 链表的大小可动态变化 | 数组大小固定,不能动态扩展 |
增删 | 较快,只需要修改前一个元素的指针即可 | 较慢,需要移动修改元素只有的所有元素 |
查询 | 较慢,只能遍历查找 | 较快,可以通过下标直接访问 |
在访问方式上 | 必须是顺序访问,不能随机访问 | 可以随机访问其中的元素 |
空间的使用上 | 可以随意扩大 | 不能 |
链表是有data和指向下一个数据的指针地址两部分组成
数组是有下标索引和data两部分组成
数组和链表都是线性表的结构,只不过它们的存储方式不一样
根据存储方式不同,可将线性表分为顺序表和链式表;
数组:在内存中,是一块连续的内存区域;
链表:是由不连续的内存空间组成;
参考:链接1,链接2
JavaScript不需要链表
了解过链表的同学应该都知道,链表有几个特点:
1、可以动态扩展空间(在js中,数组本来是这样的,但是有的语言中数组的长度是固定的,不能动态添加,如c、java语言)
2、需要一个头节点
3、需要知道下一个节点的地址
因为数组结构的局限性,所以才会有链表结构的存储方式。
那么这些局限性,在JavaScript中是不存在的。我们看看MDN怎么说的?
数组是一种类列表对象,它的原型中提供了遍历和修改元素的相关操作。
JavaScript 数组的长度和元素类型都是非固定的。
因为数组的长度可随时改变,并且其数据在内存中也可以不连续,所以 JavaScript 数组不一定是密集型的,这取决于它的使用方式。
一般来说,数组的这些特性会给使用带来方便,但如果这些特性不适用于你的特定使用场景的话,可以考虑使用类型数组 TypedArray
要问一个问题。
有谁知道JS的Array底层到底是个什么东西?
它具备栈的用法,push pop,加上unshift shift又是一个queue
又具备splice功能(链表擅长的)
但随机访问又具备O(1)的保证(真实array?hashmap?)
主要还是JS是门解释型&&高级上层语言,你所想写的东西底层体现的不一定是完完全全的数据结构思想体现。所写内容的性能实际受到的影响因素太多了。
换种问法好了,Array.prototype.sort底层采用的排序方案是什么?每款引擎每个年代都是同一种方案吗?
所以从前端数据结构角度(面向面试编程),链表是一个重要的算法、数据结构考点,实际使用实在是鲜有机会。
相关文章
- javascript、ruby和C性能一瞥(3) :上汇编
- JavaScript位运算符
- JavaScript类和继承:constructor属性
- [Javascript] Filter out Duplicates from Flat JavaScript Array with array.filter / reduce / Set
- [Javascript] Hide Properties from Showing Up in "for ... in" Loops in JavaScript
- [Javascript] Use requestIdleCallback to schedule JavaScript tasks at an optimal time
- [Javascript] Create an Image with JavaScript Using Fetch and URL.createObjectURL
- [Javascript] Avoiding Mutations in JavaScript with Immutable Data Structures
- [Javascript] Multiply Two Arrays over a Function in JavaScript
- [Javascript] Conditionally spread entries to a JavaScript object
- [Javascript] Await a JavaScript Promise in an async Function with the await Operator
- [Javascript] Understanding the .constructor property on JavaScript Objects
- [Javascript] Link to Other Objects through the JavaScript Prototype Chain
- [Javascript] Proper use of console.assert in JavaScript
- [Javascript] JavaScript Array Methods in Depth - push
- [Javascript] Hide Properties from Showing Up in "for ... in" Loops in JavaScript
- [Javascript] Understanding the .constructor property on JavaScript Objects
- [Javascript] JavaScript Array Methods in Depth - push
- javascript面向对象之Javascript 继承
- 4个Javascript 中的 for 循环
- 你真的会用ABAP, Java和JavaScript里的constructor么?
- Webclient UI view里Javascript的注释问题
- atitit.js javascript 调用c# java php后台语言api html5交互的原理与总结p97
- Angular input控件的click事件表达式如何被转换成JavaScript函数
- 【JavaScript变量】Javascript的全局变量&局部变量
- jQWidgets JavaScript 16.0 Crack
- JavaScript采用append添加的元素错误
- web前端框架Javascript开发基础之JavaScript作用域