1. JavaScript
  2. Fundamentals
  3. Data Structures

JavaScript Data Structures

Last updated:

  • Array - Ordered, mutable list of values
  • Set & WeakSet - Unordered collections of unique values
  • Map & WeakMap - Collections of key-value pairs
  • Object - Key-value pairs with additional features

Arrays

0-indexed ordered mutable list

  • can hold any type of data
myArray[2];  // returns: 42
myArray.slice(2, 4);   // returns: Array [ 42, 3.14 ]

Creating an Array

Literal syntax:

const myArray = ['a', 42, 3.14];

Array constructor:

const myArray = new Array('a', 42, 3.14);

Introspection

Arrays are implemented as objects:

console.log(typeof myArray);  // Outputs: object

To can check if a variable is an array:

const myArray = ['a', 42, 3.14];
console.log(Array.isArray(myArray)); //Outputs true

Array Iteration

myArray.forEach(function(item) {
    console.log(item);
});

for(let i = 0; i < myArray.length; i++) {
    console.log(myArray[i]);
}

for(const item of myArray) {
    console.log(item);
};

Modifying Arrays

push & pop

Add and remove elements from the end of an array:

const myArray = ['a', 42, 3.14];
myArray.push('Hello', {'x': 1}); // returns: 5 (number of elements in the array)

console.log(myArray);  // Outputs: Array(5) [ "a", 42, 3.14, "Hello", {…} ]

myArray.pop();  // returns: Object { x: 1 }
console.log(myArray);  // Outputs: Array(4) [ "a", 42, 3.14, "Hello" ]

shift & unshift

To add and remove elements from the beginning of the array:

myArray.unshift('Start', {'y': 2});  // returns:  6
console.log(myArray);
// Outputs: Array(6) [ "Start", {…}, "a", 42, 3.14, "Hello" ]

myArray.shift();   // returns "Start"
console.log(myArray);
// Outputs: Array(5) [ {…}, "a", 42, 3.14, "Hello" ]

Operations

Filter

Filtering based on a given criteria:

let myArray = [1, 4, 42, 11, 79];
let letters = myArray.filter((item) => {
  return (item % 2) === 0;
});
console.log(letters);  // Outputs: [4, 42]

Retrieving all string elements from an array:

let myArray = ["a", 42, 3.14];
let letters = myArray.filter((item) => {
  return Object.prototype.toString.call(item) === "[object String]";
});
console.log(letters);  // Outputs: ["a"]

Array Map

Transform each element of an array into another entity based on a certain flow:

let myArray = [1, 4, 42, 11, 79];
let doubleArray = myArray.map((item) => {
  return item * 2;
});
console.log(doubleArray);  // Outputs: [2, 8, 84, 22, 158]

NB: The original one remains unchanged.

Return an array containing an object property:

let articles = [
  { title: 'article 1', abstract: 'abstract 1'},
  { title: 'article 2', abstract: 'abstract 2'},
  { title: 'article 3', abstract: 'abstract 3'}
];

let titles = articles.map((article) => {
  return article.title;
})
console.log(titles);  // Outputs: ["article 1", "article 2", "article 3"]

Reduce

Reduces the entire array to one value - takes 2 parameters: an arrow function that computes the current step, and the initial value.

Calculate the sum of all elements in an array:

let myArray = [1, 4, 42, 11, 79];
let total = myArray.reduce((item, currentTotal) => {
  return currentTotal + item;
}, 0);
console.log(total);  // Outputs: 137

Flatten multi-dimensional arrays:

let myArray = [[1, 4], 23, [42, 11], 79];
const flatArray = myArray.reduce((currentFlatArray, amount) => {
  return currentFlatArray.concat(amount);
}, []);
console.log(flatArray);  // Outputs: [1, 4, 23, 42, 11, 79]

Use case - Word frequency

let text = 'Alice was beginning to get very tired of sitting ' +
'by her sister on the bank, and of having nothing to do : ' +
'once or twice she had peeped into the book her sister was ' +
'reading, but it had no pictures or conversations in it ... ';

// 1. Split text into words
let words = text.split(" ");

// 2. Compute word count
var wordsCount = words.reduce( (tally, word) => {
  let lowercaseWord = word.toLowerCase();
  tally[lowercaseWord] = (tally[lowercaseWord] || 0) + 1 ;
  return tally;
} , {});

// 3. Sort word count with the most used first

// 3.1. Create array from dictionary
var wordsCountArray = Object.keys(wordsCount).map(function(key) {
  return [key, wordsCount[key]];
});

// 3.2. Sort the array based on the second element
wordsCountArray.sort(function(first, second) {
  return second[1] - first[1];
});

// 4. Display the end result
console.log(wordsCountArray);

[["was", 2], ["to", 2], ["of", 2], ["her", 2], ["sister", 2], ["the", 2],
 ["or", 2], ["had", 2], ["it", 2], ["alice", 1], ["beginning", 1],
 ["get", 1], ["very", 1], ["tired", 1], ["sitting", 1], ["by", 1],
 ["on", 1], ["bank,", 1], ["and", 1], ["having", 1], ["nothing", 1],
 ["do", 1], [":", 1], ["once", 1], ["twice", 1], ["she", 1], ["peeped", 1],
 ["into", 1], ["book", 1], ["reading,", 1], ["but", 1], ["no", 1],
 ["pictures", 1], ["conversations", 1], ["in", 1], ["...", 1], ["", 1]]

Set & WeakSet

  • Unordered collections of unique values.
  • does not have an index but the order is guaranteed to be insertion order

Set

Store unique values of any type:

const mathConstants = new Set();

Can also receive an iterable object as argument (e.g. array, string), with any duplication being removed:

const mathConstants = new Set([0, 3.14, -1, 0]);
console.log(mathConstants);  // Outputs: Set(3) [ 0, 3.14, -1 ]

Modyfing a Set

New elements can be appended with add, removed with delete - the number of elements stored can be inspected with size:

const mathConstants = new Set([0, 3.14, -1]);

mathConstants.add(1.61803);
mathConstants.add(1.61803);  // duplicate entries will be ignored

mathConstants.delete(-1);

console.log(mathConstants);  // Outputs: [ 0, 3.14, 1.61803 ]

console.log(mathConstants.size);  // Outputs: 3

Finding an Element

const mathConstants = new Set([0, 3.14, -1]);

console.log(mathConstants.has(3.14));  // Outputs: true
console.log(mathConstants.has(1.41));  // Outputs: false

The order of elements in a Set object is guaranteed to be insertion order - new elements are added to the end of the Set.

Set Iteration

const mathConstants = new Set([0, 3.14, -1, 0]);

for (const value of mathConstants) {
  console.log(value);
}

mathConstants.forEach((value) => {
  console.log(value);
});

WeakSet

  • collection of objects that are weakly held - if there are no other references to an object, it may be garbage collected.
  • no primitives allowed - values must be objects
  • do not have a size property or any other way to get the number of values they contain
  • not enumerable - we cannot use a for...in loop
const mathConstants = new WeakSet();

const pi = {
    name: 'PI',
    value: 3.14159
};
mathConstants.add(pi);
console.log(mathConstants);  // Outputs: WeakSet [ { ... } ]

Weakly Held Objects

When a WeakSet object is created, memory is allocated to store the object but the values are not strongly held - if there are no other references to a value in the program, the object may be garbage collected by the JavaScript engine. When a key is garbage collected, its associated value is also removed from the WeakSet object.

Limitations

Very limited in functionality - pretty much the only thing you can do is check if a WeakSet contains an object:

const mathConstants = new WeakSet();

const pi = {
    name: 'PI',
    value: 3.14159
};
mathConstants.add(pi);

const tau = {
    name: 'tau',
    value: 6.28318
};


console.log(mathConstants.has(pi));   // Outputs: true
console.log(mathConstants.has(tau));  // Outputs: false

Map & WeakMap

  • collection of key-value pairs
  • keys can be of any type, including objects, and each value can be of any type or a combination of types.
  • maintains the order in which key-value pairs are added (compared to an object where property order is not guaranteed).

Map

const myMap = new Map();

Can also be initialised a with an iterable - e.g. an array of arrays containing key-value pairs:

const myMap = new Map([
  ['key1', 'value1'],
  ['key2', 'value2'],
  ['key3', 'value3']
]);

console.log(myMap);
  // Outputs: Map(3) { 'key1' => 'value1', 'key2' => 'value2', 'key3' => 'value3' }

Map Operations

const myMap = new Map();

const key1 = { name: 'key 1'};
myMap.set(key1, 'value1');

console.log(myMap);            // Outputs: Map(1) { { name: 'key 1' } => 'value1' }
console.log(myMap.get(key1));  // Outputs: value1

console.log(myMap.has(key1));  // Outputs: true

myMap.delete('random');        // Outputs: false
myMap.delete(key1);            // Outputs: true

const myMap = new Map();

const key1 = { name: 'key 1'};
myMap.set(key1, 'value1');

console.log(myMap.size);       // Outputs: 1

Map Iteration

Via the keys() iterator:

const myMap = new Map([
  ['key1', 'value1'],
  ['key2', 'value2'],
  ['key3', 'value3']
]);

for (const key of myMap.keys()) {
  console.log(key);
}

There is also a values() iterator and can be used to convert values to arrays:

const keys = Array.from(myMap.keys());
const values = Array.from(myMap.values());

Memory usage

The Map object can use any type of value as a key, whereas object keys are always converted to strings. This flexibility can also lead to increased memory usage, since Map objects can potentially contain a large number of objects as keys.

WeakMap

Similar to the Map object, but with some differences:

  • keys must be objects, with primitive values such as numbers or strings are not allowed.
  • keys are not strongly held - if there are no other references to a key in the program, the key may be garbage collected by the JavaScript engine.
  • does not have a size property or any other way to get the number of key-value pairs it contain.
  • keys cannot be iterated directly, as there is no guarantee that the keys returned by an iterator will still be valid.
  • not enumerable - we cannot use a for…in loop or keys() to iterate over properties.
const myWeakMap = new WeakMap();

WeakMap Operations

const myWeakMap = new WeakMap();

const key1 = { name: 'key 1'};
myWeakMap.set(key1, 'value1');

console.log(myWeakMap);            // Outputs: WeakMap { <items unknown> }
console.log(myWeakMap.get(key1));  // Outputs: value1

console.log(myWeakMap.has(key1));  // Outputs: true

console.log(myWeakMap.size);       // Outputs: undefined

myWeakMap.delete('random');        // Outputs: false
myWeakMap.delete(key1);            // Outputs: true