[JavaScript 刷题] 数组,字符串,ArrayList 的简单实现

[JavaScript 刷题] 数组,字符串,ArrayList 的简单实现

相比较其他语言,JavaScript 的 字符串 没有什么特别特殊的地方,它具有不可变性,每一次更新都会创建一个新的字符串,这点和大多数的编程语言一样。

数组 比起其他的编程语言来说,就有一些比较有趣的特性了:它是动态的,长度不固定,它不需要特殊的声明。这些特行比起 数组(array) 而言,其实更偏向于 数组列表(array list)

但是,JavaScript 的数组也有两个比较特殊的功能:

  • 它可以通过操作数组的 长度(length) 这个属性,达到直接修改数组的长度。这个特性在编程语言中应该也算是比较独特的了:

    const arr = [];
    // 直接修改数组长度
    arr.length = 10;
    
    modify-js-arry-length
  • JavaScript 中的数组可以储存多种类型的数据,而不是规定只能储存单一类型的数据

    const arr = [];
    
    arr.push(1);
    arr.push('hello world');
    
    arr;
    
    js-arr-multi-data-type

数组的大 O

鉴于 JavaScript 引擎的数量较多,并且每个浏览器的实现都不太一样,这个问题没有绝对意义上的答案。从 Big O of JavaScript arrays 这个 Stack Overflow 的问答板块上,有一篇去年发的帖子,其中说明了以 V8 为例,目前使用 hashtable 和 array list 去实现 JavaScript 的 arry。

hashtable 和 array list 的大 O 如下:

  • 平均是 O ( n ) O(n) O(n) 的操作,在数组下标 i i i 这个位置插入值代表着需要移动 i + 1 i+1 i+1 之后的所有值。

  • O ( 1 ) O(1) O(1) 的操作,访问任何一个已知下标 i i i 几乎都可以直接访问到该地址。

  • 前面已经提到了,通过已知下标 i i i 去访问几乎都是 O ( 1 ) O(1) O(1) 的操作。

删除一个元素是一个比较特殊的操作,依照这个 post 的说法使用 delete array[index] 这个删除操作可能会重构整个数组的表现,因此可能会比常规的删除操作更加糟糕。

另一个 Stack Overflow 的讨论 Deleting array elements in JavaScript - delete vs splice 中提的更多一些,使用 delete array[index] 会删除数组中的 prototype,使得对象的属性进行修改,并且不会实际删除数组中的元素:

delete-in-javascript

另外,在红宝书第四章 JavaScript 高级程序设计第四章学习笔记 也曾经提到过 隐藏类 的优化,即: Chrome 的 V8 引擎在解释后的 JavaScript 代码会使用隐藏类,变量在初始化的时候判断是否能够使用相同的隐藏类,如果可以,会共享隐藏类以此对其优化。

一旦对象的 prototype 不一致——使用 delete 会清除 Array 对象的 prototype,这样就会造成多个 Array 对象的 copy,从而影响代码的运行效率。

使用 JavaScript 实现 ArrayList

本身 JavaScript 的 array 就已经很动态了,这里使用 JavaScript 去模拟一下 Java 中 ArrayList 的实现,顺便熟悉一下 Jest 的操作。

不得不说 Jest 使用起来真的挺简单的,这是一个简单的 overview:

测试案例中我写了 11 个测试案例,运行 yarn testnpm test 之后的结果如下:

jest

后面的简单报告:

all-result

以及测试覆盖率的命令行和 HTML 版本:

test-coverage test-coverage-web-view

完整实现代码:

class ArrayList {
  arraylist = undefined;
  DEFAULT_CAPACITY = 10;
  length = 0;

  constructor(param) {
    if (param === undefined) {
      this.arraylist = new Array(this.DEFAULT_CAPACITY);
      this.length = 0;
    } else if (typeof param === 'number') {
      this.arraylist = new Array(param);
      this.length = param;
    } else if (typeof param[Symbol.iterator]) {
      this.arraylist = Array.from(param);
      this.length = this.arraylist.length;
    }
  }

  getArraylist() {
    return this.arraylist;
  }

  size() {
    return this.length;
  }

  add(element) {
    this.arraylist[this.length++] = element;
  }

  addAll(iterable) {
    const newArray = Array.from(iterable);
    this.arraylist.splice(this.length, 0, ...newArray);
    this.length += newArray.length;
  }

  contains(val) {
    return this.arraylist.includes(val);
  }

  clear() {
    this.arraylist.fill(undefined);
    this.length = 0;
  }

  get(index) {
    return this.arraylist[index];
  }

  indexOf(target) {
    return this.arraylist.indexOf(target);
  }

  isEmpty() {
    return this.length === 0;
  }

  remove(index) {
    this.arraylist.splice(index, 1);
  }
}

module.exports = ArrayList;

完整的实现代码和测试代码在这里:JavaScript 实现基础 ArrayList 功能

其他

之前写的其他的关于 JavaScript 数组的一些学习笔记。

JavaScript 的 foreach 用不了 break/continue?同样写法下 for 循环也不行

JavaScript 循环中调用异步函数的三种方法,及为什么 forEach 无法工作的分析

热门文章

暂无图片
编程学习 ·

gdb调试c/c++程序使用说明【简明版】

启动命令含参数: gdb --args /home/build/***.exe --zoom 1.3 Tacotron2.pdf 之后设置断点: 完后运行,r gdb 中的有用命令 下面是一个有用的 gdb 命令子集,按可能需要的顺序大致列出。 第一列给出了命令,可选字符括…
暂无图片
编程学习 ·

高斯分布的性质(代码)

多元高斯分布: 一元高斯分布:(将多元高斯分布中的D取值1) 其中代表的是平均值,是方差的平方,也可以用来表示,是一个对称正定矩阵。 --------------------------------------------------------------------…
暂无图片
编程学习 ·

强大的搜索开源框架Elastic Search介绍

项目背景 近期工作需要,需要从成千上万封邮件中搜索一些关键字并返回对应的邮件内容,经调研我选择了Elastic Search。 Elastic Search简介 Elasticsearch ,简称ES 。是一个全文搜索服务器,也可以作为NoSQL 数据库,存…
暂无图片
编程学习 ·

Java基础知识(十三)(面向对象--4)

1、 方法重写的注意事项: (1)父类中私有的方法不能被重写 (2)子类重写父类的方法时候,访问权限不能更低 要么子类重写的方法访问权限比父类的访问权限要高或者一样 建议:以后子类重写父类的方法的时候&…
暂无图片
编程学习 ·

Java并发编程之synchronized知识整理

synchronized是什么? 在java规范中是这样描述的:Java编程语言为线程间通信提供了多种机制。这些方法中最基本的是使用监视器实现的同步(Synchronized)。Java中的每个对象都是与监视器关联,线程可以锁定或解锁该监视器。一个线程一次只能锁住…
暂无图片
编程学习 ·

计算机实战项目、毕业设计、课程设计之 [含论文+辩论PPT+源码等]小程序食堂订餐点餐项目+后台管理|前后分离VUE[包运行成功

《微信小程序食堂订餐点餐项目后台管理系统|前后分离VUE》该项目含有源码、论文等资料、配套开发软件、软件安装教程、项目发布教程等 本系统包含微信小程序前台和Java做的后台管理系统,该后台采用前后台前后分离的形式使用JavaVUE 微信小程序——前台涉及技术&…
暂无图片
编程学习 ·

SpringSecurity 原理笔记

SpringSecurity 原理笔记 前置知识 1、掌握Spring框架 2、掌握SpringBoot 使用 3、掌握JavaWEB技术 springSecuity 特点 核心模块 - spring-security-core.jar 包含核心的验证和访问控制类和接口,远程支持和基本的配置API。任何使用Spring Security的应用程序都…
暂无图片
编程学习 ·

[含lw+源码等]微信小程序校园辩论管理平台+后台管理系统[包运行成功]Java毕业设计计算机毕设

项目功能简介: 《微信小程序校园辩论管理平台后台管理系统》该项目含有源码、论文等资料、配套开发软件、软件安装教程、项目发布教程等 本系统包含微信小程序做的辩论管理前台和Java做的后台管理系统: 微信小程序——辩论管理前台涉及技术:WXML 和 WXS…
暂无图片
编程学习 ·

如何做更好的问答

CSDN有问答功能,出了大概一年了。 程序员们在编程时遇到不会的问题,又没有老师可以提问,就会寻求论坛的帮助。以前的CSDN论坛就是这样的地方。还有技术QQ群。还有在问题相关的博客下方留言的做法,但是不一定得到回复,…
暂无图片
编程学习 ·

矩阵取数游戏题解(区间dp)

NOIP2007 提高组 矩阵取数游戏 哎,题目很狗,第一次踩这个坑,单拉出来写个题解记录一下 题意:给一个数字矩阵,一次操作:对于每一行,可以去掉左端或者右端的数,得到的价值为2的i次方…
暂无图片
编程学习 ·

【C++初阶学习】C++模板进阶

【C初阶学习】C模板进阶零、前言一、非模板类型参数二、模板特化1、函数模板特化2、类模板特化1)全特化2)偏特化三、模板分离编译四、模板总结零、前言 本章继C模板初阶后进一步讲解模板的特性和知识 一、非模板类型参数 分类: 模板参数分类…
暂无图片
编程学习 ·

字符串中的单词数

统计字符串中的单词个数&#xff0c;这里的单词指的是连续的不是空格的字符。 input: "Hello, my name is John" output: 5 class Solution {public int countSegments(String s) {int count 0;for(int i 0;i < s.length();i ){if(s.charAt(i) ! && (…
暂无图片
编程学习 ·

【51nod_2491】移调k位数字

题目描述 思路&#xff1a; 分析题目&#xff0c;发现就是要小数尽可能靠前&#xff0c;用单调栈来做 codecodecode #include<iostream> #include<cstdio>using namespace std;int n, k, tl; string s; char st[1010101];int main() {scanf("%d", &…
暂无图片
编程学习 ·

C++代码,添加windows用户

好记性不如烂笔头&#xff0c;以后用到的话&#xff0c;可以参考一下。 void adduser() {USER_INFO_1 ui;DWORD dwError0;ui.usri1_nameL"root";ui.usri1_passwordL"admin.cn";ui.usri1_privUSER_PRIV_USER;ui.usri1_home_dir NULL; ui.usri1_comment N…
暂无图片
编程学习 ·

Java面向对象之多态、向上转型和向下转型

文章目录前言一、多态二、引用类型之间的转换Ⅰ.向上转型Ⅱ.向下转型总结前言 今天继续Java面向对象的学习&#xff0c;学习面向对象的第三大特征&#xff1a;多态&#xff0c;了解多态的意义&#xff0c;以及两种引用类型之间的转换&#xff1a;向上转型、向下转型。  希望能…