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(null, '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(null, 'A');  // Only this value takes up memory
console.log(sparseArr.get(1000));  // Output: A
console.log(sparseArr.get(999));   // Output: null