JavaScript数据结构与算法——链表

news/2024/2/22 19:01:05

1.链表数据结构

链表存储有序的元素集合,但不同于数组,链表中的元素咋内存中并不是连续放置的每个元素有一个存储元素本身的节点和一个指向下一个元素的引用组成。下图展示了一个链表的结构:
clipboard.png
链表的优点:
链表是很常用的一种数据结构,不需要初始化容量,可以任意加减元素;
添加或者删除元素时只需要改变前后两个元素结点的指针域指向地址即可,所以添加,删除很快;

缺点:
因为含有大量的指针域,占用空间较大;
查找元素需要遍历链表来查找,非常耗时。

适用场景:
数据量较小,需要频繁增加,删除操作的场景

2.创建链表

function LinkedList() {// 创建一个node类,表示将要加入的项 element表示要添加的值,next指向列表中下一个节点项的指针let Node = function(element) {this.element = element;this.next = null;}let length = 0;let head = null;// 下面声明链表的方法// 1.向列表尾部添加一个新的项this.append = function(element) {let node = new Node(element);current;// 列表为空,添加的是第一个元素if(head === null) {head = node; // 列表不为空,向其追加   } else {current = head;// 循环列表,直到找到最后一项while(current.next) {current = current.next;}// 找到最后一项,将其next赋为node,建立链接current.next = node;}// 更新列表长度length++;}// 2.从列表中移除元素this.removeAt = function(position) {// 检查position是否超出链表范围if(position > -1 && position < length) {let current = head,previous,index = 0;// 移除第一个元素if(position === 0 ) {head = current.next;} else {// 循环到指定位置,找到该位置的 previous和currentwhile(index++ < position) {previous = current;current = current.next;}// 将previous与current的下一项链接起来:跳过currentprevious.next = current.next;}    // 链表长度减一length--;// 返回被删除项return current.element;} else {// 不是有效位置,返回nullreturn null}}// 3.在任意位置插入元素this.insert = function(element, position) {//判断是否超过链表范围if (position >= 0 && position<= length) {let node = new Node(element),current = head,previous,index = 0;// 在首位插入元素if (position === 0 ) {node.next = current;head = node;} else{// x循环到position应该添加的位置,取出previous和currentwhile(index++ < position) {previous = current;current = current.next;}// 在previous和current间插入node.next = current;previous.next = node;};    // 更新链表长度length++;return true;} else{return false;};}//4. 把LinkedList对象转化成字符串this.toString = function() {let current = head,string = '';while(current) {string += current.element + (current.next ? 'n' : '');current = current.next;}  return string;  }//5.链表中是否存在某个值this.indexOf = function(element) {let current = head,index = 0;while(current) {if(element === current.element) {return index;}index++;current = current.next;}  return -1; } //6.通过element实现remove元素this.remove = function(element) {let index = this.indexOf(element);return this.removeAt(index);}//7.isEmpty size getHead方法this.isEmpty = function() {return length === 0; }this.size = function() {return length;}this.getHead = function() {return head;}    
}

https://dhexx.cn/news/show-317843.html

相关文章

【转】Android ProgressDialog的使用

原文网址&#xff1a;http://blog.csdn.net/sjf0115/article/details/7255280 版权声明&#xff1a;本文为博主原创文章&#xff0c;未经博主允许不得转载。 <1>简介 ProgressDialog是AlertDialog类的一个扩展&#xff0c;可以为一个未定义进度的任务显示一个旋转轮形状的…

Reddit重写其iOS应用,改进性能、模块化和测试

去年&#xff0c;Reddit一直在努力改进其iOS应用的性能&#xff0c;同时使其适合更快的迭代周期&#xff0c;改善其测试覆盖率&#xff0c;提高其可扩展性。所有这些都是通过把应用原来的MVC架构改造成Model-View-Presenter&#xff08;MVP&#xff09;架构实现的。\\原来的MVC…

为什么用Immutable.js代替普通js对象?

FROM URL:https://juejin.im/post/59df1a69f265da43346ee96a 将数据视为不可变&#xff0c;将给你带来很多好处。事实上&#xff0c;这是也React背后的原理&#xff1a;React的元素是不可变的。但是用Immutable.js有什么好处呢&#xff1f; 假定有一个非常巨大的对象… 这里有1…

2016 杭州区域赛补题

A - ArcSofts Office Rearrangement HDU - 5933 题意&#xff1a;现在有n个办公区&#xff0c;每个办公区内有a[i]个办公人员&#xff0c;现在要将这些人均匀的分布在m个办公区内&#xff0c;每个办公区人员必须等价。现在有两个操作&#xff0c;1操作&#xff0c;可以将相邻的…

聊聊flink的ParameterTool

为什么80%的码农都做不了架构师&#xff1f;>>> 序 本文主要研究一下flink的ParameterTool 实例 fromPropertiesFile String propertiesFilePath "/home/sam/flink/myjob.properties"; ParameterTool parameter ParameterTool.fromPropertiesFile(prop…

elasticsearch系列六:聚合分析(聚合分析简介、指标聚合、桶聚合)

一、聚合分析简介 1. ES聚合分析是什么&#xff1f; 聚合分析是数据库中重要的功能特性&#xff0c;完成对一个查询的数据集中数据的聚合计算&#xff0c;如&#xff1a;找出某字段&#xff08;或计算表达式的结果&#xff09;的最大值、最小值&#xff0c;计算和、平均值等。E…

周大侠啊 进击的 JavaScript(一) 之 类型转换

原文链接&#xff1a;周大侠啊 进击的 JavaScript&#xff08;一&#xff09; 之 类型转换 说起 js 类型转换&#xff0c;都是头疼吧&#xff0c;晕晕的&#xff0c;但是不行啊&#xff0c;这东西很重要滴&#xff01; 基础知识 JavaScript的数据类型分为六种&#xff0c;分别为…

兰州大学计算机考研生源,兰州大学推免生统计,只有5人来自985高校,既无奈又现实...

各大高校2020年的推免研究生工作已经基本结束&#xff0c;根据各个高校官网统计的数据来看&#xff0c;今年的推免研究生比去年普遍增多&#xff0c;总体上来说&#xff0c;各大985高校更喜欢推免的学生&#xff0c;也更喜欢985或者211高校的本科生。但是&#xff0c;我国有一所…

C# Json 和 Xml的互转

首先第一步我们需要引用微软的一个类库&#xff0c;Newtonsoft.Json.dll 第二步我们需要using system.XML、WEB以及using Newtonsoft.Json 然后获取Xml字符串strXml 和 Json字符串strJson 1、Json转换为XML XmlDocument docj JsonConvert.DeserializeXmlNode(strJson);string …

计算机控制面板设置密码,如何设置修改电脑的开机密码

如何设置修改电脑的开机密码腾讯视频/爱奇艺/优酷/外卖 充值4折起我们为了保护我们的隐私&#xff0c;经常会习惯给我们的电脑设置开机密码&#xff0c;但是想要更改密码的时候&#xff0c;该怎么操作呢&#xff1f;今天就跟大家介绍一下如何设置修改电脑的开机密码的具体操作步…