js数据结构与算法:链表
目录
1.链表初认识
1.1链表
链表由一系列结点(链表中每一个元素称为结点)组成,
结点可以在运行时动态生成。
每个结点包括两个部分:
一个是存储数据元素的数据域,
另一个是存储下一个结点地址的指针域。
head用作指向第一个元素的指针(引用)
node里面的value代表数据,next代表指向下一项的指针
当node.next指向的为空时,代表此时的node为最后一个元素
链表的最后一个元素,他的next指向一定是undefined
1.2为什么使用链表
使用链表存储数据,比数组好。
为什么这么说。
数组有一个缺点,就是他的大小固定,
向里面插入数据或者删除时,需要移动元素。
成本较高,而链表只需要改变指针的指向就可以了。
注意:
访问链表的元素,必须从链表的起点(表头)
开始迭代链表。直到访问到指定的元素。
2.链表的各种方法
2.1搭建链表
我们还是用对象的形式来模拟链表。在创建
链表的时候我们需要定义两个辅助工具。
一个用于检查传入的元素是否与链表中的
元素是否相等,另一个用于创建一个新节点。
检查相等:
function defaultEquals(a,b){
return a===b
}
创建一个新节点(node):
class Node{
constructor(element){
this.element=element
this.next=undefined
}
}
完整的链表结构:
2.2 push()
向一个链表插入一个元素,记住是在尾部
插入元素,插入其他位置的函数在下面解释。
那么我们就需要考虑,插入尾部时,就会有两种
情况,一个就是链表为空,添加的元素就是第一个元素
还有一种就是向链表的尾部插入元素。
在这里我们用head来保存对第一个元素的引用
用current来代表指向链表的项。用count来代表链表的长度
链表为空:
当链表为空时,我们只需要将head的指向改变为node。
链表的最后一项的next一定时null(或者undefinded)
链表不为空时:
链表不为空迭代链表,判断next的指向。得到最后一个元素
将他的指向修改为指向插入的元素
源码:
class Linklist{
constructor(Equals){
this.count=0
this.head=undefined
this.Equals=Equals
}
push(element){
const node=new Node(element)
let current
if(this.head==null){
this.head=node
}
else{
current=this.head
while(current.next!=null){
current=current.next
}
current.next=node
}
this.count++
}
}
2.3 removeAt(index)
removeAt(index)用于移除指定位置的元素。
那么首先需要链表不为空,之后就是考虑移除
元素的位置,如果是第一个元素,我们只要将head
指向下一个元素,如果是其他位置时,需要判断移除
元素的合法性(大于0),在这里我们引入一个变量
previous用于标记当前元素的前一个位置。
只需要将previous指向于当前元素的先一个元素
removeAt(index){
if(index>=0&&index<this.count){
let current=this.head
if(index===0){
this.head=current.next
}else{
let provious
for(let i=0;i<index;i++){
provious=current
current=current.next
}
provious.next=current.next
}
this.count--
return current.element
}
return undefined
}
2.4 getElement(index)
getElement(index)用于得到指定位置的值,
为此我们需要迭代链表,直到循环到指定的
位置
getElementAt(index){
if(index>=0&&index<this.count){
let node=this.head
for(let i=0;i<index&&node!=null;i++){
node=node.next
}
return node
}
return undefined
}
}
2.5 isEmpty()和size()
isEmpty()和size()实现这两个方法就比较简单
判断一下count就行了
代码:
isEmpty(){
return this.count===0
}
size(){
return this.count
}
2.6 toString()
用于将链表对象转化为字符串。如果链表
为空,返回空字符串,不为空迭代所有的元素
将元素值添加字符串。
toString(){
if(this.head==null){
return ""
}
let objString=`${this.head.element}`
let current=this.head.next
for (let i=1;i<this.size()&¤t!==null;i++){
objString=`${ objString},${current.element}`
current=current.next
}
return objString
}
3.使用链表并总结
3.1使用链表
const list=new Linklist()
list.push(23)
list.push(65)
list.push(45)
list.push(3)
console.log(list)
console.log(list.size())
console.log(list.isEmpty())
console.log(list.toString())
console.log(list.removeAt(2))
console.log(list.getElementAt(1))
3.2总结
1.学会了链表的一些基本概念。
2.掌握了链表的一些方法,以及源码书写
✍在最后,如果觉得博主写的还行,
期待🍟点赞 🍬评论 🍪收藏
相关文章
- Html Table用JS导出excel格式问题 导出EXCEL后单元格里的000412341234会变成412341234 7-14 会变成 2018-7-14(7月14) 自定义格式 web利用table表格生成excel格式问题 js导出excel增加表头、mso-number-format定义数据格式 数字输出格式转换 mso-number-format:"@"
- html table表格导出excel的方法 html5 table导出Excel HTML用JS导出Excel的五种方法 html中table导出Excel 前端开发 将table内容导出到excel HTML table导出到Excel中的解决办法 js实现table导出Excel,保留table样式
- 【原创】分布式之数据库和缓存双写一致性方案解析(三) 前端面试送命题(二)-callback,promise,generator,async-await JS的进阶技巧 前端面试送命题(一)-JS三座大山 Nodejs的运行原理-科普篇 优化设计提高sql类数据库的性能 简单理解token机制
- 【Js】前端使用xlsx.full.min.js读取和导出excel表格数据
- js 所有文档加载完后执行代码
- js,jq滚动监听,切换等常用JS代码
- JS链表原理
- 微信小程序:【JS】中的函数合集!更新中...
- 【Vue/js】Js中执行变量中的命令语句,也就是所谓的宏替换(很实用的例子)
- Node.js Stream - 基础篇
- JS Foo.getName笔试题解析,杂谈静态属性与实例属性,变量提升,this指向,new一个函数的过程
- js数据结构-链表
- js勾选时显示相应内容
- 【HarmonyOS】【JS】【布局】鸿蒙js开发input 输入框弹出输入法时上方布局被挤扁?
- 【HarmonyOS】【JS】 鸿蒙js开发使用div自带的scroll,滑动条拉不到最下面?
- 读JS高级——第五章-引用类型 _记录
- JS模式:jq中简单的模式--》采摘自js设计(tomxu_version)
- 《写给PHP开发者的Node.js学习指南》一第 2 章 简单的Node.js框架2.1 HTTP服务器
- js 小知识
- js 保留两位小数,Js四舍五入,JavaScript Math四舍五入
- JS教程之使用 Pinia、Electron 和 Quasar 构建 Vue 3 桌面应用程序
- JS教程之Electron.js设计强大的多平台桌面应用程序的好工具
- 聊聊JS动画库:Velocity.js
- three.js之目录
- js 给json添加新的字段,或者添加一组数据,在JS数组指定位置删除、插入、替换元素
- 推荐4款高星星JS库:canvas库-Fabric.js、JavaScript客户端文件上传库-FilePond、客户端保存文件解决方案-FileSaver、JavaScript在线解压 ZIP 文件-JSZip
- 【HarmonyOS】【JS】【布局】鸿蒙js开发input 输入框弹出输入法时上方布局被挤扁?
- js 数组 深拷贝 复制 (汇总)
- Vue.js 入门指南之“前传”(含sublime text 3 配置)
- JQuery/JS插件 json2.js