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

你在学习文章相关的知识吗？本文《DSA 与 JS：了解 JavaScript 中的自定义数组数据结构 - 分步指南》，主要介绍的内容就涉及到，如果你想提升自己的开发能力，就不要错过这篇文章，大家要知道编程理论基础和实战操作都是不可或缺的哦！

介绍

数组是编程中的基本数据结构，对于有效组织和存储数据至关重要。它们允许开发人员通过将元素（例如数字、字符串或对象）分组为单个有序结构来管理元素集合。数组通过索引提供对元素的轻松访问，使其可用于排序、搜索和操作数据等各种任务。

javascript 的原生数组功能强大且灵活，内置数据结构，可以根据需要动态增长或收缩。与低级语言中的数组通常具有固定大小不同，javascript 数组可以处理不同的数据类型并自动调整其大小。 javascript 提供了许多内置方法，这些方法抽象了管理内存、调整大小和元素访问的复杂性。这些方法简化了数组操作，使开发人员能够专注于解决问题，而不必担心底层实现。 javascript 数组经过 v8 等现代引擎的优化，使其在大多数用例中都具有高性能。

虽然 javascript 提供了方便且高度优化的数组实现，但构建自定义数组可以帮助您了解内存管理、动态调整大小和高效数据访问的机制。通过构建自定义数组，开发人员不仅可以提高解决问题的能力，还可以更深入地了解提高编程效率的核心原理，为更高级的数据结构和算法挑战做好准备。

构建自定义数组

让我向您展示一个如何使用 javascript 中的类编写数组的示例。这种方法更加底层，手动模拟数组的行为。要在 javascript 中构建自定义数组，您可以创建一个模仿 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 < this.length - 1; i++) {
      this.data[i] = this.data[i + 1];
    }
    delete this.data[this.length - 1];
    this.length--;
  }
}

// example usage
const myarray = new customarray();
myarray.push(10);   // [10]
myarray.push(20);   // [10, 20]
myarray.push(30);   // [10, 20, 30]

console.log(myarray.get(1));  // output: 20

myarray.delete(1);   // [10, 30]
console.log(myarray); // { data: { '0': 10, '1': 30 }, length: 2 }

myarray.pop();  // remove last element [10]
console.log(myarray); // { data: { '0': 10 }, length: 1 }

解释：

1. 构造函数（构造函数）：初始化一个空对象data，并将初始长度设置为0。这个对象（数据）将充当数组的内部存储。

2. push (push())：通过将新元素分配给下一个可用索引（由 this.length 跟踪）来​​将新元素添加到数组中，然后增加长度。

3. pop (pop())：通过删除最后一个索引并减少长度来删除数组中的最后一个元素。这模仿了 array.prototype.pop() 方法的行为。

4. get (get())：获取特定索引处的值。它模仿通过索引访问数组中的元素（例如 arr[1]）。

5. delete (delete())：删除给定索引处的元素，并将其余元素向左移动以填补空白，类似于 array.prototype.splice () 会在原生 javascript 数组中执行。

6. shift items (shiftitems())：删除一个元素后，此方法将删除索引后的所有元素向左移动一个位置，这是维持类似数组的行为所必需的.

时间复杂度和性能

性能测量的主题采用 big o 表示法。所以，如果你认为你需要研究时间复杂度和性能，你可以阅读这篇文章来掌握这些概念。

推()操作

时间复杂度：o(1)（恒定时间）push() 方法在数组末尾追加一个元素。由于它只是将值放置在当前长度索引处，因此它会在恒定时间内执行，这意味着该操作不依赖于数组的大小。

空间复杂度：o(1)（恒定空间）空间复杂度是恒定的，因为无论数组大小如何，它只添加一个新元素。

push(value) {
  this.data[this.length] = value; // o(1)
  this.length++;
}

pop() 操作

时间复杂度：o(1)（恒定时间） pop() 方法删除最后一个元素，这涉及访问最后一个索引并调整长度。这也是在恒定时间内完成的。

空间复杂度：o(1)（恒定空间）不使用额外的内存，仅删除最后一个元素。

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

调整大小（动态调整大小的情况下）

时间复杂度：o(n)（线性时间）如果要实现动态调整大小（数组满后将容量加倍），将元素复制到新的更大数组将需要 o(n ）时间，因为每个元素都必须移动到新位置。然而，这不会在每次调用 push() 时发生，因此分摊到许多操作上，每个操作接近 o(1)。

空间复杂度：o(n)（线性空间）调整大小时，会分配一个容量更大的新数组，从而导致基于元素数量的线性空间复杂度。

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 < this.length; i++) {
      newdata[i] = this.data[i]; // o(n) operation
    }
    this.data = newdata;
  }
}

这些是如何在自定义数组实现中测量不同操作的时间和空间复杂度的示例。它们根据数组大小和操作类型（例如，推送、弹出、调整大小）等因素，以时间（操作需要多长时间）和空间（使用多少内存）来说明计算成本。这些测量有助于分析数据结构和算法的效率。

编写 javascript 脚本的有用性

javascript 中的自定义数组在多种特定场景中非常有用，在这些场景中，您需要对性能、内存管理或 javascript 原生数组未提供的开箱即用的特定行为进行更多控制。以下是自定义数组的一些用例，以及展示它们如何提供优势的示例。

固定长度数组（优化内存使用）

在某些情况下，您可能需要一个具有固定大小的数组，这有助于更精确地控制内存使用情况。 javascript 的原生数组会动态调整大小，但使用自定义数组，您可以分配固定数量的空间以提高效率。

用例：您正在开发一个实时应用程序（例如游戏或嵌入式系统），您需要严格的内存限制并确切知道需要多少个元素。

class fixedarray {
  constructor(size) {
    this.data = new array(size); // pre-allocating memory
    this.length = size;
  }

  set(index, value) {
    if (index >= this.length) throw new error('index out of bounds');
    this.data[index] = value;
  }

  get(index) {
    if (index >= 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 memory
console.log(sparseArr.get(1000));  // Output: A
console.log(sparseArr.get(999));   // Output: null

在 javascript 中实现 自定义数组 可以让您灵活地针对特定用例进行优化，例如内存效率（固定或稀疏数组）、操作效率（循环缓冲区），甚至更好的编程实践（不可变数组） 。这些优化可以显着提高具有特定要求的应用程序的性能和代码可靠性，帮助您超越原生 javascript 数组的限制。

自定义数组与原生数组的比较

在 javascript 中比较自定义数组与原生数组时，了解每种数组在不同上下文中的优点和缺点至关重要。本机数组是 javascript 的内置功能，为开发人员提供高度优化的动态数据结构，该结构易于使用并深入集成到该语言中。原生数组带有多种方法，例如push()、pop()、map()和filter()，这使得数组操作在大多数用例中变得简单而高效。它们的动态特性意味着它们会在添加新元素时自动调整大小，这在您不需要严格控制内存管理或性能优化时非常方便。

另一方面，自定义数组允许开发人员控制类似数组的数据结构的内部行为。可以实现自定义数组来满足本机数组可能无法很好处理的特定性能、内存或结构要求。例如，如果您需要一个不需要调整大小的固定大小数组，或者需要自定义调整大小机制，则自定义数组实现将允许您预先分配内存、控制调整大小策略，甚至优化访问模式以实现恒定时间操作。

自定义数组的一个主要好处是它们使您可以直接控制内存的分配方式以及操作的执行方式。例如，如果性能在特定算法中至关重要，并且本机数组方法会带来开销，则自定义实现可以提供微调的效率。自定义数组还可以设计用于更专门的用例，例如循环缓冲区或稀疏数组，这些在 javascript 中本机不支持。

原生数组在大多数常见场景中通常更快，因为它们是直接在 javascript 引擎中实现的，利用低级优化。因此，决定使用其中一种在很大程度上取决于应用程序的具体需求，特别是在性能和​​内存管理方面。

最终，自定义数组实现会加深您对 javascript 和计算机科学原理的理解，增强您编写更高效、深思熟虑的代码的能力，并为您提供在本机抽象不足时优化解决方案的知识。

文中关于的知识介绍，希望对你的学习有所帮助！若是受益匪浅，那就动动鼠标收藏这篇《DSA 与 JS：了解 JavaScript 中的自定义数组数据结构 - 分步指南》文章吧，也可关注golang学习网公众号了解相关技术文章。