Javascript Basic Data Structures

Array

A JavaScript array is a dynamically-sized collection of elements, with the property that each element is uniquely identified by an integer key (called "index") starting from 0, can be of any type, and can be individually retrieved or modified. We call the side with the lowest index the "start" / "beginning" of an array, and the side with the highest index the "end". Access an element by an index is O(1).

Indexing

Only non-negative integer indices are allowed, and unlike in Python, accessing negative indices with bracket notation does not give you access to the last elements of the array.

Subarray slicing can be done with slice(start_index, upto_index), and the slicing indices are left-inclusive and right-exclusive. The upto_index can be ommited to extract till the end of the array, and both start_index and upto_index can be negative to indicate an offset from the end of array.

const arr = [0, 10, 20, 30, 40, 50];
let subarray = arr.slice(2, 5);
// [20, 30, 40]
subarray = arr.slice(-2);
// [40, 50]

Common Array Operations

  • push(item) adds item to the end of array and returns the array length; amortized O(1)
  • pop() removes and returns the last element of the array; amortized O(1)
  • shift() removes and returns the first element of the array; O(n)
  • unshift(item) adds item to the start of the array and returns the array length; O(n)
  • splice(start_index, count_to_remove, add_item1, add_item2, ...) removes and returns count_to_remove item(s) from an array given its/their index and optionally replaces them with add_items; O(n)

A note on Javascript runtimes: JavaScript array performance varies depending on the implementation, but almost always supports amortized O(1) time append/remove at the end of an array. Some implementations also support fast prepend/remove at the beginning.

In general, to iterate through a list, for loop is easier to reason than while since there's no condition to manage that could skip elements. In JavaScript, you can iterate through a list with C-like for loops, forEach loops, and for...of loops. The for...of loop can iterate over any iterable object, such as String, Array, and Map.