Dan D Kim

Let's share stories

Javascript Data Structure Cheat Sheet

2020-11-30 Dan D. Kimjavascript

Table of Contents

  1. Array
  2. Map
  3. Set
  4. Object

Array

Function Syntax Return value Invalid Case Runtime
Create array = [] null
Pop array.pop() popped element return undefined if empty O( 1 )
Push array.push(10) new length of the array O( 1 )
Shift / Dequeue array.shift() the removed (first) element return undefined if empty O( N )
Unshift / Queue array.unshift(10) new length of the array O (N)
Find array.find(element => element > 5) The first element in the array that matches the testing function returns undefined if no match O( N )
Index Of array.indexOf(element => element > 5) The index of the first element that matches the testing function returns -1 if no match O( N )
Filter array.filter(element => element > 5) A new array with matched elements Empty array if no match O( N )
Size array.length Number of elements

Iteration

// array.values()
for (const val of array.values())
// array.entries()
for (const [index, val] of array.entries())
// array.forEach()
array.forEach(val => val * 2)
// array.forEach()
array.forEach((val, index) => { // Note it's value-first, not index-first
  console.log(`${index}: ${val}`)
})

Methods to know

Map

Function Syntax Return value Invalid Case Runtime
Create map = new Map() the map
Add / Update map.set('key', 'val') the map object O( 1 )
Get map.get('key') the value of key return undefined if key not found O( 1 )
Has map.has('key') true if key match, false if not O( 1 )
Delete map.delete('key') true if removed, false if key did not exist O( 1 )
Clear map.clear() undefined O( N )
Size map.size Number of entries

Instantiate with values

const map = new Map([
  ['red', 10],
  ['blue', 20],
  ['green', 30]
])

Iteration

// map.keys()
for (const key of map.keys())
// map.entries()
for (const [key, value] of map.entries())
// map.forEach
map.forEach((value, key) => { // Note it's value-first, not key-first
  console.log(`${key}: ${value}`)
})

.clear() vs new Map()

How should you clean a map?

You might think that if you instantiate a new Map, the runtime could be faster. That might be true, but keep in mind that the previous map will have to be garbage collected. This means that the O( N ) work to clear the map is being done regardless, just in the garbage collector thread. You are basically giving up responsibility of clearing up the memory and leaving it to the garbage collector.

In general, it is not recommended to allocate new memory if you can avoid it.

Explain this if it comes up to your interviewer. Going with .clear() is a pretty safe choice.

Set

Function Syntax Return value Invalid Case Runtime
Create set = new Set()
Add set.add(10) set object O( 1 )
Has set.has(10) true if value exists, false otherwise O( 1 )
Delete set.delete(10) true if value is removed, false otherwise O( 1 )
Clear set.clear() Returns undefined O( N )
Size set.size Number of elements

Instantiate with values

const set = new Set('cat dog')
console.log(...set) // c, a, t,  , d, o, g
const set = new Set(['cat', 'dog'])
console.log(...set) // cat, dog

Iteration

// set.values()
for (const value of set.values())
// set.entries()
for (const value of set.entries())
// set.forEach()
set.forEach(val => console.log(val))

Object

Function Syntax Return value Invalid Case Runtime
Create object = {}
Add object.key = 10
object['key'] = 10		 O( 1 )
Get object.key
object['key']		 value of key undefined if key prop does not exist O( 1 )
Has object.key !== undefined
'key' in object		 true if key exists. false otherwise. O( 1 )
Delete delete object.key false if key is a non-configurable property and writable. Throws error if non-configurable and non-writable. true otherwise. Throws error if key is a non-configurable property and non-writable O( 1 )
Size Object.keys(object).length Number of properties of object O( N )

Configurable: Indicates whether the property descriptor may be changed and if the property may be deleted from the corresponding object. Reference

Writable: Indicates whether the value associated with the property may be changed with an assignment operator. Reference

Iteration

// for-in
for (const key in object) {
  const value = object[key]
}
// Object.keys()
Object.keys(object).forEach(key => {
  const value = object[key]
})

For when to use Maps versus Objects, check out my post about it here

Happy interviewing!