JS数据结构0x004：链表

sumory 发布于2019-08-23 12:47 / 638人阅读

摘要：概述这篇文章是说链表，链表这种数据结构非常普遍，有时候我们根本就没有意识到用的是链表啥是链表链表就是用绳子连起来的酒瓶子，酒就是数据，每个酒瓶子都连着下一个酒瓶子。

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 栗子：表单进度

这个栗子使用其他数据结构也可以实现，这里特意使用链表来实现就是为了演示而已

效果

视图

源码

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 资源

源代码：[https://github.com/followWint...]

服务器托管私有云链表数据结构队列 linux 数据结构链表 java链表数据结构 C++数据结构链表

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/99001.html

React入门0x004：jsx 和数据渲染

摘要：概述在中，渲染数据的形式有多种多样，但是万变不离其中，都是用。当然，自由也带来混乱，需要将这种自由化为思想的自由，而不是工程的自由代码的自由，否则将会带来噩梦。 0x000 概述在React中，渲染数据的形式有多种多样，但是万变不离其中，都是用js。 0x001 渲染文本 // 渲染文本 ReactDom.render( 这是一个文本, document.getEle...

xingpingz 2019-08-23 11:27 评论0 收藏0
es6基础0x004：剩余参数

摘要：概述剩余参数将没有对应形参的参数聚合成一个数组语法只聚合未对应形参参数剩余参数只会将没有对应形参的参数聚合成一个数组而则是包含了所有的参数。剩余参数是数组剩余参数始终是一个数组，而不像是一个伪数组转化成数组解构剩余参数使用翻译翻译后 0x000 概述剩余参数将没有对应形参的参数聚合成一个数组 0x001 语法 function(a, b, ...theArgs) { } 0x002 ...

waltr 2019-08-23 13:00 评论0 收藏0
React入门0x007: 生命周期概念

摘要：概述上一章只是稍微了解了一下和相关的简单用法，这一章需要讲一下组件的生命周期。生命周期的概念这玩意似乎很高大上，其实就是一个假概念罢了，直接来实现一个类似的吧。 0x000 概述上一章只是稍微了解了一下state和setState相关的简单用法，这一章需要讲一下组件的生命周期。 0x001 生命周期的概念这玩意似乎很高大上，其实就是一个假概念罢了，直接来实现一个类似的吧。大凡事物从...

Blackjun 2019-08-23 11:30 评论0 收藏0
JS数据结构0x003：队列

0x000 概述这篇文章说的是队列，队列的用处也贼大，削峰、限流、消息异步化等等等 0x001 什么是队列队列就是先入先出的数组，就和平常银行排队一样，先排队的人先处理事务，如图 showImg(https://segmentfault.com/img/bVbi4Hp?w=1774&h=560);只有两个操作：入队：将数据放入队列出队：将数据取出并处理 0x002 初始化 js中的队列...

xuhong 2019-08-23 12:44 评论0 收藏0