双向链表[js实现] 【4】
用途： 获取相应位置的元素
思路
定义一个current和index初始都指向第一个节点。
image.png
current和index向后移，直到和position相等。然后把current对应节点的data返回即可。
image.png
编码
- 首先是越界判断，小于零或者大于等于链表长度返回false
- 定义变量，current和index。current指向head，index从0开始。
- while循环向后寻找，每次执行完后给index进行+1。并将current的next赋值给current。
- 直到current和position相等，跳出循环，返回current的data
TwoWayLinkList.prototype.get = function (position) {
// 越界判断
if (position < 0 || position >= this.length) { return false }
// 获取元素
var current = this.head
var index = 0
while (index++ < position) {
current = current.next
}
return current.data
}
复制代码测试一下
// 测试
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())
console.log(list.get(2))
image.png
效率分析
其实现在的get()方法的效率并不是很高。比如position为99，那么我们就需要从0一直找到99。对于单向链表只能从头开始找。但是双向链表可以根据就近原则，选择从前往后找，还是从后往前找。
- this.length / 2 > position :从前向后遍历
- this.length / 2 < position :从后向前遍历
- 对于从后向前寻找的current初始指向tail，index为length-1(小标为长度-1)
- 每次循环后减一
代码
TwoWayLinkList.prototype.get = function (position) {
// 越界判断
if (position < 0 || position >= this.length) { return false }
if (this.length / 2 >= position) {
// 获取元素
var current = this.head
var index = 0
while (index++ < position) {
current = current.next
}
} else {
// 获取元素
var current = this.tail
// 元素的下标只到length-1
var index = this.length - 1
while (index-- > position) {
current = current.prev
}
}
return current.data
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-06-10，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录