您现在的位置是:首页 > Javascript
当前栏目
双向链表[js实现] 【3】
2023-02-25 18:16:13 时间
转为字符串
forwardString
用途:向前,输出字符串。
- 从尾部开始,先找到第一个节点。也就是tail指向的节点。
- 定义一个结果字符串
- 依次向前遍历,只要current不为空,将当前节点current的data拼接到result上。然后将current.prev作为新的current。
- 直到current为空,停止循环。返回拼接的结果字符串。
/**
* 2.链表转换为字符串
*
* */
TwoWayLinkList.prototype.forwardString = function (data) {
// 指向第一个节点
var current = this.tail
var result = ""
// 依次向前遍历 只要有值就拼接到字符串上
while (current) {
result += current.data + " "
current = current.prev
}
return result
}
backwardString
用途: 向后输出字符串。
- 从头部开始,与上一个的区别:先将head作为current的初始值。
- 依次向前遍历,如果有值拼接到结果字符串上。并把当前current的next作为新的current
- 直到current为空,返回结果字符串。
TwoWayLinkList.prototype.backwardString = function (data) {
// 指向第一个节点
var current = this.head
var result = ""
// 依次向后遍历 只要有值就拼接到字符串上
while (current) {
result += current.data + " "
current = current.next
}
return result
}
复制代码
toString
实际上就是调用了backwardString()方法。
TwoWayLinkList.prototype.toString = function (data) {
return this.backwardString()
}
复制代码
insert()
说明:
传入两个参数position(位置)和data(要插入的数据)
首先做越界处理
position不能小于0 也不能大于当前双向链表的长度。
/**
* isnert(position,data)
* */
TwoWayLinkList.prototype.insert = function (position, data) {
if (position < 0 || position > this.length) return false
}
创建新节点
// 根据data创建新的节点
var newNode = new Node(data)
判断原来链表是否为空
说明插入的是第一个节点,只需要将head和tail都指向新节点。
if (this.length == 0) {
this.head = newNode
this.tail = newNode
}
当原来的链表不是空的
也就是进入了else,此时还需要考虑到一些其他情况:
- 当插入的位置是索引为0的位置,要改head的指向
- 当插入的位置是结尾,要改tail指向当向索引是0的位置插入 此时的header和tail都指向着原来的节点。
然后需要把header指向新节点,再把原来节点的prev指向新节点、把新节点的next指向原来的节点
// 判断position是否为0
if (position == 0) {
// 当前的head指向原来的节点,当新节点插入后新节点就是他的prev了
this.head.prev = newNode
// 当前的head指向原来的节点,此时新节点的next就是原来的节点(也就是head)
newNode.next = this.head
// 改变head的指向
this.head = newNode
}
当向结尾插入
此时就类似于我们之前写好的append方法
else if (position == this.length) {
this.tail.next = newNode
newNode.prev = this.tail
this.tail = newNode
}
当插入中间位置
此时需要先找到位置对应的元素。我们使用current向后查找。如图:这里需要更改四个指向
- 新节点的prev需要指向current节点的上一个节点
- 新节点的next指向current
- current节点的prev指向新节点
- current节点的前一个节点的next指向新节点
// 判断position是否为0
if (position == 0) {
// 当前的head指向原来的节点,当新节点插入后新节点就是他的prev了
this.head.prev = newNode
// 当前的head指向原来的节点,此时新节点的next就是原来的节点(也就是head)
newNode.next = this.head
// 改变head的指向
this.head = newNode
} else if (position == this.length) {
this.tail.next = newNode
newNode.prev = this.tail
this.tail = newNode
} else {
var current = this.head
var index = 0
while (index++ < position) {
current = current.next
}
// 修改指针
newNode.next = current
newNode.prev = current.prev
current.prev.next = newNode
current.prev = newNode
}
完整代码
/**
* isnert(position,data)
* */
TwoWayLinkList.prototype.insert = function (position, data) {
// 越界判断
if (position < 0 || position > this.length) return false
// 根据data创建新的节点
var newNode = new Node(data)
// 判断原来的链表是否为空
if (this.length == 0) {
this.head = newNode
this.tail = newNode
} else {
// 判断position是否为0
if (position == 0) {
// 当前的head指向原来的节点,当新节点插入后新节点就是他的prev了
this.head.prev = newNode
// 当前的head指向原来的节点,此时新节点的next就是原来的节点(也就是head)
newNode.next = this.head
// 改变head的指向
this.head = newNode
} else if (position == this.length) {
this.tail.next = newNode
newNode.prev = this.tail
this.tail = newNode
} else {
var current = this.head
var index = 0
while (index++ < position) {
current = current.next
}
// 修改指针
newNode.next = current
newNode.prev = current.prev
current.prev.next = newNode
current.prev = newNode
}
}
this.length += 1
return true
}
测试一下
// 测试
var list = new TwoWayLinkList()
list.append('abc')
list.append('bce')
list.append('ghg')
console.log(list.insert(0, 'insert'))
console.log(list.insert(4, 'insert1'))
console.log(list.insert(3, 'insert2'))
console.log(list.toString())
相关文章
- Nacos 和 Apollo中的 长轮询 定时机制,太好用了
- Vue3 新特性 Computed、Watch、WatchEffect 看完就会
- 有 React fiber,为什么没有 Vue fiber?
- 前端开发必备的文件处理库!
- 手写 Bind:处理 New 的情况
- 22个Vue 源码中的工具函数
- 11个罕见的JavaScript单行代码,会让你大吃一惊
- 如何看待《关于禁止小程序 JavaScript 解释器使用规范要求》?
- 终于有人把Hadoop大数据系统架构讲明白了
- 太长了,巧妙地优化了跑马灯
- Xjson 是如何实现四则运算的?
- Vue3 的 Ref、IsRef、ToRef、ToRefs、ToRaw 详细介绍
- 聊聊 Kubectl scale 命令的优秀实践
- 小程序不让用 JS 解释器?那我再杠一次鹅厂
- 圆角大杀器,使用滤镜构建圆角及波浪效果!
- 五张图带你彻底理解 RocketMQ 轨迹消息
- SpringBoot 自定义参数解析器 So Easy!
- 围绕Vue 3 Composition API构建一个应用程序,包含一些优秀实践!
- Spring Boot快速接入Prometheus监控
- 聊聊 Spring boot 集成 Mybatis,你学会了吗?