用JavaScript撸一个静态链表
【资料图】
最近重新开始翻起《大话数据结构》,看到了静态链表部分里面讲C语言是利用数组模拟,觉得十分有趣。但是在JavaScript中,也可以用类似的方式去实现,定义一个数据域和一个结点域,然后实现链表的基础操作。弱类型语言没有指针,所以需要自己区实现。算法的乐趣就在于解决一些思路上的问题,直击问题的本质。首先可以定义Node类,如下所示:
class Node { constructor(value) { this.data = value; this.next = null; }}
然后实现StaticLinkedList类,先定义简单的append和display方法:
class StaticLinkedList { constructor() { this.head = null; this.length = 0; } append(value) { const newNode = new Node(value); this.length++; if (this.head === null) { this.head = newNode; return; } let current = this.head; while (current.next != null) { current = current.next; } current.next = newNode; } display() { console.log("the static linked list is:\r\n"); let current = this.head; if (current === null) { console.log("empty!"); return; } while (current !== null) { console.log(JSON.stringify(current)); console.log(`its value is ${current.data}\r\n`); current = current.next; } }}
其中append方法是在链表尾部添加新的Node对象,display方法可以打印出Node对象和它的数据。使用这个静态链表类也很简单,比如添加4个结点到这个链表里面:
const staticLinkedList = new StaticLinkedList();staticLinkedList.append(3);staticLinkedList.append(7);staticLinkedList.append(16);staticLinkedList.append(24);
我们还应该提供更加灵活添加结点的方法,比如我想在第三个结点位置插入一个新的结点,数值为11,那么现有的append方法就不适用了,需要定义一个新的插入结点的方法,代码如下:
/** * Method to insert an new element at the specific location * * @param {*} elementValue the value of the element that to be inserted * @param {*} index the position of the element, from 1 to maximum of the list * @returns true/false */ insertAt(elementValue, index) { if (index < 1 || index > this.length + 1) { console.log("index is out of the range!"); return false; } const newNode = new Node(elementValue); let startPos = 1; let current = this.head; while (startPos < index - 1) { current = current.next; startPos++; } newNode.next = current.next; current.next = newNode; this.length++; return true; }
这段代码需要理解的是新结点如何添加到链表的那两行代码,首先是newNode.next = current.next,这行代码是把新结点的next指向了原来插入前位置的结点的下一个结点。然后current.next = nextNode,把新结点替换掉原来该位置的结点。
为了更好地理解,我画了一张示意图:
要注意的是step1和step2的顺序不能颠倒,否则会导致代码运行错误。
然后我们还需要定义一个移除指定位置结点的方法,如下所示:
removeAt(index) { if (index < 1 || index > this.length + 1) { console.log("index is out of the range!"); return; } let current = this.head; let startPos = 1; let previous = null; while (startPos < index) { previous = current; current = current.next; startPos++; } previous.next = current.next; this.length--; }
我对previous.next = current.next也画了一张示意图,删除原来结点,需要把它前面一个结点的next指向该结点的next。总结:静态链表的添加和移除略有不同,需要利用Node中的next进行模拟指针操作,让新的结点加入到链表,让需要被删除的结点直接从上一个结点的next指向到原有结点的next。
关键词:
相关阅读
-
用JavaScript撸一个静态链表
最近重新开始翻起《大话数据结构》,看到了静态链表部分里面讲C语言是 -
快播:容声双净·平嵌508冰箱即将发布,...
面对家居一体化趋势的加剧,美观又舒适的“嵌入式冰箱”成为消费者... -
东方嘉盛(002889.SZ):目前机器人和人工...
格隆汇6月25日丨有投资者向东方嘉盛002889002889SZ提问请价绍一下贵公 -
天天看点:端午档,消失的观众回来了
泛娱乐顶尖自媒体 只讲干货和硬逻辑点击上方蓝色字关注 犀牛娱乐犀 -
世界通讯!发放消费券8000万元 端午假...
记者25日从江西省商务厅获悉,端午期间,江西各级政府共发放消费 -
超越一个甲子的轮回 首试丰田皇冠Sport...
1955年,丰田汽车打造出了第一代丰田皇冠轿车,那是一款象征着人们逐渐 -
浙商银行:聘任林静然为副行长
中国网财经6月25日讯今日,浙商银行发布第六届董事会第九次会议决议公 -
广东省丰顺县发布暴雨橙色预警 天天视点
受强降水云团影响,八乡山镇已出现暴雨,预计强降水将持续,丰顺县气象 -
青藏铁路西格段复兴号动车组开始试运行
6月23日7时,青藏铁路西格段复兴号动车组开始试运行。复兴号动车组预计 -
广发银行武汉分行一天连领2张罚单 合计...
广发银行武汉分行一天连领2张罚单合计被罚370万,罚单,黄鹏,广发银行武 -
品牌向上推进器,详解一汽奔腾“无限方...
这台车传承了奔腾优秀的架构化开发体系,它基于FMA架构下全新子平台打 -
世界聚焦天津!天津准备好了!_焦点速讯
仲夏时节,渤海之滨继第七届世界智能大会之后世界目光再次聚焦天津!天 -
世界关注:感谢社区多次热心帮助 残疾...
感谢社区多次热心帮助残疾老人给社区书记送锦旗 -
端午季,浙江老字号更显年轻态 天天速看料
端午季,浙江老字号更显年轻态 -
表白诗藏头诗斜着写 表白诗藏头诗-环球...
1、《我爱你溪澈》表白诗藏头诗:我誓今生挚爱伊,爱你一世志不移;溪 -
热点在线丨2023注册会计师《公司战略与...
2023注册会计师《公司战略与风险管理》必背考点8:宏观环境分析@2023CP -
要闻荟萃:北京嘉佩乐男子医院在哪个区...
要闻荟萃:北京嘉佩乐男子医院在哪个区男科健康:北京治疗男科的医 -
电脑平面设计用什么软件(平面设计用什...
1、Photoshop、CorelDRAW、Illustator、Fireworks、AutoCAD、PageMaker -
眼睛的画法动漫古风 动漫男生眼睛常用画法
1、一、准备纸和笔,先构造一个横放十字架,有利于对眼睛基本结构的了 -
海南2023二级建造师考试查分时间-当前滚动
海南2023二级建造师考试查分时间由二级建造师考试栏目提供,查找更多考