Lesson 02-Data Structures – Arrays

Definition and Characteristics of Arrays

In JavaScript, an array is a special type of object used to store an ordered collection of data. Unlike arrays in most programming languages, JavaScript arrays can contain elements of different types, such as numbers, strings, objects, or even other arrays.

Arrays are stored contiguously in memory, which allows element access via index with a time complexity of O(1). Array indices start at 0, consistent with most programming languages. For example, array[0] accesses the first element of an array.

JavaScript arrays are dynamic, meaning their size can change at any time. When adding elements to an array, if the current size is insufficient, the array automatically expands its capacity. This dynamic nature makes arrays particularly useful for handling data collections of uncertain size.

Array characteristics include:

  • Quick access to elements via indices
  • Dynamic modification of array content using methods
  • Support for multiple iteration methods to process elements
  • Ability to nest arrays to form multidimensional arrays

There are several ways to create arrays in JavaScript:

// Using array literal
let arr1 = [1, 2, 3, 4, 5];

// Using Array constructor
let arr2 = new Array(1, 2, 3, 4, 5);

// Creating an empty array of specified length
let arr3 = new Array(5); // Note: Creates an empty array of length 5, not containing 5 undefined elements

// Using Array.of method (ES6)
let arr4 = Array.of(1, 2, 3, 4, 5); // Creates an array containing [1, 2, 3, 4, 5]

// Using Array.from method to create an array from an array-like or iterable object (ES6)
let arr5 = Array.from('hello'); // ['h', 'e', 'l', 'l', 'o']

Note that using new Array(length) requires caution, as it creates a sparse array of the specified length with empty slots, not an array containing the specified number of undefined elements.

Implementation of Arrays in JavaScript

Internally, JavaScript arrays are typically implemented using a combination of hash tables and dynamic arrays. This implementation allows arrays to maintain O(1) index access while supporting non-integer indices and dynamic element addition.

Modern JavaScript engines (e.g., V8) highly optimize arrays, employing different storage strategies based on usage patterns:

  1. Fast Mode:
    • Used when the array is filled with contiguous integer indices and has no holes
    • Stored as a contiguous memory block, similar to traditional arrays
    • Offers the fastest index access
  2. Slow Mode:
    • Used when the array contains non-integer indices or holes
    • Implemented as a hidden hash table
    • Slower index access
  3. Doubly Typed Arrays:
    • For arrays containing elements of the same type, the engine may use a more optimized storage format
    • For example, arrays of pure numbers may use a more compact memory layout

The memory layout of an array can be simplified into the following components:

  • Array Header: Stores metadata such as length, capacity, etc.
  • Element Storage: Stores the actual array elements
  • Expansion/Contraction Mechanism: When the array size exceeds capacity, a larger memory space is allocated, and elements are copied

The expansion strategy typically uses a “doubling” approach, where the new capacity is twice the current capacity when the array is full (specific implementations may vary). This strategy balances memory usage and performance in most cases.

Static Arrays vs. Dynamic Arrays

Static and dynamic arrays are two different array implementation concepts. Although JavaScript arrays are dynamic, understanding both concepts helps in grasping how arrays work.

Static Arrays

Static arrays are a common implementation in traditional programming languages, with a fixed size determined at creation. Characteristics of static arrays include:

  • Memory Allocation: Allocated in the stack or a contiguous block of heap memory with a fixed size
  • Fast Access: Due to contiguous memory, element addresses can be calculated directly via offsets
  • Fixed Size: Once created, the size cannot be changed without creating a new array and copying elements

Pseudocode for a static array:

// Pseudocode: Static array implementation
class StaticArray {
  constructor(size) {
    this.size = size;
    this.storage = new Array(size); // Actual memory allocation
  }
  
  get(index) {
    if (index < 0 || index >= this.size) throw new Error("Index out of bounds");
    return this.storage[index];
  }
  
  set(index, value) {
    if (index < 0 || index >= this.size) throw new Error("Index out of bounds");
    this.storage[index] = value;
  }
}

The main drawback of static arrays is their fixed size, making them unsuitable for datasets of unknown or dynamically changing sizes. Additionally, if the capacity is underestimated, frequent memory reallocation and data copying may be required.

Dynamic Arrays

Dynamic arrays are designed to address the fixed-size limitation of static arrays, and JavaScript arrays are dynamic. Characteristics of dynamic arrays include:

  • Automatic Expansion: When capacity is insufficient, a larger storage space is allocated, and elements are copied
  • Flexible Size: The array size can be adjusted dynamically as needed
  • Amortized Cost: While expansion operations may take O(n) time, the amortized cost per element operation is O(1)

Simplified implementation of a dynamic array:

class DynamicArray {
  constructor(initialCapacity = 10) {
    this.capacity = initialCapacity;
    this.size = 0;
    this.storage = new Array(this.capacity);
  }
  
  get(index) {
    if (index < 0 || index >= this.size) throw new Error("Index out of bounds");
    return this.storage[index];
  }
  
  set(index, value) {
    if (index < 0 || index >= this.size) throw new Error("Index out of bounds");
    this.storage[index] = value;
  }
  
  push(value) {
    if (this.size === this.capacity) {
      this.resize(2 * this.capacity);
    }
    this.storage[this.size] = value;
    this.size++;
  }
  
  pop() {
    if (this.size === 0) throw new Error("Array is empty");
    this.size--;
    const value = this.storage[this.size];
    this.storage[this.size] = null; // Prevent memory leaks
    return value;
  }
  
  resize(newCapacity) {
    const newStorage = new Array(newCapacity);
    for (let i = 0; i < this.size; i++) {
      newStorage[i] = this.storage[i];
    }
    this.storage = newStorage;
    this.capacity = newCapacity;
  }
}

The expansion strategy of dynamic arrays typically doubles the capacity when the array is full, ensuring an amortized time complexity of O(1). For example:

  1. Initial capacity is 1
  2. After inserting the 1st element, capacity is 1
  3. After inserting the 2nd element, capacity expands to 2 (2^1)
  4. After inserting the 3rd element, capacity expands to 4 (2^2)
  5. After inserting the 5th element, capacity expands to 8 (2^3)
  6. And so on…

Although the expansion operation itself is O(n), the intervals between expansions increase, resulting in an amortized cost of O(1) per element operation.

Static vs. Dynamic in JavaScript

In JavaScript, we effectively only use dynamic arrays, but understanding static arrays is beneficial for:

  • Performance Optimization: Pre-filling arrays when the approximate size is known can reduce expansion overhead
  • Understanding Underlying Principles: Knowing how arrays work aids in using them more efficiently
  • Interfacing with Low-Level Languages: When interacting with languages like C/C++, static arrays may need to be handled

In JavaScript, pre-filling arrays can optimize performance:

// Pre-fill array to reduce expansion overhead
function createPreallocatedArray(size) {
  const arr = new Array(size);
  for (let i = 0; i < size; i++) {
    arr[i] = 0; // Or another default value
  }
  return arr;
}

const myArray = createPreallocatedArray(1000); // Create pre-filled array

Although JavaScript arrays are dynamic, this pre-filling technique is useful in performance-sensitive scenarios.

Array Operations

CRUD Operations

JavaScript arrays provide a rich set of built-in methods for manipulating elements. This section details commonly used methods for creating, reading, updating, and deleting (CRUD) elements.

Adding Elements

  1. push() – Adds one or more elements to the end of the array, returning the new length
const fruits = ['apple', 'banana'];
fruits.push('orange'); // Returns 3
console.log(fruits); // ['apple', 'banana', 'orange']
  1. unshift() – Adds one or more elements to the beginning of the array, returning the new length
fruits.unshift('pear'); // Returns 4
console.log(fruits); // ['pear', 'apple', 'banana', 'orange']
  1. splice() – Inserts elements at a specified position
// Syntax: splice(start, deleteCount, item1, item2, ...)
fruits.splice(2, 0, 'grape', 'kiwi'); // Inserts 'grape' and 'kiwi' at index 2, no deletion
console.log(fruits); // ['pear', 'apple', 'grape', 'kiwi', 'banana', 'orange']

Deleting Elements

  1. pop() – Removes and returns the last element of the array
const lastFruit = fruits.pop(); // Returns 'orange'
console.log(fruits); // ['pear', 'apple', 'grape', 'kiwi', 'banana']
  1. shift() – Removes and returns the first element of the array
const firstFruit = fruits.shift(); // Returns 'pear'
console.log(fruits); // ['apple', 'grape', 'kiwi', 'banana']
  1. splice() – Deletes elements at a specified position
// Syntax: splice(start, deleteCount)
fruits.splice(1, 2); // Deletes 2 elements starting from index 1
console.log(fruits); // ['apple', 'banana']

Updating Elements

  1. Direct assignment via index
fruits[0] = 'mango';
console.log(fruits); // ['mango', 'banana']
  1. splice() – Replaces elements at a specified position
fruits.splice(1, 1, 'peach'); // Replaces 1 element at index 1 with 'peach'
console.log(fruits); // ['mango', 'peach']

Querying Elements

  1. [] Index Access
console.log(fruits[0]); // 'mango'
  1. indexOf() – Returns the index of the first occurrence of an element
const index = ['a', 'b', 'c', 'a'].indexOf('a'); // Returns 0
  1. lastIndexOf() – Returns the index of the last occurrence of an element
const lastIndex = ['a', 'b', 'c', 'a'].lastIndexOf('a'); // Returns 3
  1. find() – Returns the first element that satisfies the condition
const numbers = [1, 2, 3, 4, 5];
const even = numbers.find(num => num % 2 === 0); // Returns 2
  1. findIndex() – Returns the index of the first element that satisfies the condition
const index = numbers.findIndex(num => num > 3); // Returns 3
  1. includes() – Checks if the array contains a specified element
const hasThree = numbers.includes(3); // Returns true

Advanced Operations

  1. concat() – Merges multiple arrays
const arr1 = [1, 2];
const arr2 = [3, 4];
const combined = arr1.concat(arr2); // [1, 2, 3, 4]
  1. slice() – Extracts a portion of the array (does not modify the original array)
const sliced = fruits.slice(1, 3); // From index 1 to 3 (excluding 3), ['banana']
  1. flat() / flatMap() – Flattens nested arrays (ES2019)
const nested = [1, [2, [3, [4]]]];
const flattened = nested.flat(2); // [1, 2, 3, [4]]
  1. at() – Retrieves an element at a specified index (ES2022, supports negative indices)
const last = fruits.at(-1); // Gets the last element

Iteration Methods

JavaScript arrays provide various iteration methods that do not modify the original array (unless specified) and execute a callback function for each element.

Basic Iteration

  1. forEach() – Executes a callback for each element
const numbers = [1, 2, 3];
numbers.forEach(num => console.log(num));
// Output:
// 1
// 2
// 3
  1. map() – Creates a new array with the results of calling a callback on each element
const doubled = numbers.map(num => num * 2); // [2, 4, 6]
  1. filter() – Creates a new array with all elements that pass the callback’s test
const evens = numbers.filter(num => num % 2 === 0); // [2]

Aggregation Methods

  1. reduce() – Reduces the array to a single value by executing a callback on an accumulator and each element
const sum = numbers.reduce((acc, num) => acc + num, 0); // 6
const product = numbers.reduce((acc, num) => acc * num, 1); // 6
  1. reduceRight() – Executes reduce from right to left
const str = ['h', 'e', 'l', 'l', 'o'].reduceRight((acc, char) => acc + char, '');
// 'olleh'

Search and Traversal

  1. some() – Tests if at least one element passes the callback’s test
const hasEven = numbers.some(num => num % 2 === 0); // true
  1. every() – Tests if all elements pass the callback’s test
const allEven = numbers.every(num => num % 2 === 0); // false
  1. find() – Returns the value of the first element that passes the test
const firstEven = numbers.find(num => num % 2 === 0); // 2
  1. findIndex() – Returns the index of the first element that passes the test
const firstEvenIndex = numbers.findIndex(num => num % 2 === 0); // 1
  1. keys() – Returns an iterator of array indices
for (const key of numbers.keys()) {
  console.log(key); // 0, 1, 2
}
  1. values() – Returns an iterator of array values
for (const value of numbers.values()) {
  console.log(value); // 1, 2, 3
}
  1. entries() – Returns an iterator of [index, value] pairs
for (const [index, value] of numbers.entries()) {
  console.log(index, value); // 0 1, 1 2, 2 3
}

Chaining Calls

Many array methods return the array itself (except for forEach, reduce, etc.), enabling method chaining:

const result = [1, 2, 3, 4, 5]
  .filter(num => num % 2 === 0) // [2, 4]
  .map(num => num * 10) // [20, 40]
  .reduce((acc, num) => acc + num, 0); // 60

Multidimensional Arrays and Matrices

JavaScript does not have a dedicated matrix type, but multidimensional arrays (i.e., matrices) can be implemented using nested arrays. This section covers the creation, access, and common operations of multidimensional arrays.

Creating Multidimensional Arrays

  1. Static Initialization
// 2x3 matrix
const matrix = [
  [1, 2, 3],
  [4, 5, 6]
];
  1. Dynamic Creation
function createMatrix(rows, cols, initialValue = 0) {
  return Array(rows).fill().map(() => Array(cols).fill(initialValue));
}

const matrix2 = createMatrix(2, 2, 1); // 2x2 matrix, initial value 1

Note: Using Array(rows).fill(Array(cols).fill(initialValue)) causes all rows to reference the same array. Use map to create independent rows.

Accessing Multidimensional Arrays

console.log(matrix[0][0]); // 1
console.log(matrix[1][2]); // 6

Traversing Multidimensional Arrays

  1. Nested Loops
for (let i = 0; i < matrix.length; i++) {
  for (let j = 0; j < matrix[i].length; j++) {
    console.log(matrix[i][j]);
  }
}
  1. Using reduce and map
matrix.flat().forEach(val => console.log(val));
// Or
matrix.forEach(row => row.forEach(cell => console.log(cell)));

Common Operations

  1. Matrix Transpose
function transpose(matrix) {
  return matrix[0].map((_, colIndex) => matrix.map(row => row[colIndex]));
}

const original = [[1, 2], [3, 4], [5, 6]];
const transposed = transpose(original); // [[1, 3, 5], [2, 4, 6]]
  1. Matrix Multiplication
function multiplyMatrices(a, b) {
  if (a[0].length !== b.length) throw new Error("Invalid matrix dimensions");
  
  const result = createMatrix(a.length, b[0].length, 0);
  
  for (let i = 0; i < a.length; i++) {
    for (let j = 0; j < b[0].length; j++) {
      for (let k = 0; k < a[0].length; k++) {
        result[i][j] += a[i][k] * b[k][j];
      }
    }
  }
  
  return result;
}

const a = [[1, 2], [3, 4]];
const b = [[5, 6], [7, 8]];
const product = multiplyMatrices(a, b); // [[19, 22], [43, 50]]
  1. Flattening a Matrix to a 1D Array
// Using flat method
const flattened = matrix.flat(); // [1, 2, 3, 4, 5, 6]

// Or using reduce
const flattenedReduce = matrix.reduce((acc, row) => acc.concat(row), []);
  1. Finding Maximum/Minimum in a Matrix
// Using flat and Math.max/Math.min
const max = Math.max(...matrix.flat());
const min = Math.min(...matrix.flat());

// Alternative without spread operator
const maxAlt = matrix.flat().reduce((acc, val) => Math.max(acc, val), -Infinity);
  1. Matrix Filling
function fillMatrix(matrix, value) {
  return matrix.map(row => row.map(() => value));
}

Performance Considerations

When handling large matrices, consider performance:

  • Avoid unnecessary array copying
  • For numerically intensive tasks, consider using TypedArray
  • For very large-scale data, consider Web Workers or specialized libraries (e.g., TensorFlow.js)

Practical Application Examples

  1. Image Processing: Pixels can be represented as multidimensional arrays for image transformations
// 2x2 grayscale image
const image = [
  [255, 0],
  [0, 128]
];

// Invert colors
const inverted = image.map(row => row.map(pixel => 255 - pixel));
  1. Game Development: Representing game maps or boards
// 3x3 tic-tac-toe board
const board = [
  ['', '', ''],
  ['', 'X', ''],
  ['', '', 'O']
];

// Check win condition
function checkWin(board, player) {
  // Check rows
  for (let i = 0; i < 3; i++) {
    if (board[i].every(cell => cell === player)) return true;
  }
  
  // Check columns
  for (let j = 0; j < 3; j++) {
    if (board.every(row => row[j] === player)) return true;
  }
  
  // Check diagonals
  if ((board[0][0] === player && board[1][1] === player && board[2][2] === player) ||
      (board[0][2] === player && board[1][1] === player && board[2][0] === player)) {
    return true;
  }
  
  return false;
}
  1. Scientific Computing: Matrix operations (e.g., neural network weights)
// Neural network weight matrix
const weights = createMatrix(3, 2, Math.random());

// Forward propagation
function forward(input, weights) {
  return multiplyMatrices([input], weights)[0];
}

Understanding multidimensional arrays and matrix operations is foundational for many advanced JavaScript applications (e.g., data visualization, games, machine learning). Mastering these concepts and techniques will significantly enhance your programming capabilities.

Course: Front-End Data Structures Essentials
Share your love

Trending now

Exploring Web 3D Core Technologies Development
Assembly Language Programming From Low-Level Logic to System Kernel
WebRTC Advanced Guide：Media, Transport & Architecture
WebSocket Deep Guide：Building High-Performance Realtime Systems