← Data structures from scratch · Lesson 5/32

Walking, adding and removing

1/7

Walking through

Walking an array means visiting each slot once: O(n). In JavaScript there are two forms you'll use all the time:

for (let i = 0; i < arr.length; i++) when you need the index.
for (const x of arr) when you only care about the value.

Looking for a value without knowing where it is is also a walk: indexOf and includes check slot by slot until they find it. That's linear search, O(n) in the worst case.

leccion.js

1const tianguis = ["jitomate", "cebolla", "chile", "aguacate"];
2
3for (let i = 0; i < tianguis.length; i++) {
4  console.log(i, tianguis[i]);
5}
6for (const cosa of tianguis) {
7  console.log(cosa.toUpperCase());
8}
9
10console.log(tianguis.indexOf("chile"));   // where it is
11console.log(tianguis.indexOf("mango"));   // -1: not there
12console.log(tianguis.includes("mango"));

$ node leccion.js

Press RUN (or Ctrl+Enter).

What to look at

The first loop gives index and value; the second, just the value.
indexOf returns -1 when it doesn't find it: to know that, it had to check all four slots.

The whole lesson on one page

Walking through

Walking an array means visiting each slot once: O(n). In JavaScript there are two forms you'll use all the time:

for (let i = 0; i < arr.length; i++) when you need the index.
for (const x of arr) when you only care about the value.

Looking for a value without knowing where it is is also a walk: indexOf and includes check slot by slot until they find it. That's linear search, O(n) in the worst case.

1const tianguis = ["jitomate", "cebolla", "chile", "aguacate"];
2
3for (let i = 0; i < tianguis.length; i++) {
4  console.log(i, tianguis[i]);
5}
6for (const cosa of tianguis) {
7  console.log(cosa.toUpperCase());
8}
9
10console.log(tianguis.indexOf("chile"));   // where it is
11console.log(tianguis.indexOf("mango"));   // -1: not there
12console.log(tianguis.includes("mango"));

The first loop gives index and value; the second, just the value.
indexOf returns -1 when it doesn't find it: to know that, it had to check all four slots.

The end is cheap; the front is expensive

push adds at the end and pop removes from the end: nobody has to move, so they cost O(1).

unshift adds at the front and shift removes from the front. Since the slots are contiguous and numbered, everyone else has to shift one place to open or close the gap: O(n). splice, which adds or removes in the middle, also shifts everything behind it.

The program times each one with 20,000 items.

1function medir(nombre, hacer) {
2  const arr = [];
3  const t0 = Date.now();
4  for (let i = 0; i < 20000; i++) hacer(arr, i);
5  console.log(nombre, Date.now() - t0, "ms");
6}
7
8medir("push   ", (a, i) => a.push(i));
9medir("unshift", (a, i) => a.unshift(i));
10
11const letras = ["a", "b", "c", "d"];
12letras.splice(1, 2);        // from 1, remove 2
13console.log(letras);
14letras.splice(1, 0, "x");   // from 1, remove 0 and insert "x"
15console.log(letras);

unshift takes many times longer than push for the same count: each one shifts everyone already there. (The milliseconds change from run to run; the gap doesn't.)
splice(start, howMany, ...newItems) removes and inserts in the middle.

map, filter and reduce

Three walks so common they have their own names. All three return something new and leave the original alone:

map(f): an array of the same size, with f applied to each item.
filter(f): only the items for which f returns true.
reduce(f, initial): folds everything into a single value, like a sum.

They're still O(n): loops written another way.

1const precios = [20, 45, 12, 80];
2
3const conIva = precios.map(p => p * 1.16);
4console.log(conIva);
5
6const baratos = precios.filter(p => p < 30);
7console.log(baratos);
8
9const total = precios.reduce((suma, p) => suma + p, 0);
10console.log(total);
11
12console.log(precios); // the original didn't change

map gives four prices with 16 % tax (with ugly decimals: that's floating point for you).
filter keeps 20 and 12.
reduce starts at 0 and keeps adding: 157.