Skip to content
Ayotl
Español

← Data structures from scratch · Lesson 4/32

Arrays and indexes

✕
1/7

Slots in a row, from 0

An array stores its items next to each other, in numbered slots. The slot's number is its index, and counting starts at 0: the first is arr[0] and the last is arr[arr.length - 1].

Since the slots sit next to each other in memory, reaching slot 7 is just arithmetic: "where the array starts + 7 slots". You don't walk past the earlier ones. That's why reading or writing arr[i] costs O(1), whether the array has ten items or ten million.

125821301234arr[3] ↓
leccion.js

$ node leccion.js

Press RUN (or Ctrl+Enter).

What to look at

  • precios[3] is 21: the fourth item, because counting starts at 0.
  • You get the last one with length - 1, not length.
  • Changing slot 1 didn't move anything else.

Array on MDN (Spanish) ↗

The whole lesson on one page

Slots in a row, from 0

An array stores its items next to each other, in numbered slots. The slot's number is its index, and counting starts at 0: the first is arr[0] and the last is arr[arr.length - 1].

Since the slots sit next to each other in memory, reaching slot 7 is just arithmetic: "where the array starts + 7 slots". You don't walk past the earlier ones. That's why reading or writing arr[i] costs O(1), whether the array has ten items or ten million.

125821301234arr[3] ↓
const precios = [12, 5, 8, 21, 3];

console.log(precios[0]);                  // the first
console.log(precios[3]);                  // the fourth
console.log(precios[precios.length - 1]); // the last

precios[1] = 6;                           // writing is O(1) too
console.log(precios);
  • precios[3] is 21: the fourth item, because counting starts at 0.
  • You get the last one with length - 1, not length.
  • Changing slot 1 didn't move anything else.

Outside the array

What happens if you ask for a slot that doesn't exist? In C or Java that's a serious error (or worse: reading garbage from memory). JavaScript is more relaxed and hands you undefined, silently. Convenient, but it hides bugs: an index that's off by one gives undefined and the program keeps going as if nothing happened.

The most common array bug has a name: off by one. A loop with i <= arr.length takes one turn too many and reads the slot that isn't there.

const dias = ["lun", "mar", "mié"];

console.log(dias[3]);   // doesn't exist
console.log(dias[-1]);  // neither: no counting from the end
console.log(dias.at(-1)); // at() does count from the end

// The off-by-one bug: <= takes one extra turn
for (let i = 0; i <= dias.length; i++) {
  console.log(i, dias[i]);
}
  • dias[3] and dias[-1] give undefined, no error.
  • at(-1) is the modern way to ask for the last one.
  • The loop's last turn prints 3 undefined: that's the extra turn.

Grids: arrays of arrays

A board, a map or a spreadsheet is an array of rows, and each row is another array. You read it with two indexes: first the row (y), then the column (x): grid[y][x].

That's how Daily Challenge's Snake stores its walls: an array of 17 rows with 16 cells each, true where there's a wall. Checking whether a cell is free is one O(1) read.

  • x wall
const mapa = [
  "xxxxxx",
  "x....x",
  "x.xx.x",
  "x....x",
  "xxxxxx",
];
// From text to a grid of booleans: true = wall
const muros = mapa.map(fila => [...fila].map(c => c === "x"));

console.log(muros.length, "rows,", muros[0].length, "columns");
console.log(muros[2][2]);  // row 2, column 2
console.log(muros[1][2]);  // row 1, column 2
  • 5 rows of 6 columns.
  • muros[2][2] is true: row 2 has a wall in the middle.
  • muros[1][2] is false: open floor. Order matters: row first, column second.