DSA 与 JS：了解 JavaScript 中的自定义数组数据结构 - 分步指南

class customarray {  constructor() {    this.data = {};  // object to hold array data    this.length = 0; // length of the array  }  // method to add an element at the end  push(element) {    this.data[this.length] = element;    this.length++;    return this.length;  }  // method to remove the last element  pop() {    if (this.length === 0) return undefined;    const lastelement = this.data[this.length - 1];    delete this.data[this.length - 1];    this.length--;    return lastelement;  }  // method to get the element at a specific index  get(index) {    return this.data[index];  }  // method to delete an element at a specific index  delete(index) {    const item = this.data[index];    this.shiftitems(index);  // shift items after deletion    return item;  }  // internal method to shift items after deletion  shiftitems(index) {    for (let i = index; i <h3>      解释：</h3><ol><li><p><strong>构造函数（</strong>构造函数）：初始化一个空对象data，并将初始长度设置为0。这个对象（数据）将充当数组的内部存储。</p><p><span>立即学习</span>“<a href="https://pan.quark.cn/s/c1c2c2ed740f" style="text-decoration: underline !important; color: blue; font-weight: bolder;" rel="nofollow" target="_blank">Java免费学习笔记（深入）</a>”；</p></li><li><p><strong>push (</strong>push())：通过将新元素分配给下一个可用索引（由 this.length 跟踪）来​​将新元素添加到数组中，然后增加长度。</p> </li><li><p><strong>pop (</strong>pop())：通过删除最后一个索引并减少长度来删除数组中的最后一个元素。这模仿了 array.prototype.pop() 方法的行为。</p></li><li><p><strong>get (</strong>get())：获取特定索引处的值。它模仿通过索引访问数组中的元素（例如 arr[1]）。</p></li><li><p><strong>delete (</strong>delete())：删除给定索引处的元素，并将其余元素向左移动以填补空白，类似于 array.prototype.splice () 会在原生 javascript 数组中执行。</p></li><li><p><strong>shift items (</strong>shiftitems())：删除一个元素后，此方法将删除索引后的所有元素向左移动一个位置，这是维持类似数组的行为所必需的.</p></li></ol><h2>      <strong>时间复杂度和性能</strong></h2><p>性能测量的主题采用 big o 表示法。所以，如果你认为你需要研究时间复杂度和性能，你可以阅读这篇文章来掌握这些概念。</p><h2>      推()操作</h2><p><strong>时间复杂度</strong>：o(1)（恒定时间）push() 方法在数组末尾追加一个元素。由于它只是将值放置在当前长度索引处，因此它会在恒定时间内执行，这意味着该操作不依赖于数组的大小。</p><p><strong>空间复杂度</strong>：o(1)（恒定空间）空间复杂度是恒定的，因为无论数组大小如何，它只添加一个新元素。<br></p><pre class="brush:php;toolbar:false">push(value) {  this.data[this.length] = value; // o(1)  this.length++;}

pop() {  const lastitem = this.data[this.length - 1]; // o(1)  delete this.data[this.length - 1];  this.length--;  return lastitem;}

class resizablearray {  constructor() {    this.data = {};    this.length = 0;    this.capacity = 2; // initial capacity  }  push(value) {    if (this.length === this.capacity) {      this._resize(); // resize array when it's full    }    this.data[this.length] = value;    this.length++;  }  _resize() {    const newdata = {};    this.capacity *= 2;    for (let i = 0; i <p>这些是如何在自定义数组实现中测量不同操作的<strong>时间和空间复杂度</strong>的示例。它们根据数组大小和操作类型（例如，推送、弹出、调整大小）等因素，以时间（操作需要多长时间）和空间（使用多少内存）来说明计算成本。这些测量有助于分析数据结构和算法的效率。</p><h2>      <strong>编写 javascript 脚本的有用性</strong></h2><p>javascript 中的自定义数组在多种特定场景中非常有用，在这些场景中，您需要对性能、内存管理或 javascript 原生数组未提供的开箱即用的特定行为进行更多控制。以下是自定义数组的一些<strong>用例</strong>，以及展示它们如何提供优势的示例。</p><h2>      固定长度数组（优化内存使用）</h2><p>在某些情况下，您可能需要一个具有固定大小的数组，这有助于更精确地控制内存使用情况。 javascript 的原生数组会动态调整大小，但使用自定义数组，您可以分配固定数量的空间以提高效率。</p><p>用例：您正在开发一个实时应用程序（例如游戏或嵌入式系统），您需要严格的内存限制并确切知道需要多少个元素。<br></p><pre class="brush:php;toolbar:false">class fixedarray {  constructor(size) {    this.data = new array(size); // pre-allocating memory    this.length = size;  }  set(index, value) {    if (index &gt;= this.length) throw new error('index out of bounds');    this.data[index] = value;  }  get(index) {    if (index &gt;= this.length) throw new error('index out of bounds');    return this.data[index];  }}const fixedarr = new fixedarray(5);fixedarr.set(0, 'a');console.log(fixedarr.get(0));  // output: a

class SparseArray {  constructor() {    this.data = {};  }  set(index, value) {    if (value !== null && value !== undefined) {      this.data[index] = value;    }  }  get(index) {    return this.data[index] || null; // Return null if the value isn't set  }}const sparseArr = new SparseArray();sparseArr.set(1000, 'A');  // Only this value takes up memoryconsole.log(sparseArr.get(1000));  // Output: Aconsole.log(sparseArr.get(999));   // Output: null