JS数据结构&算法学习——链表

简介: 终于到链表篇了,掌握了链表就大概掌握了半个数据结构

链表

终于到链表篇了,掌握了链表就大概掌握了半个数据结构

链表是一种线性的存储结构,其节点之间的逻辑关系是通过节点所对应的引用(指针)来进行关联,其链表中的每个节点含有两部分,一个为存储数据(data)的,一个是作为存储引用(next),也就是相邻节点的地址,其实最后一个节点的next为空

1.webp.jpg

生活应用

我们生活中能体现链表的特点的就是列车了,列车一个车厢一个车厢连在一起,乘客是data,而列车的钩子为next,指向下一个列车,我们想在中间添加一个车厢只需要将两节车厢断开中间加入一个新的车厢,并将前一个车厢的钩子指向新的车厢,新的车厢的钩子指向下一个车厢,删除也是如此。

链表 VS 数组

参照之前的数组篇,可以对比一下链表和数组之前的区别

链表与数组同为线性的存储结构,但是有很大的区别如下:

  1. 数组的创建需要一段连续的存储空间,因为其物理地址是连续的,而链表的物理地址是可以是不连续的,所以它的创建只需要创建一个头结点即可
  2. 由于数组定义的限制所在,若不满足容量需求则需要麻烦的扩容,因为其连续性,扩容很麻烦,甚至来说如果物理地址被占用是无法进行扩容的,而链表可以任意增加容量,也就是说无穷大
  3. 数组进行插入和删除操作需要进行对目标元素后的所有元素进行移动,耗费时间极长,虽然JS给我们提供的Array类能帮助我们进行插入及删除等操作,比如说splice,但是底层原理还是不变的,而链表的插入与删除只需要通过修改引用值就可以完成,时间复杂度接近于O(1)
  4. 链表进行元素查找过程是需要从头部开始根据引用来寻找目标值,而数组查找元素只需要使用下标即可

链表封装

我们了解了链表的结构与其逻辑后封装了一个链表类如下:

function LinkList() {
    this.head = null
    this.length = 0
    function Node(data, next) {
        this.data = data
        this.next = next
    }
}
复制代码

链表的封装需要考虑整体的结构,在链表类内再定义一个节点类,因为链表中的节点有两个部分即数据和引用,和优先级队列封装类似


目录
打赏
0
0
0
0
69
分享
相关文章
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构。本文介绍了K-means算法的基本原理,包括初始化、数据点分配与簇中心更新等步骤,以及如何在Python中实现该算法,最后讨论了其优缺点及应用场景。
157 4
|
11天前
|
局域网网络管控里 Node.js 红黑树算法的绝妙运用
在数字化办公中,局域网网络管控至关重要。红黑树作为一种自平衡二叉搜索树,凭借其高效的数据管理和平衡机制,在局域网设备状态管理中大放异彩。通过Node.js实现红黑树算法,可快速插入、查找和更新设备信息(如IP地址、带宽等),确保网络管理员实时监控和优化网络资源,提升局域网的稳定性和安全性。未来,随着技术融合,红黑树将在网络管控中持续进化,助力构建高效、安全的局域网络生态。
30 9
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
31 2
探索局域网电脑监控软件:Python算法与数据结构的巧妙结合
在数字化时代,局域网电脑监控软件成为企业管理和IT运维的重要工具,确保数据安全和网络稳定。本文探讨其背后的关键技术——Python中的算法与数据结构,如字典用于高效存储设备信息,以及数据收集、异常检测和聚合算法提升监控效率。通过Python代码示例,展示了如何实现基本监控功能,帮助读者理解其工作原理并激发技术兴趣。
56 20
基于 Node.js Socket 算法搭建局域网屏幕监控系统
在数字化办公环境中,局域网屏幕监控系统至关重要。基于Node.js的Socket算法实现高效、稳定的实时屏幕数据传输,助力企业保障信息安全、监督工作状态和远程技术支持。通过Socket建立监控端与被监控端的数据桥梁,确保实时画面呈现。实际部署需合理分配带宽并加密传输,确保信息安全。企业在使用时应权衡利弊,遵循法规,保障员工权益。
31 7
深度探秘:运用 Node.js 哈希表算法剖析员工工作时间玩游戏现象
在现代企业运营中,确保员工工作时间高效专注至关重要。为应对员工工作时间玩游戏的问题,本文聚焦Node.js环境下的哈希表算法,展示其如何通过快速查找和高效记录员工游戏行为,帮助企业精准监测与分析,遏制此类现象。哈希表以IP地址等为键,存储游戏网址、时长等信息,结合冲突处理与动态更新机制,确保数据完整性和时效性,助力企业管理层优化工作效率。
26 3
Python 中的数据结构和算法优化策略
Python中的数据结构和算法如何进行优化?
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
79 1
JavaScript学习第二章--字符串
本文介绍了JavaScript中的字符串处理,包括普通字符串和模板字符串的使用方法及常见字符串操作方法如`charAt`、`concat`、`endsWith`等,适合前端学习者参考。作者是一位热爱前端技术的大一学生,专注于分享实用的编程技巧。
38 2
JavaScript学习第一章
本文档介绍了JavaScript的基础知识,包括其在网页中的作用、如何通过JavaScript动态设置HTML元素的CSS属性,以及JavaScript中的变量类型(`var`、`let`、`const`)和数据类型(基本数据类型与引用数据类型)。通过实例代码详细解释了JavaScript的核心概念,适合初学者入门学习。
61 1

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等