JavaScript真的需要链表吗？
<p>javaScript可以原生提供的数据类型的确有限，但是并不代表不需要。<br>从一开始只有Object、Array到现在增加的Map和Set也确实证明前端也在不断发展自己的数据结构。<br>
下边就有些没有的数据结构进行模拟实现。<br>
<img src="https://img2020.cnblogs.com/blog/870258/202109/870258-20210907172636574-1610470426.png" alt="" loading="lazy"></p>
<h1 id="java中链表的必要性">java中链表的必要性</h1>
<p>Java内部有自己的链表结构的数据类型LinkedList<br>
为什么要有链表这种存储结构呢？<br>
因为在java中，java数组存在弊端，ArrayList倒是解决了部分弊端（支持动态自动扩容）。<br>
但是 LinkedList则以链表的形式进行存储，会有其它好处，以下是对比</p>
<table>
<thead>
<tr>
<th></th>
<th>链表</th>
<th>数组</th>
</tr>
</thead>
<tbody>
<tr>
<td>内存占用</td>
<td>不需要连续的内存空间</td>
<td>需要连续的内存空间</td>
</tr>
<tr>
<td>大小可变</td>
<td>链表的大小可动态变化</td>
<td>数组大小固定，不能动态扩展</td>
</tr>
<tr>
<td>增删</td>
<td>较快，只需要修改前一个元素的指针即可</td>
<td>较慢，需要移动修改元素只有的所有元素</td>
</tr>
<tr>
<td>查询</td>
<td>较慢，只能遍历查找</td>
<td>较快，可以通过下标直接访问</td>
</tr>
<tr>
<td>在访问方式上</td>
<td>必须是顺序访问，不能随机访问</td>
<td>可以随机访问其中的元素</td>
</tr>
<tr>
<td>空间的使用上</td>
<td>可以随意扩大</td>
<td>不能</td>
</tr>
</tbody>
</table>
<p>链表是有data和指向下一个数据的指针地址两部分组成<br>
<img src="https://img2020.cnblogs.com/blog/870258/202109/870258-20210908105504299-808725056.png" alt="" loading="lazy"></p>
<p>数组是有下标索引和data两部分组成<br>
<img src="https://img2020.cnblogs.com/blog/870258/202109/870258-20210908105705495-1977900114.png" alt="" loading="lazy"></p>
<p>数组和链表都是线性表的结构，只不过它们的存储方式不一样<br>
根据存储方式不同，可将线性表分为顺序表和链式表；<br>
数组：在内存中，是一块连续的内存区域；<br>
链表：是由不连续的内存空间组成；<br>
<img src="https://img2020.cnblogs.com/blog/870258/202109/870258-20210908113520770-1407779940.gif" alt="" loading="lazy"><br>
<img src="https://img2020.cnblogs.com/blog/870258/202109/870258-20210908113554218-606656945.png" alt="" loading="lazy"><br>
参考：链接1，链接2</p>
<h1 id="javascript不需要链表">JavaScript不需要链表</h1>
<p>了解过链表的同学应该都知道，链表有几个特点：<br>
1、可以动态扩展空间（在js中，数组本来是这样的，但是有的语言中数组的长度是固定的，不能动态添加，如c、java语言）<br>
2、需要一个头节点<br>
3、需要知道下一个节点的地址</p>
<p>因为数组结构的局限性，所以才会有链表结构的存储方式。<br>
那么这些局限性，在JavaScript中是不存在的。我们看看MDN怎么说的？</p>
<blockquote>
<p>数组是一种类列表对象，它的原型中提供了遍历和修改元素的相关操作。<br>
JavaScript 数组的长度和元素类型都是非固定的。<br>
因为数组的长度可随时改变，并且其数据在内存中也可以不连续，所以 JavaScript 数组不一定是密集型的，这取决于它的使用方式。<br>
一般来说，数组的这些特性会给使用带来方便，但如果这些特性不适用于你的特定使用场景的话，可以考虑使用类型数组 TypedArray</p>
</blockquote>
<p>要问一个问题。<br>
有谁知道JS的Array底层到底是个什么东西？<br>
它具备栈的用法，push pop，加上unshift shift又是一个queue<br>
又具备splice功能（链表擅长的）<br>
但随机访问又具备O(1)的保证（真实array？hashmap？）</p>
<p>主要还是JS是门解释型&&高级上层语言，你所想写的东西底层体现的不一定是完完全全的数据结构思想体现。所写内容的性能实际受到的影响因素太多了。<br>
换种问法好了，Array.prototype.sort底层采用的排序方案是什么？每款引擎每个年代都是同一种方案吗？</p>
<p>所以从前端数据结构角度（面向面试编程），链表是一个重要的算法、数据结构考点，实际使用实在是鲜有机会。</p><br><br>
来源：https://www.cnblogs.com/dingshaohua/p/15239309.html
頁:
[1]