Understand collections in JS

Without any further ado, let's get straight to it :)

What are the collections?

Collections are the type of data structure that follows Iteration protocols

The iterable protocol allows JavaScript objects to define or customize their iteration behavior, such as what values are looped over in a for...of construct. Some built-in types are built-in iterables with a default iteration behavior, such as Array or Map, while other types (such as Object) are not.

So whenever we loop through an element using the for-of loop, behind the scenes, the for-loop works like this:

const str = "Hello World";
const iterator = str[Symbol.iterator](); // String iterator object
let stringIterator = iterator.next(); // has a method next

  /* Imperative way */
   while (!stringIterator.done) {
       const { value } = stringIterator;
       console.log(value);
       stringIterator = iterator.next();
    }

   /* Or declarative way */
   const iterator = string[Symbol.iterator]();
   for(let v of iterator) {
        console.log(v);
 }

Make object iterator

 const obj = {
      a: "a",
      b: "b",
      c: "c",
      [Symbol.iterator]: function () {
        const keys = Object.keys(this);
        let i = 0;
        return {
          next: () => {
            return i < keys.length
              ? {
                  done: false,
                  value: this[keys[i++]],
                }
              : {
                  done: true,
                  value: undefined,
                };
          },
        };
      },
    };

   for (let i of obj) {
      console.log(i);
   }

💡

With Iteration procols any object can implement this by following the conventions who have the rights to say we can only loop over the array but not an object ? JS is a dynamic language, remember that ;)

Array

Arrays are one of the most common data types. Using them, we can handle a collection of data. But just like everything in JS, an array is an object, and it's kind of a surprise because why is it an object? Well, the short answer is that being an object can have some great benefits, such as allowing us to access methods

Create an array

Using the built-in Array constructor
Using array literal

const ninjas = ["Kuma", "Hattori", "Yagyu"];
const samurai = new Array("Oda", "Tomoe");

💡

Using array literals to create arrays is preferred over creating arrays with the Array constructor. The primary reason is simplicity: [] versus new Array() (2 characters versus 11 characters—hardly a fair contest).

Array bounds

Because JS is a dynamic language, when we define an array with a length of 3, later we assign it the value array[4]="ninja". The array will expand to accommodate the new situation

💡

Nothing stops us from manually changing its value

Array methods

Let's start our discussion with some basic methods of an array

push adds an item to the end of array
unshift adds an item to the beginning of an array
pop removes an item at the end of an array
shift removes an item at the beginning of an array

💡

As we all love data structure lessons back in university, we should know that shift and unshift will have a complexity of 0 (n)

Remove item at arbitrary location

Delete item from an array, leaving a hole in it

Splice method

The splice method is the versitle method in JS; it can either delete or insert element at certain location in an array depending on parameters we pass in. Let's explore it

const ninjas = ["1", "2", "3", "4"];

const removedItems = ninjas.splice(1, 1);
// splice returns an array of removed item ["2"];
ninjas;
// ["1","3","4"]

//Replace
ninja.splice(1,2,"5","6","7");
ninja;
// ["1","5","6","7","4"];

Common operation on arrays

Iterating
Mapping
Testing
Finding
Aggegating

Iterating

const ninjas = ["Yagyu", "Kuma", "Hattori"];
for(let i = 0; i < ninjas.length; i++){
  console.log(ninjas[i] !== null, ninjas[i]);
}

But this method has a lot of noisy details that developers has to pay attention to, so instead of doing that manually, JS offers us a built-in function that does the exact same thing

ninjas.forEach(ninja => { console.log(ninja !== null, ninja);
));

Mapping an array

const ninjas = [
  {name: "Yagyu", weapon: "shuriken"},
  {name: "Yoshi", weapon: "katana"},
  {name: "Kuma", weapon: "wakizashi"}
];
const weapons = ninjas.map(ninja => ninja.weapon);

Testing an array

When working with collections of items , we'll often run into situations where we need know whether all or at least some of the array items satisfy certain conditions

💡

The method returns true if all of the callback returns a true value

const ninjas = [
  {name: "Yagyu", weapon: "shuriken"},
  {name: "Yoshi" },
  {name: "Kuma", weapon: "wakizashi"}
];

const allNinjasAreNamed = ninjas.every(ninja => "name" in ninja);
const allNinjasAreArmed = ninjas.every(ninja => "weapon" in ninja);

💡

The method returns true if there's a callback return true

const someNinjasAreArmed = ninjas.some(ninja => "weapon" in ninja);

Searching arrays

Find a single item

Another common methods that we often use is finding item in an array

const ninjas = [
  {name: "Yagyu", weapon: "shuriken"},
  {name: "Yoshi" },
  {name: "Kuma", weapon: "wakizashi"}
];

const ninjaWithWakizashi = ninjas.find(ninja => {
  return ninja.weapon === "wakizashi";
});

Find multiple items

const armedNinjas = ninjas.filter(ninja => "weapon" in ninja);

Find an index of item

const yoshiIndex = ninjas.findIndex(ninja => ninja === "Yoshi");

Sorting an array

One of the most common array operations is sorting—arranging items systematically in some order. Unfortunately, correctly implementing sorting algorithms isn’t the easiest of programming tasks. JS has provided us the built-in sort method

array.sort((a, b) => a – b);

JS engine that implemented the sorting algorithm. The only thing we have to provide is callback that informs the sorting algorithm about the relationship between two items

If a callback returns a value less than 0, then item a should come before item b.
If a callback returns a value equal to 0 , then items a and b are equal
If a callback returns a value greater than 0, then item a should come after item b.

💡

Trick to remember. Suppose we have 10-15 = -5 < 0 then 10 should come before and 15-10 then 15 should come after 10

const ninjas = [{name: "Yoshi"}, {name: "Yagyu"}, {name: "Kuma"}];

ninjas.sort(function(ninja1, ninja2){
  if(ninja1.name < ninja2.name) { return -1; }
  if(ninja1.name > ninja2.name) { return 1; }
  return 0; 
});

Aggregating

const numbers = [1, 2, 3, 4];
const sum = 0;
numbers.forEach(number => {
   sum += number;
});

// Simplify the problem

const numbers = [1, 2, 3, 4];
const sum = numbers.reduce((aggregated, number)=> aggeregated+ 
number, 0);

Array-like objects (Custom Object Implementation)

Has indexed access to the elements and a non-negative length property to know the number of elements in it. These are the only similarities it has with an array.
Doesn't have any of the Array methods like push, pop, join, map, etc.

So it's not inherited these utilities methods from array interface

arr_like.forEach((el)=>console.log(el));
forEach is not a function

But why should we care?

JS is weird, and it indeed has this data structure in its implementation. We can encounter it with various different scenarios

document.getElementsByClassName
children
arguments properties
DOMTokenList

function checkArgs() {
   console.log(arguments);
}

document.getElementsByTagName('li');

And we can't use array methods on this type of data structure. What a pity

How do I convert it to an array?

Using ES6 spread operator
Array.from

function checkArgs() {
  // Using spread operator
  [...arguments].forEach((elem) => {
    console.log(elem);
  });
}

const collection = Array.from(document.getElementsByTagName('li'))

Summary

Array-like objects are not arrays. We can have index access and length properties access but we can't use array methods
There're many ways to convert array-like-objects to arrays (spread operator, Array.from methods)

Array are mutable

Yes, you heard it right. Arrays are not immutable

function arraySum(arr) {
    let sum = 0, num ;
    while( (num=arr.pop() !== undefined) {
        sum +=num;
    }
    return sum;
}

💡

This code has the side affect of emptying an array

function arraySum(arr) {
    // We can clone the copy of it to prevent mutate the original array
    const copyingArray = [...arr];
    ....
}

Well this is good but not that explicit , so better yet to switch to TS

function arraySum(arr:readonly number[]) {
  ...
  arr.pop(); // 'pop' does not exist on type 'readonly number[]'
}

You can read from its element, but you can't write to them
You can read its length, but you can't set it
You can't call pop or other methods that mutate the array

The index signature in array is string

JS is a famously quirky language and I agree with you

A JS object is a collection of key and value pairs. The keys are usually strings. Let's have a look at the example

x = {};
x[[1,2,3]] = 2;
// {'1,2,3':2} it converts an array of number to string by calling
// toString method
x = { 1:"1",2:"2",3:"3" } // number key will be converted to string
Object.keys(x);
["1","2","3"];

What about an array, then?

typeof [];
// object
x=[1,2,3];
x[0]
//1
//but also
x["0"]; // works too
Object.keys(x);
//["1",2","3"];

//So when you access index in array with number and you think it's number
//but in fact JS convert those number to string to access to the array
//Array is anboject so their keys are string not number

//In TS they attempts to bring some sanity to this by allowing only
//numeric to be key in array but oc in run-time TS will be gone away
//and you can use string to access the array index
interface Array<T> {
    [n:number]:T;
}

Array for Algorithms

Maps

Properties inherited through prototypes

Don't use objects as maps because objects have inherited properties that we may not need.

💡

A map does have a constructor property. Surprisingly, the key difference is that with map, we access the property with the function get and maybe behind the scenes, the get function actually does some validation for us to make sure that we can't access the constructor property

The key is converted to string

const obj1 = {};
const obj2 = {};
const map = {[obj1]:"obj1",[obj2]:"obj2"};

//Convert object to string "[Object object]";

map[obj1];
'obj2'
map[obj2];
'obj2'

Creating our first map

const ninjaIslandMap = new Map();

const ninja1 = { name: "Yoshi"};
const ninja2 = { name: "Hattori"};
const ninja3 = { name: "Kuma"};

ninjaIslandMap.set(ninja1, { homeIsland :"Japan" } );
ninjaIslandMap.set(ninja2, { homeIsland :"VN" } );

ninjaIslandMap.get(ninja1).homeIsland; // Japan
ninjaIslandMap.get(ninja2).homeIsland; // VN

A map can store object as its key

Some of the properties that can be used with map

set
get
delete
has
clear

Iterating over maps

My favourite thing about maps is that we can easily iterate over them compared to objects, when we have to use some JS utilities to loop over them.

Loop over keys
Loop over values
Loop over key and value pairs

const directory = new Map();
directory.set("Yoshi", "+81 26 6462");
directory.set("Kuma", "+81 52 2378 6462");
directory.set("Hiro", "+81 76 277 46");

for(let item of directory){
  item[0] , item[1]
}

for(let key of directory.keys()) {
   key;
   directory.get(key)
}

for(let value of directory.values()) {
   value;
}

Compare object vs map

Sets

In the real world, we have to deal with collections of distinct items (meaning each item can appear once), and we have not yet had this data structure in JS before ES6. Luckily, with the new ES6, we have this cool collection that we can utilize

const set = new Set(["Kuma", "Hattori", "Yagyu", "Hattori"]);

Set has a very similar API to map

has
add
delete
clear

Union of sets

A union of two sets, A and B for example , creates a new set that contains all elements from both A and B

const ninjas = ["Kuma", "Hattori", "Yagyu"];
const samurai = ["Hattori", "Oda", "Tomoe"];

const warriors = new Set([...ninjas, ...samurai]);

assert(warriors.size === 5, "There are 5 warriors in total");

Intersection of sets

The intersection of two sets, A and B , creates a set that contains element of A that are also in B

const ninjas = new Set(["Kuma", "Hattori", "Yagyu"]);
const samurai = new Set(["Hattori", "Oda", "Tomoe"]);

const ninjaSamurais = new Set(
  [...ninjas].filter(ninja => samurai.has(ninja))
);

Difference of sets

The difference of two sets, A and B, contains all elements that are in set A but are not in set B

const ninjas = new Set(["Kuma", "Hattori", "Yagyu"]);
const samurai = new Set(["Hattori", "Oda", "Tomoe"]);

const pureNinJas = new Set(
   [...ninjas].filter((ninja=>!sumurai.has(ninja)));

Perform a lookup with Set

Summary

A collection in JS is any object that follows iterator protocol
Set and Map data structures give us more power, from easy to iterate to performance-benchmark
So all of the time , I would say prefer using map over object and set over array

Collections in JS

Understand collections from JS land?

Table of contents