脚本宝典收集整理的这篇文章主要介绍了JS数据结构0x004:链表,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
0x000 概述
这篇文章是说链表,链表这种数据结构非常普遍,有时候我们根本就没有意识到用的是链表
0x001 啥是链表
链表就是用绳子连起来的酒瓶子,酒就是数据,每个酒瓶子都连着下一个酒瓶子。
链表一共有两个操作
- 插入:将一个新的节点插入链表
- 删除:将一个节点从链表中删除
0x001 初始化
链表不像数组、队列、栈一样需要容器,链表是通过一个数据引用另一个数据连接起来的,所以链表的初始化就是初始化第一个链表节点,这个链表作为特殊的开始节点,不作为数据。
function init() {
return {
data: 'start',
next: null
}
}
0x002 插入节点
插入节点有两种情况
- 直接插到最后面:直接将最后一个节点的
next
指向新的节点
- 插到指定节点后面:找到这个节点,将新节点的
next
指向这个节点的next
,并将这个节点的next
指向新节点
function insert(node, newNode, data) {
while (node) {
if (data && node.data === data) {
if (node.next) {
newNode.next = node.next
}
node.next = newNode
return
}
if (!data && node.next === null) {
node.next = newNode
return
}
node = node.next
}
}
0x003 删除节点
删除节点只需要断开next
指向就行了
function delete_(node, data) {
let parent = node
node = node.next
while (node) {
if (node.data === data) {
if (parent) {
parent.next = node.next
return
} else {
return
}
}
parent = node
node = node.next
}
throw `not found node by data: ${data}`
}
0x004 使用
let node = init() // {'data':'start','next':null}
insert(node, {data: 2, next: null}) // {'data':'start','next':{'data':2,'next':null}}
insert(node, {data: 3, next: null}) // {'data':'start','next':{'data':2,'next':{'data':3,'next':null}}}
insert(node, {data: 4, next: null}, 2) // {'data':'start','next':{'data':2,'next':{'data':4,'next':{data: 3, next: null}}}}
delete_(node, 2) // {'data':'start','next'{'data':4,'next':{data: 3, next: null}}}
0x005 栗子:表单进度
这个栗子使用其他数据结构也可以实现,这里特意使用链表来实现就是为了演示而已
- 效果
-
视图
<div class="container">
<div id="content" class="mt-2">
</div>
<button class="btn btn-primary mt-2" id="btn">填写下一项</button>
</div>
-
源码
<script src="./../index.js"></script>
<script>
let node = init({
data: "开始验证",
})
insert(node, {
data: "个人信息",
})
insert(node, {
data: "兴趣爱好",
})
insert(node, {
data: "收货地址",
})
let nodeNow = node
document.getElementById('btn').onclick = () => {
if (!nodeNow) return
let p = document.createElement('p')
p.innerText = nodeNow.data
document.getElementById('content').appendChild(p)
nodeNow = nodeNow.next
}
</script>
0x006 双向链表
在上面的视线中,使用next
指向下一个节点,从方向上说,我们可以从父节点访问子节点,但是无法从子节点访问父节点,或者说,我只能从一个方向有序访问链表。在这基础上衍生出双向链表,双向链表就是在单向链表的基础上添加对上一个节点的引用
- 示意图
-
节点
{
"data":"",
"prev":null,
"next":null
}
-
插入
newNdoe.prev=node.prev // 将新节点的 prev 指向当前节点的 prev
newNode.next=node // 将新节点的 next 点指向当前节点
node.prev.next=newNode // 将新节点的 prev 的 next 指向新节点
-
删除
node.prev.next=node.next // 将当前节点的 prev 的 next 指向当前节点的 next
node.prev=null // 将当前节点的 prev 断开
node.next.prev=node.prev// 将当前节点的 next 的 prev 指向当前节点的 prev
node.next=null // 将当前节点的 next 断开
0x007 环形链表
环形链表就是将收尾的节点也链接起来,如果是单项链表首尾连接,那就是单项环形链表,如果是双向链表首尾连接,那就是双向循环链表。代码没有太大的差别,就是在最后一个节点next
指向第一个,第一个节点的prev
指向最后一个,形成一个环装
- 图示
0x008 资源
以上是脚本宝典为你收集整理的JS数据结构0x004:链表全部内容,希望文章能够帮你解决JS数据结构0x004:链表所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。