搜尋

首頁  >  文章  >  web前端  >  DSA 與 JS：了解 JavaScript 中的自訂陣列資料結構 - 逐步指南

DSA 與 JS：了解 JavaScript 中的自訂陣列資料結構 - 逐步指南

Mary-Kate Olsen
Mary-Kate Olsen原創
2024-09-30 06:18:03658瀏覽

DSA with JS: Understanding Custom Array Data Structure in JavaScript - A Step-by-Step Guide

介紹

陣列是程式設計中的基本資料結構，對於有效組織和儲存資料至關重要。它們允許開發人員透過將元素（例如數字、字串或物件）分組為單一有序結構來管理它們的集合。陣列透過索引提供對元素的輕鬆訪問，使其可用於排序、搜尋和操作資料等各種任務。

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;
}

Resizing (In the case of dynamic resizing)

Time Complexity: O(n) (Linear time) If you were to implement dynamic resizing (doubling the capacity once the array is full), copying elements to a new larger array would take O(n) time because every element has to be moved to a new location. However, this doesn't happen on every push() call, so amortized over many operations, it approaches O(1) per operation.

Space Complexity: O(n) (Linear space) When resizing, a new array with larger capacity is allocated, leading to a linear space complexity based on the number of elements.

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;
  }
}

these are examples of how time and space complexity can be measured for different operations in a custom array implementation. They illustrate the computational cost in terms of time (how long the operation takes) and space (how much memory it uses) based on factors like the size of the array and the type of operation (e.g., push, pop, resizing). These measurements help analyze the efficiency of data structures and algorithms.

Usefulness in coding a javascript script

Custom arrays in JavaScript can be useful in several specific scenarios where you need more control over performance, memory management, or specific behaviors that JavaScript's native array doesn't provide out of the box. Here are a few use cases for custom arrays, along with examples showing how they can provide advantages.

Fixed-Length Array (Optimized Memory Use)

In some cases, you might want an array that has a fixed size, which helps control memory usage more precisely. JavaScript's native array dynamically resizes, but with a custom array, you can allocate a fixed amount of space for efficiency.

Use Case: You are developing a real-time application (e.g., a game or embedded system) where you need strict memory constraints and know exactly how many elements are required.

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

Advantage: Memory is pre-allocated and fixed, which can be beneficial when memory optimization is crucial.

Sparse Array (Efficient for Large, Mostly Empty Arrays)

A sparse array stores only non-null or non-zero elements, which can save memory in cases where an array is large but contains mostly empty or default values.

Use Case: You need to handle a large dataset where only a small percentage of the entries hold values (e.g., managing sparse matrices in scientific computing).

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

Implementing custom arrays in JavaScript gives you the flexibility to optimize for specific use cases like memory efficiency (fixed or sparse arrays), operational efficiency (circular buffers), or even better programming practices (immutable arrays). These optimizations can significantly improve performance and code reliability in applications with specific requirements, helping you go beyond the limitations of native JavaScript arrays.

Comparing Custom Arrays with Native Arrays

When comparing custom arrays with native arrays in JavaScript, it's essential to understand the strengths and weaknesses of each in different contexts. Native arrays are a built-in feature of JavaScript, providing developers with a highly optimized, dynamic data structure that’s easy to use and integrated deeply into the language. Native arrays come with numerous methods such as push(), pop(), map(), and filter(), which make array manipulation straightforward and efficient for most use cases. Their dynamic nature means they automatically resize when new elements are added, which is convenient when you don’t need strict control over memory management or performance optimizations.

On the other hand, custom arrays allow developers to control the internal behavior of the array-like data structures. Custom arrays can be implemented to fit specific performance, memory, or structural requirements that native arrays might not handle well. For instance, if you need a fixed-size array where resizing is not required, or you need a custom resizing mechanism, a custom array implementation would allow you to pre-allocate memory, control the resizing strategy, or even optimize access patterns to achieve constant-time operations.

One key benefit of custom arrays is that they give you direct control over how memory is allocated and how operations are performed. For example, if performance is crucial in a particular algorithm and native array methods introduce overhead, custom implementations can provide fine-tuned efficiency. Custom arrays can also be designed for more specialized use cases, such as circular buffers or sparse arrays, which are not supported natively in JavaScript.

原生數組在大多數常見場景中通常更快，因為它們是直接在 JavaScript 引擎中實現的，利用低階優化。因此，使用其中一種的決定很大程度上取決於應用程式的特定需求，特別是在效能和記憶體管理方面。

最終，自訂陣列實作會加深您對 JavaScript 和電腦科學原理的理解，增強您編寫更有效率、深思熟慮的程式碼的能力，並為您提供在本機抽像不足時優化解決方案的知識。

以上是DSA 與 JS：了解 JavaScript 中的自訂陣列資料結構 - 逐步指南的詳細內容。更多資訊請關注PHP中文網其他相關文章！

JavaScript Array Object NULL if for while Filter using class internal Length map delete JS number default constructor this prototype location position Access
陳述：
本文內容由網友自願投稿，版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容，請聯絡admin@php.cn
上一篇：產品和登陸頁面改進、在里斯本與製作者會面以及組織黑客馬拉松 ✨下一篇：產品和登陸頁面改進、在里斯本與製作者會面以及組織黑客馬拉松 ✨

相關文章

看更多