双向链表[js实现] 【3】
转为字符串
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都指向新节点。
image.png
if (this.length == 0) {
this.head = newNode
this.tail = newNode
}当原来的链表不是空的
也就是进入了else，此时还需要考虑到一些其他情况:
- 当插入的位置是索引为0的位置，要改head的指向
- 当插入的位置是结尾，要改tail指向当向索引是0的位置插入 此时的header和tail都指向着原来的节点。
image.png
然后需要把header指向新节点，再把原来节点的prev指向新节点、把新节点的next指向原来的节点
image.png
// 判断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指向新节点
image.png
// 判断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())
image.png
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-06-08，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录