Javascript Data Structure

Part 1. Built-in Data Structures

What is Data Structure?

The way you organize data.

What is an Algorithm?

The way you solve the problem.

Built-in Data Structures

• Array
• Set
• Map
• Object

Array

Arrays are list-like objects whose prototype has methods to perform traversal and mutation operations. Neither the length of a JavaScript array nor the types of its elements are fixed. Since an array’s length can change at any time, and data can be stored at non-contiguous locations in the array, JavaScript arrays are not guaranteed to be dense; this depends on how the programmer chooses to use them. In general, these are convenient characteristics; but if these features are not desirable for your particular use, you might consider using typed arrays.

Array: non-contiguous, elements can be different types

Typed Array: contiguous, element should be the same type (mainly for binary data)

An element inside an array can be of any type, and different elements of the same array can be of different types

let arr = [1, "two", [3, "four"], {"hello":"world"}]
console.log(arr)
// [ 1, 'two', [ 3, 'four' ], { hello: 'world' } ]

Methods and property you must remember

• []
  construct a new array
• length
  length of the array
• push()
  add to an end
• pop()
  pop from an end
• shift()
  pop from the start
• unshift()
  add to the start
• splice(…)
  Adds and/or removes elements from an array.
  https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/splice
• slice(…)
  Extracts a section of the calling array and returns a new array.
  https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/slice
• map(…)
  Returns a new array containing the results of calling a function on every element in this array.
• reduce(…)
• forEach(…)

adding or removing at the start and end of an array

changes the contents of an array by removing or replacing existing elements and/or adding new elements in place.

returns a shallow copy of a portion of an array into a new array object selected from start to end (end not included) where start and end represent the index of items in that array. The original array will not be modified.

Sets

Set objects are collections of values. You can iterate through the elements of a set in insertion order. A value in the Set may only occur once; it is unique in the Set’s collection.

let mySet = new Set()
mySet.add(1)           // Set [ 1 ]
mySet.add('some text') // Set [ 1, 5, 'some text' ]
let o = {a: 1, b: 2}
mySet.add(o)
mySet.add({a: 1, b: 2}) // o is referencing a different object, so this is okay
console.log(mySet)
// Set { 1, 'some text', { a: 1, b: 2 }, { a: 1, b: 2 } }

• constructor
• size
• add
• delete(value)
• has(value)
• clear()

Map

The Map object holds key-value pairs and remembers the original insertion order of the keys. Any value (both objects and primitive values) may be used as either a key or a value.

The wrong way of creating a map

// don't do below to create a map. Below is just adding a property to an opbject!!!!
let wrongMap = new Map()
wrongMap['bla'] = 'blaa'
wrongMap['bla2'] = 'blaaa2'
console.log(wrongMap)
// Map { bla: 'blaa', bla2: 'blaaa2' }

The proper way of creating a map

the map needs to be added using the “set” method.

let contacts = new Map()
contacts.set('Jessie', {phone: "213-555-1234", address: "123 N 1st Ave"})
contacts.has('Jessie') // true
contacts.get('Hilary') // undefined
contacts.set('Hilary', {phone: "617-555-4321", address: "321 S 2nd St"})
contacts.get('Jessie') // {phone: "213-555-1234", address: "123 N 1st Ave"}
contacts.delete('Raymond') // false
contacts.delete('Jessie') // true
console.log(contacts.size) // 1

Property

• size

Method

• clear()
• delete(key)
• get(key)
• has(key)
• set(key, value)

Iteration method

• keys()
• values()
• entries()

let myMap = new Map()
myMap.set(0, 'zero')
myMap.set(1, 'one')

for (let [key, value] of myMap) {
  console.log(key + ' = ' + value)
}
// 0 = zero
// 1 = one

for (let key of myMap.keys()) {
  console.log(key)
}
// 0
// 1

for (let value of myMap.values()) {
  console.log(value)
}
// zero
// one

for (let [key, value] of myMap.entries()) {
  console.log(key + ' = ' + value)
}
// 0 = zero
// 1 = one

• forEach(callbackFn,[, thisArg])

myMap.forEach(function(value, key) {
  console.log(key + ' = ' + value)
})
// 0 = zero
// 1 = one

Object

It is used to store various keyed collections and more complex entities. Objects can be created using the Object() constructor or the {}

Static methods

Object.

• assign()
• create()
• defineProperty()
• defineProperties()
• getOwnPropertyDescriptor()
• getOwnPropertyDescriptors()
• getOwnPropertyNames()
• getOwnPropertySymbols()
• getPrototypeOf()
• setPrototypeOf()
• is()
• preventExtensions()
• freeze()
• seal()
• isExtensible()
• isFrozen()
• isSealed()
• entries()
• keys()
• values()

Instance properties

Object.prototype.

• constructor
• __proto__
• __noSuchMethod__

Instance methods

Object.prototype.

• __defineGetter__()
• __defineSetter__()
• __lookupGetter__()
• __lookupSetter__()
• hasOwnProperty()
• isPrototypeOf()
• propertyIsEnumerable()
• toLocaleString()
• toString()
• unwatch()
• valueOf()
• watch()