JavaScript中链表的详细介绍

雨婷吖_4630

雨婷吖_4630

2019-01-02

6094人浏览

转载

本篇文章给大家带来的内容是关于javascript中链表的详细介绍,有一定的参考价值,有需要的朋友可以参考一下,希望对你有所帮助。

链表和数组

大家都用过js中的数组,数组其实是一种线性表的顺序存储结构,它的特点是用一组地址连续的存储单元依次存储数据元素。而它的缺点也正是其特点而造成,比如对数组做删除或者插入的时候,可能需要移动大量的元素。

这里大致模拟一下数组的插入操作:

    insert(arr, index, data){
        for(let i = index + 1; i <p>从上面的代码可以看出数组的插入以及删除都有可能会是一个O(n)的操作。从而就引出了链表这种数据结构,链表不要求逻辑上相邻的元素在物理位置上也相邻,因此它没有顺序存储结构所具有的缺点,当然它也失去了数组在一块连续空间内随机存取的优点。</p><h3>单向链表</h3><p><span class="img-wrap"><img src="https://img.php.cn//upload/image/880/877/695/1546394138978971.png?x-oss-process=image/resize,p_40" title="1546394138978971.png" alt="557295227-5c273f96b5146_articlex.png"></span></p><h4>单向链表的特点:</h4>
  • 用一组任意的内存空间去存储数据元素(这里的内存空间可以是连续的,也可以是不连续的)

  • 每个节点(node)都由数据本身和一个指向后续节点的指针组成

  • 整个链表的存取必须从头指针开始,头指针指向第一个节点

  • 最后一个节点的指针指向空(NULL)

链表中的几个主要操作

  • 创建节点

  • 插入节点

  • 搜索/遍历节点

  • 删除节点

  • 合并

初始化节点

  • 指针指向空

  • 存储数据

    class Node {
        constructor(key) {
            this.next = null;
            this.key = key;
        }
    }

初始化单向链表

  • 每个链表都有一个头指针,指向第一个节点,没节点则指向NULL

    class List {
        constructor() {
            this.head = null;
        }
    }

创建节点

    static createNode(key) {
        return new createNode(key);
    }

这里说明一下,这一块我是向外暴露了一个静态方法来创建节点,而并非直接把它封装进插入操作里去,因为我感觉这样的逻辑会更加正确一些。 从创建一个链表 -> 创建一个节点 -> 将节点插入进链表中。可能你会遇到一些文章介绍的方式是直接将一个数据作为参数去调用insert操作,在insert内部做了一个创建节点。

插入节点(插入到头节点之后)

插入操作只需要去调整节点的指针即可,两种情况:

  • head没有指向任何节点,说明当前插入的节点是第一个

    • head指向新节点

    • 新节点的指针指向NULL

  • head有指向的节点

    • head指向新的节点

    • 新节点的指针指向原本head所指向的节点

    insert(node) {
        // 如果head有指向的节点
        if(this.head){
           node.next = this.head;
        }else {
           node.next = null;
        }
        this.head = node;
    }

搜索节点

  • 从head开始查找

  • 找到节点中的key等于想要查找的key的时候,返回该节点

    find(key) {
        let node = this.head;
        while(node !== null && node.key !== key){
            node = node.next;
        }
        return node;
    }

删除节点

这里分三种情况:

  • 所要删除的节点刚好是第一个,也就是head指向的节点

    • 将head指向所要删除节点的下一个节点(node.next)

  • 要删除的节点为最后一个节点

    使用 Husky 在 JavaScript 仓库中强制执行本地 Git 钩子检查
    使用 Husky 在 JavaScript 仓库中强制执行本地 Git 钩子检查

    使用 Husky 将 pre-commit、pre-push 和 commit-msg 检查集成到仓库中,以便代理和开发人员在更改离开工作站之前运行相同的本地防护措施。

    下载
    • 寻找到所要删除节点的上一个节点(prevNode)

    • 将prevNode中的指针指向NULL

  • 在列表中间删除某个节点

    • 寻找到所要删除节点的上一个节点(prevNode)

    • 将prevNode中的指针指向当前要删除的这个节点的下一个节点

    delete(node) {
        // 第一种情况
        if(node === this.head){
            this.head = node.next;
            return;
        }
        
        // 查找所要删除节点的上一个节点
        let prevNode = this.head;
        while (prevNode.next !== node) {
            prevNode = prevNode.next;
        }
        
        // 第二种情况
        if(node.next === null) {
            prevNode.next = null;
        }
        
        // 第三种情况
        if(node.next) {
            prevNode.next = node.next;
        }
    }

单向链表整体的代码

class ListNode {
  constructor(key) {
    this.next = null;
    this.key = key;
  }
}

class List {
  constructor() {
    this.head = null;
    this.length = 0;
  }

  static createNode(key) {
    return new ListNode(key);
  }

  // 往头部插入数据
  insert(node) {
    // 如果head后面有指向的节点
    if (this.head) {
      node.next = this.head;
    } else {
      node.next = null;
    }
    this.head = node;
    this.length++;
  }

  find(key) {
    let node = this.head;
    while (node !== null && node.key !== key) {
      node = node.next;
    }
    return node;
  }

  delete(node) {
    if (this.length === 0) {
      throw 'node is undefined';
    }

    if (node === this.head) {
      this.head = node.next;
      this.length--;
      return;
    }

    let prevNode = this.head;

    while (prevNode.next !== node) {
      prevNode = prevNode.next;
    }

    if (node.next === null) {
      prevNode.next = null;
    }
    if (node.next) {
      prevNode.next = node.next;
    }
    this.length--;
  }
}

双向链表

如果你把上面介绍的单向列表都看明白了,那么这里介绍的双向列表其实差不多。

3524714793-5c28579ab4e5f_articlex.png

2438733537-5c2857c485a86_articlex.png

从上面的图可以很清楚的看到双向链表和单向链表的区别。双向链表多了一个指向上一个节点的指针。

初始化节点

  • 指向前一个节点的指针

  • 指向后一个节点的指针

  • 节点数据

    class ListNode {
        this.prev = null;
        this.next = null;
        this.key = key;
    }

初始化双向链表

  • 头指针指向NULL

    class List {
        constructor(){
            this.head = null;
        }
    }

创建节点

    static createNode(key){
        return new ListNode(key);
    }

插入节点((插入到头节点之后)

  • 看上图中head后面的第一个节点可以知道,该节点的prev指向NULL

  • 节点的next指针指向后一个节点, 也就是当前头指针所指向的那个节点

  • 如果head后有节点,那么原本head后的节点的prev指向新插入的这个节点(因为是双向的嘛)

  • 最后将head指向新的节点

    insert(node) {
        node.prev = null;
        node.next = this.head;
        if(this.head){
            this.head.prev = node;
        }
        this.head = node;
    }

搜索节点

这里和单向节点一样,就直接贴代码了

  search(key) {
    let node = this.head;
    while (node !== null && node.key !== key) {
      node = node.next;
    }
    return node;
  }

删除节点

和之前单向链表一样,分三种情况去看:

  • 删除的是第一个节点

    • head指向所要删除节点的下一个节点

    • 下一个节点的prev指针指向所要删除节点的上一个节点

  • 删除的是中间的某个节点

    • 所要删除的前一个节点的next指向所要删除的下一个节点

    • 所要删除的下一个节点的prev指向所要删除的前一个节点

  • 删除的是最后一个节点

    • 要删除的节点的上一个节点的next指向null(也就是指向删除节点的next所指的地址)

3094154137-5c28605177ddf_articlex.png

    delete(node) {
        const {prev,next} = node;
        delete node.prev;
        delete node.next;
        if(node === this.head){
            this.head = next;
        }
        if(next){
            next.prev = prev;
        }
        if(prev){
            prev.next = next;
        }
    }

双向链表整体代码

    class ListNode {
  constructor(key) {
    // 指向前一个节点
    this.prev = null;
    // 指向后一个节点
    this.next = null;
    // 节点的数据(或者用于查找的键)
    this.key = key;
  }
}

/**
 * 双向链表
 */
class List {
  constructor() {
    this.head = null;
  }

  static createNode(key) {
    return new ListNode(key);
  }

  insert(node) {
    node.prev = null;
    node.next = this.head;
    if (this.head) {
      this.head.prev = node;
    }
    this.head = node;
  }

  search(key) {
    let node = this.head;
    while (node !== null && node.key !== key) {
      node = node.next;
    }
    return node;
  }

  delete(node) {
    const { prev, next } = node;
    delete node.prev;
    delete node.next;

    if (node === this.head) {
      this.head = next;
    }

    if (prev) {
      prev.next = next;
    }
    if (next) {
      next.prev = prev;
    }
  }
}

总结

这里做一个小总结吧,可能有一部分人读到这里还不是特别的明白,我的建议是先好好看懂上面的单向链表。 其实只要你明白了链表的基础概念,就是有一个head,然后在有好多的节点(Node),然后用一个指针把他们串起来就好了,至于里面的插入操作也好,删除也好,其实都是在调整节点中指针的指向。


Java免费学习笔记:立即使用
解锁 Java 大师之旅:从入门到精通的终极指南

相关文章

java速学教程(入门到精通)
java速学教程(入门到精通)

java怎么学习?java怎么入门?java在哪学?java怎么学才快?不用担心,这里为大家提供了java速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

node.js javascript

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
Navicat创建数据库教程
Navicat创建数据库教程

本专题整理Navicat创建数据库相关教程,介绍新建前的准备、基础设置和创建后的检查方法。内容兼顾入门学习及实际使用需求,帮助用户了解不同数据库类型下的操作差异,为后续建表、保存数据和日常管理提供参考。

2026.11.20

0

7

Navicat入门教程大全
Navicat入门教程大全

本专题整理Navicat入门教程,从认识软件界面到开展数据库操作,介绍初次使用需要了解的知识和方法。内容兼顾连接配置、数据管理及日常使用中的疑问,方便用户按学习进度查阅,为后续实践和独立操作打好基础。

2026.11.20

0

17

Navicat数据库连接配置指南
Navicat数据库连接配置指南

从确认数据库信息到建立可用连接,本专题串联Navicat连接数据库的相关知识和操作方法。既有初次配置时需要了解的基础内容,也有连接后的检查思路,方便用户按实际需求查阅教程,逐步熟悉数据库连接的设置流程。

2026.11.20

0

10

PHP8.6数组与数据处理教程
PHP8.6数组与数据处理教程

本专题汇总PHP8.6数组与数据处理教程,涵盖CSV读取和导出、引用遍历删除、array_filter回调模式、配置键名冲突、pathinfo文件名校验、GMP大整数进制转换及UTF-8正则筛选,说明升级兼容变化、输入范围和失败处理方法。

2026.11.20

0

8

PHP8.6升级迁移教程
PHP8.6升级迁移教程

本专题汇总PHP8.6升级迁移与弃用接口改造教程,涵盖反射调用、对象属性赋值、标识符更名、构造函数与__debugInfo调整,以及插件类名检查、常量导出、ArrayIterator排序、SPL和DTO查询参数转换,帮助梳理弃用提示并完成代码兼容改造。

2026.11.20

0

10

PHP8.6安装配置与FPM运维教程
PHP8.6安装配置与FPM运维教程

本专题汇总PHP8.6正式版安装部署与FPM运维教程,涵盖Linux并存安装、独立ini配置、扩展重新编译、Nginx切换与回滚、FPM状态监控和慢日志排查,以及环境变量、请求超时、OPcache刷新和预加载配置。

2026.11.20

0

10

Nginx CVE-2026-123007排查与防护指南
Nginx CVE-2026-123007排查与防护指南

Nginx HTTP/2漏洞该怎么修复?本专题围绕CVE-2026-123007,介绍安全版本升级、模块兼容检查和配置恢复方法,以及日志排查、权限设置等后续加固操作,方便你按实际部署情况查找对应教程。

2026.11.20

20

8

GoFrame框架Web开发与路由中间件
GoFrame框架Web开发与路由中间件

本专题聚焦GoFrame框架的Web开发,拆解路由注册与匹配规则、请求参数获取、参数校验与中间件执行顺序,说明统一响应、JWT鉴权、文件上传与接口文档生成的落地方式,并补充优雅重启与测试实践。

2026.11.17

60

15

GoFrame框架安装与gf命令行工具
GoFrame框架安装与gf命令行工具

本专题围绕GoFrame框架的安装与工具链配置展开,讲清Go版本要求、gf命令行的安装方式、代理镜像与依赖准备,说明项目初始化、热编译、交叉编译打包的做法,并整理安装阶段的常见报错与验证步骤。

2026.11.17

80

15

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
LLVM Programmer’s Manual
LLVM Programmer’s Manual

共0课时 | 0人学习

MongoDB 教程
MongoDB 教程

共17课时 | 6.6万人学习