[JS与链表]普通链表

为什么要用链表

要储存一系列数据,最常用的数据结构是数组。数组有个缺点就是在中间插入或删除元素需要移动元素,成本很高。

什么是链表

链表也是有序元素的集合结构。链表中的元素在内存中并不是连续放置的。每个元素都可以理解为一个对象。包含了本身元素的值,和一个指向下一个元素的引用。

在内存的堆栈中假想:

现实也有一些链表的例子:

① 芭蕾舞队

中间插入一个芭蕾演员,需要:被插入点前一个演员牵(next),同时要牵住下一个演员(自身的next)

②火车挂载货厢

链表的好处

在于添加或移除元素的时候不需要移动其他元素。

但是在数组中我们可以通过指针直接访问任何位置的任何元素。

而若要访问链表中间的一个元素,则需要从表头开始迭代链表直到找到所需的元素。

创建链表

通过上面的例子,我们知道链表是由一块一块的节点链接起来。

所以我们需要先创建节点Node类

class Node {
   constructor(ele) {
        this.element = ele;
        // 暴露到外面赋值
        this.next = undefined;
    }
}
  • element代表当前链表元素的值

  • next属性指向链表下一个元素

然后我们来实现LinkedList类

class LinkedList {
    constructor() {
        this.count = 0;
        this.head = undefined;
    }
}

我们用count属性来统计链表元素的数量。用head来记录链表头端的首个元素。

在链表尾部添加元素

①链表为空,添加的是第一个元素。

②链表不为空,迭代找到最后一个元素,向其追加元素。

push(element) {
    const node = new Node(element);
    // 注意,这里是== null,==null会囊括===undefined和====null两种结果
    // 链表最后一个节点的下一个元素(next)始终是undefined或null
    if (this.head == null) {
        this.head = node;
    }else {
        let nextNode = this.head;
        while (nextNode.next!=null) {
            nextNode = nextNode.next;
        }
        nextNode.next = node;
    }
    this.count++;
}

从链表中移除元素(按照索引)

还是两种场景:

① 移除链表头部第一个元素。

可以看到只要把head赋值给第二个元素就好了。之前的head节点不需要删除,等待js的垃圾回收机制回收它(没有被引用。)

② 移除链表除头部之外其他元素。

由图示,我们只需要断开目标节点的next,并把目标节点前一个节点的next挂载到下一个节点的value即可。也就是说,我们需要获取剔除节点的前一个节点即可。

removeAt(index) {
    // 错误场景
    if (index>0 && index >=this.count) {return undefined}
    this.count --;
    // 移除第一项
    if (index === 0) {
        const throwEle = this.head.element;
        this.head = this.head.next;
        return throwEle;
    }else {
        // 移除中间项,只需要找到剔除节点的的前一个节点
        // 前一个节点
        let preNode;
        // 当前节点
        let currentNode = this.head;
        // 找到删除项
        for (var i =0;i<index;i++) {
            preNode = currentNode;
            currentNode = currentNode.next;
        }
        preNode.next = currentNode.next;
        return currentNode.element
    }
}

回头优化代码

既然我们能够在remove方法里通过index下标定位到链表的元素,那我们可以把定位的逻辑抽离出来作为内部公共方法。

getNodeAt(index) {
     if (index>0 && index >=this.count) {return undefined}
     if (this.index === 0) {return this.head}
     let currentNode = this.head;
     for (var i =0;i<index;i++) {
           currentNode = currentNode.next
     }
    return currentNode
}
removeAt(index) {
    // 错误场景
    if (index>0 && index >=this.count) {return undefined}
    let delNode;
    delNode = this.getNodeAt(index)
    // 移除第一项
    if (index === 0) {
        this.head = this.head.next;
    }else {
        let preNode = this.getNodeAt(index - 1);
        preNode.next = delNode.next;
    }
    this.count --;
    return delNode
}

在链表任意位置插入元素

还是两种情况:表头与表中

insertAt(ele,index) {
    if (index < 0 || index > this.count) {return false}
    const newNode = new Node(ele)
    if (index === 0) {
        const originHead = this.head;
        this.head = newNode;
        this.head.next = originHead
    }else {
        const originNode = this.getNodeAt(index);
        const preNode = this.getNodeAt(index - 1);
        preNode.next = newNode;
        newNode.next = originNode;
    }
    this.count ++;
    return true
}

就算是在结尾插入也是符合第二种场景。

返回元素在链表中的位置

思路类似于数组的indexof,通过迭代链表里的元素对比传参元素,若存在则返回下标,不存在就返回-1。

首先,我们需要定义比较函数。如果我们链表节点储存的element是数字或字符串等基本数据类型,我们可以使用a === b作为比较函数传入。但是如果是储存复杂的引用对象,我们必须开放让使用者自定义比较函数的接口。

// 以基本类型的数据对比为例
function compareFn(a,b) {
    return a === b
}
class LinkedList {
    constructor(equalFn=compareFn) {
        this.count = 0;
        this.head = undefined;
        this.equalFn = equalFn;
    }
}

可以看到,我们给予了LinkedList类一个默认的比较函数。同时也支持用户在生成实例的时候传入自定义的比较函数,以适应自身的比较需求。

indexOf(ele) {
    let currentNode = this.head;
    for (var i = 0 ;i < this.count;i++) {
        if (this.euqalFn(currentNode.element,ele)) {
            return i;
        }else {
            currentNode = currentNode.next;
        }
    }
    return -1
}

从链表中移除元素(指定值)

我们上面已经实现了根据索引删除链表中的元素。现在要实现根据指定的值移除元素,我们需要两步:

①通过指定的元素值找到它在链表中的下标。

②根据下标删除链表中的元素。

remove(ele){
    const index = this.indexOf(ele);
    return this.removeAt(index)
}

获取链表长度

size() {return this.count}

判断链表是否为空

isEmpty() {
    return this.size() === 0
}

获取头部元素

getHead() {
    return this.head;
}

toString方法

此方法会把LinkedList对象转换成一个字符串。

toString() {
    if (this.head == null) {return ''}
    let currentNode = this.head;
    let objStr = ''
    for (var i = 0 ;i < this.count;i++) {
       objStr+=`[下标为${i},值为${currentNode.element}]`
       currentNode = currentNode.next;
    }
}

代码整理

class Node {
   constructor(ele) {
        this.element = ele;
        this.next = undefined;
    }
}
function compareFn(a,b) {
    return a === b
}
class LinkedList {
    constructor(equalFn=compareFn) {
        this.count = 0;
        this.head = undefined;
        this.equalFn = equalFn;
    }
    toString() {
        if (this.head == null) {return ''}
        let currentNode = this.head;
        let objStr = ''
        for (var i = 0 ;i < this.count;i++) {
           objStr+=`[下标为${i},值为${currentNode.element}]`
           currentNode = currentNode.next;
        }
    }
    remove(ele){
        const index = this.indexOf(ele);
        return this.removeAt(index)
    }
    indexOf(ele) {
        let currentNode = this.head;
        for (var i = 0 ;i < this.count;i++) {
            if (this.equalFn(currentNode.element,ele)) {
                return i;
            }else {
                currentNode = currentNode.next;
            }
        }
        return -1
    }
    insertAt(ele,index) {
        if (index < 0 || index > this.count) {return false}
        const newNode = new Node(ele)
        if (index === 0) {
            const originHead = this.head;
            this.head = newNode;
            this.head.next = originHead
        }else {
            const originNode = this.getNodeAt(index);
            const preNode = this.getNodeAt(index - 1);
            preNode.next = newNode;
            newNode.next = originNode;
        }
        this.count ++;
        return true
    }
    getNodeAt(index) {
         if (index>0 && index >=this.count) {return undefined}
         if (this.index === 0) {return this.head}
         let currentNode = this.head;
         for (var i =0;i<index;i++) {
               currentNode = currentNode.next
         }
        return currentNode
    }
    removeAt(index) {
        // 错误场景
        if (index>0 && index >=this.count) {return undefined}
        let delNode;
        delNode = this.getNodeAt(index)
        // 移除第一项
        if (index === 0) {
            this.head = this.head.next;
        }else {
            let preNode = this.getNodeAt(index - 1);
            preNode.next = delNode.next;
        }
        this.count --;
        return delNode
    }
    push(element) {
        const node = new Node(element);
        // 注意,这里是== null,==null会囊括===undefined和====null两种结果
        // 链表最后一个节点的下一个元素(next)始终是undefined或null
        if (this.head == null) {
            this.head = node;
        }else {
            let nextNode = this.head;
            while (nextNode.next!=null) {
                nextNode = nextNode.next;
            }
            nextNode.next = node;
        }
        this.count++;
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/776.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

简单了解JSP

JSP概念与原理概念: Java Server Pages&#xff0c;Java服务端页面一种动态的网页技术&#xff0c;其中既可以定义 HTML、JS、CSS等静态内容&#xff0c;还可以定义Java代码的动态内容JSP HTML Java, 用于简化开发JSP的本质上就是一个ServletJSP 在被访问时&#xff0c;由JSP容…

博途PLC开放式以太网通信TRCV_C指令应用编程(运动传感器UDP通信)

博途PLC开放式以太网通信TSENG_C指令应用,请参看下面的文章链接: 博途PLC 1200/1500PLC开放式以太网通信TSEND_C通信(UDP)_plc的udp通信_RXXW_Dor的博客-CSDN博客开放式TSEND_C通信支持TCP 、UDP等,关于TSEND_C的TCP通信可以参看下面这篇文章:博途PLC 1200/1500PLC开放式…

opencv识别车道线(霍夫线变换)

目录1、前言2、霍夫线变换2.1、霍夫线变换是什么&#xff1f;2.2、在opencv中的基本用法2.2.1、HoughLinesP函数定义2.2.2、用法3、识别车道3.1、优化3.1.1、降噪3.1.2、过滤方向3.1.3、截选区域3.2、测试其它图片3.2.1、代码3.2.2、图片13.2.3、图片23.2.4、图片31、前言 最近…

C++模拟实现红黑树

目录 介绍----什么是红黑树 甲鱼的臀部----规定 分析思考 绘图解析代码实现 节点部分 插入部分分步解析 ●父亲在祖父的左&#xff0c;叔叔在祖父的右&#xff1a; ●父亲在祖父的右&#xff0c;叔叔在祖父的左&#xff1a; 测试部分 整体代码 介绍----什么是红黑树 红…

2023年江苏省职业院校技能大赛中职网络安全赛项试卷-教师组任务书

2023年江苏省职业院校技能大赛中职网络安全赛项试卷-教师组任务书 一、竞赛时间 9:00-12:00&#xff0c;12:00-15:00&#xff0c;15:00-17:00共计8小时。 二、竞赛阶段 竞赛阶段 任务阶段 竞赛任务 竞赛时间 分值 第一阶段 基础设施设置与安全加固、网络安全事件响应、数…

链表相关oj题

1.Leetcode203 移除链表元素 解题思路&#xff1a;从头节点开始进行元素删除&#xff0c;每删除一个元素&#xff0c;需要重新链接节点 struct ListNode* removeElements(struct ListNode* head, int val){struct ListNode*dummyheadmalloc(sizeof(struct ListNode));dummyhea…

spring5(四):IOC 操作 Bean 管理(基于注解方式)

IOC操作Bean管理&#xff08;基于xml方式&#xff09;前言一、注解1、概述二、入门案例1、Bean 的创建2、Bean的自动装配2.1 Autowired2、Qualifie3、Resource4、Value3、扫描组件3.1 配置文件版3.2 注解版4、测试前言 本博主将用CSDN记录软件开发求学之路上亲身所得与所学的心…

Mysql常用命令

mysql连接&#xff1a; [roothost]# mysql -u root -p Enter password:******创建数据库&#xff1a; CREATE DATABASE 数据库名&#xff1b; 删除数据库&#xff1a; drop database 数据库名; 使用mysqladmin删除数据库&#xff1a; [roothost]# mysqladmin -u root -p dr…

【数据结构】链表OJ(二)

Yan-英杰的博客 悟已往之不谏 知来者之可追 目录 一、反转链表 二、合并两个有序链表 三、链表分割 四、链表的回文结构 一、反转链表 输入&#xff1a;head [1,2,3,4,5] 输出&#xff1a;[5,4,3,2,1] 输入&#xff1a;head [1,2] 输出&#xff1a;[2,1] 示例 3&#xf…

Vulnhub靶场----10、LazySysadmin

文章目录一、环境搭建二、渗透流程一、环境搭建 DC-7下载地址&#xff1a;https://download.vulnhub.com/dc/DC-9.zip kali&#xff1a;192.168.144.148 DC-9&#xff1a;192.168.144.157 二、渗透流程 1、信息收集nmap -sV -sT -p- -T4 192.168.144.157思路&#xff1a; 1、80…

基于vivado(语言Verilog)的FPGA学习(3)——FPGA理论知识

基于vivado&#xff08;语言Verilog&#xff09;的FPGA学习&#xff08;3&#xff09;——FPGA理论知识 文章目录基于vivado&#xff08;语言Verilog&#xff09;的FPGA学习&#xff08;3&#xff09;——FPGA理论知识1. FPGA介绍1.1.FPGA内部结构&#xff08;1&#xff09;. 可…

【云原生|Docker】01-docker简介

目录 前言 Docker简介 1. 什么是docker 2. Docker和vm有什么区别 3. Docker架构 4. Docker特性 Docker安装 1. Docker版本介绍 2. Centos7安装docker 3. Docker校验 4. Docker启动 5. Docker配置文件 前言 接下来准备记录云原生系列的相关知识&#x…

Linux防火墙的关闭

查看防火墙的状态打开终端输入如下命令systemctl status firewalld如图所示&#xff1a;running表示防火墙目前处于打开状态输入命令进行关闭防火墙&#xff1a;systemctl stop firewalld如图所示正常的用户是没有权限的&#xff0c;需要输入管理员的密码才能够进行关闭防火墙。…

OpenAI GPT-4震撼发布:多模态大模型

OpenAI GPT-4震撼发布&#xff1a;多模态大模型发布要点GPT4的新功能GPT-4:我能玩梗图GPT4:理解图片GPT4:识别与解析图片内容怎样面对GPT4申请 GPT-4 API前言&#xff1a; &#x1f3e0;个人主页&#xff1a;以山河作礼。 &#x1f4dd;​&#x1f4dd;:本文章是帮助大家更加了…

中国版的“ChatGPT”狂飙的机会或许要出现了

⭐️我叫忆_恒心&#xff0c;一名喜欢书写博客的在读研究生&#x1f468;‍&#x1f393;。 如果觉得本文能帮到您&#xff0c;麻烦点个赞&#x1f44d;呗&#xff01; 近期会不断在专栏里进行更新讲解博客~~~ 有什么问题的小伙伴 欢迎留言提问欧&#xff0c;喜欢的小伙伴给个三…

avue-crud组件的行内编辑实现失焦保存,在没有右侧操作栏的情况下

前言 关于 avue 框架&#xff0c;其实本来不想写一篇随笔记录的&#xff0c;因为目前在网上有很多文章&#xff0c;关于其配置项介绍的比较详细&#xff0c;而且官网上也有对应的文档&#xff0c;这两者结合足以满足大部分的开发需求。 不过&#xff0c;产品经理总会有些不一…

[大二下]什么是NPM

[大二下]什么是npm? 什么是NPM? 最简单来回答: ​ 就是一个包管理器, 一个仓库, 谁需要里面的物品, 谁就拿 npm 全称 Node Package(译: 包,包裹) Manager(译:如下). 直译过来就是 Node的包管理, 但是我们真正咱们约定俗成的称 NPM为"Node的包管理器". npm是Jav…

nvm使用-node版本切换-npm版本-node版本异常导致错误

目录什么是nvm?为什么要用它&#xff1f;它改变的是谁的版本号&#xff1f;安装并使用安装前操作安装使用&#xff08;常用命令&#xff09;nvm -hnvm install \<version\> [arch]nvm listnvm use [version] [arch]其他什么是nvm? .nvm是一个node的版本管理工具&#x…

【计算机图形学】扫面转换算法(DDA算法 中点画线算法 Bresenham画线算法)

模块1 扫描转换算法 一 实验目的 编写直线、弧线的光栅扫描转换算法&#xff0c;并对线宽与线形的算法加以探讨用DDA算法、中点画线算法、Bresenham画线算法绘制直线&#xff08;如果键盘输入数据&#xff0c;给出数据值&#xff1b;如果绘制图案&#xff0c;图案中应包含各种…

机器看世界

博主简介 博主是一名大二学生&#xff0c;主攻人工智能研究。感谢让我们在CSDN相遇&#xff0c;博主致力于在这里分享关于人工智能&#xff0c;c&#xff0c;Python&#xff0c;爬虫等方面知识的分享。 如果有需要的小伙伴可以关注博主&#xff0c;博主会继续更新的&#xff0c…