Dynamic array

• Quick summary: an array that can resize itself.
• Also known as: array list, list, growable array, resizable array, mutable array, dynamic table.
• Important facts:
  • Same as array in most regards: stores elements sequentially, uses numeric indexing, allocates contiguous memory space.
  • Expands as you add more elements. Doesn't require setting initial capacity.
  • When it exhausts capacity, a dynamic array allocates a new contiguous memory space that is double the previous capacity, and copies all values to the new location.
  • Time complexity is the same as for a fixed array except for worst-case appends: when capacity needs to be doubled, append is O(n). However, the average append is still O(1).
• Pros:
  • Variable size. A dynamic array expands as needed.
  • Constant time access.
• Cons:
  • Slow worst-case appends: O(n). Average appends: O(1).
  • Insertion and deletion are still slow because subsequent elements must be moved a single index further. Worst-case (insertion into/deletion from the first index, a.k.a. prepending) for both is O(n).
• Time complexity (worst case):
  • Access: O(1)
  • Search: O(n)
  • Insertion: O(n) (append: O(n))
  • Deletion: O(n)
• See also: same as arrays (see above).

xxxxxxxxxx

/* Arrays are dynamic in Javascript :-) */

​

// instantiation

let empty = new Array();

let teams = new Array('Knicks', 'Mets', 'Giants');

​

// literal notation

let otherTeams = ['Nets', 'Patriots', 'Jets'];

​

// size

console.log('Size:', otherTeams.length);

​

// access

console.log('Access:', teams[0]);

​

// sort

const sorted = teams.sort();

console.log('Sorted:', sorted);

​

// search

const filtered = teams.filter((team) => team === 'Knicks');

console.log('Searched:', filtered);