# Blog

## Data Structures: Objects and Arrays Posted on May 28, 2019 in JavaScript by Matt Jennings

Note: Information below was taken from Eloquent JavaScript, 3rd edition, Chapter 4 Data Structures: Objects and Arrays.

Objects allow us to group values—including other objects—to build more complex structures.

### Arrays

JavaScript provides a data type specifically for storing sequences of values. It is called an array and is written as a list of values between square brackets, separated by commas.

```let listOfNumbers = [2, 3, 5, 7, 11];
console.log(listOfNumbers[2]);
// 5
console.log(listOfNumbers[0]);
// 2
console.log(listOfNumbers[2 - 1]);
// 3```

### Properties

We’ve seen a few suspicious-looking expressions like `myString.length` (to get the length of a string) and `Math.max` (the maximum function) in past chapters. These are expressions that access a property of some value. In the first case, we access the `length` property of the value in `myString`. In the second, we access the property named `max` in the `Math` object (which is a collection of mathematics-related constants and functions).

Almost all JavaScript values have properties. The exceptions are `null` and `undefined`. If you try to access a property on one of these nonvalues, you get an error.

```null.length;
// TypeError: null has no properties```

The two main ways to access properties in JavaScript are with a dot and with square brackets. Both `value.x` and `value[x]` access a property on `value`—but not necessarily the same property. The difference is in how `x` is interpreted.

Whereas `value.x` fetches the property of `value` named “x”, `value[x]` tries to evaluate the expression `x` and uses the result, converted to a string, as the property name.

So if you know that the property you are interested in is called color, you say `value.color`. If you want to extract the property named by the value held in the binding `i`, you say `value[i]`. Property names are strings.

The elements in an array are stored as the array’s properties, using numbers as property names. Because you can’t use the dot notation with numbers and usually want to use a binding that holds the index anyway, you have to use the bracket notation to get at them.

The `length` property of an array tells us how many elements it has. This property name is a valid binding name, and we know its name in advance, so to find the length of an array, you typically write `array.length` because that’s easier to write than `array["length"]`.

### Methods

Both string and array objects contain, in addition to the `length` property, a number of properties that hold function values.

```let doh = "Doh";
console.log(typeof doh.toUpperCase);
// function
console.log(doh.toUpperCase());
// DOH```

Properties that contain functions are generally called methods of the value they belong to, as in “`toUpperCase` is a method of a string”.

This example demonstrates two methods you can use to manipulate arrays:

```let sequence = [1, 2, 3];
sequence.push(4);
sequence.push(5);
console.log(sequence);
// [1, 2, 3, 4, 5]
console.log(sequence.pop());
// 5
console.log(sequence);
// [1, 2, 3, 4]```

A stack, in programming, is a data structure that allows you to push values into it and pop them out again in the opposite order so that the thing that was added last is removed first.

### Objects

Values of the type object are arbitrary collections of properties. One way to create an object is by using braces as an expression.

```let day1 = {
squirrel: false,
events: ["work", "touched tree", "pizza", "running"]
};
console.log(day1.squirrel);
// false
console.log(day1.wolf);
// undefined
day1.wolf = false;
console.log(day1.wolf);
// false```

Properties whose names aren’t valid binding names or valid numbers have to be quoted.

```let descriptions = {
work: "Went to work",
"touched tree": "Touched a tree"
};```

This means that braces have two meanings in JavaScript. At the start of a statement, they start a block of statements. In any other position, they describe an object. Fortunately, it is rarely useful to start a statement with an object in braces, so the ambiguity between these two is not much of a problem.

Reading a property that doesn’t exist will give you the value `undefined`.

It is possible to assign a value to a property expression with the `=` operator. This will replace the property’s value if it already existed or create a new property on the object if it didn’t.

The `delete` operator cuts off a tentacle from such an octopus. It is a unary operator that, when applied to an object property, will remove the named property from the object. This is not a common thing to do, but it is possible.

```let anObject = {left: 1, right: 2};
console.log(anObject.left);
// 1
delete anObject.left;
console.log(anObject.left);
// undefined
console.log("left" in anObject);
// false
console.log("right" in anObject);
// true```

The binary `in` operator, when applied to a string and an object, tells you whether that object has a property with that name. The difference between setting a property to `undefined` and actually deleting it is that, in the first case, the object still has the property (it just doesn’t have a very interesting value), whereas in the second case the property is no longer present and `in` will return `false`.

To find out what properties an object has, you can use the `Object.keys`function. You give it an object, and it returns an array of strings—the object’s property names.

```console.log(Object.keys({x: 0, y: 0, z: 2}));
// ["x", "y", "z"]
```

There’s an `Object.assign` function that copies all properties from one object into another.

```let objectA = {a: 1, b: 2};
Object.assign(objectA, {b: 3, c: 4});
console.log(objectA);
// {a: 1, b: 3, c: 4}```

Arrays, then, are just a kind of object specialized for storing sequences of things. If you evaluate `typeof []`, it produces `"object"`.

We will represent the journal that Jacques keeps as an array of object

```let journal = [
{events: ["work", "touched tree", "pizza",
"running", "television"],
squirrel: false},
{events: ["work", "ice cream", "cauliflower",
"lasagna", "touched tree", "brushed teeth"],
squirrel: false},
{events: ["weekend", "cycling", "break", "peanuts",
"beer"],
squirrel: true},
/* and so on... */
];```

### Mutability

We saw that object values can be modified. The types of values discussed in earlier chapters, such as numbers, strings, and Booleans, are all immutable—it is impossible to change values of those types. You can combine them and derive new values from them, but when you take a specific string value, that value will always remain the same. The text inside it cannot be changed.

If you have a string that contains `"cat"`, it is not possible for other code to change a character in your string to make it spell `"rat"`.

Objects work differently. You can change their properties, causing a single object value to have different content at different times.

```let object1 = {value: 10};
let object2 = object1;
let object3 = {value: 10};

console.log(object1 === object2);
// true
console.log(object1 === object3);
// false
object1.value = 15;

console.log(object1.value);
// 15
console.log(object2.value);
// 15
console.log(object3.value);
// 10```

The `object1` and `object2` bindings grasp the same object, which is why changing `object1` also changes the value of `object2`. They are said to have the same identity. The binding `object3` points to a different object, which initially contains the same properties as `object1` but lives a separate life.

Bindings can also be changeable or constant, but this is separate from the way their values behave. Even though number values don’t change, you can use a `let` binding to keep track of a changing number by changing the value the binding points at.

Similarly, though a `const` binding to an object can itself not be changed and will continue to point at the same object, the contents of that object might change.

```const score = {visitors: 0, home: 0};
// This is okay
score.visitors = 1;
// This isn't allowed
score = {visitors: 1, home: 1};```

Arrays have an `includes` method that checks whether a given value exists in the array. The function uses that to determine whether the event name it is interested in is part of the event list for a given day.

### Array loops

```for (let i = 0; i < JOURNAL.length; i++) {
let entry = JOURNAL[i];
// Do something with entry
}```

There is a simpler way to write such loops in modern JavaScript.

```for (let entry of JOURNAL) {
console.log(`\${entry.events.length} events.`);
}```

### Further arrayology

We saw `push` and `pop`, which add and remove elements at the end of an array, earlier in this chapter. The corresponding methods for adding and removing things at the start of an array are called `unshift` and `shift`.

```let todoList = [];
}
}
}```

To search for a specific value, arrays provide an `indexOf` method. The method searches through the array from the start to the end and returns the index at which the requested value was found—or -1 if it wasn’t found.

To search from the end instead of the start, there’s a similar method called `lastIndexOf`.

```console.log([1, 2, 3, 2, 1].indexOf(2));
// 1
console.log([1, 2, 3, 2, 1].lastIndexOf(2));
// 3```

Both `indexOf` and `lastIndexOf` take an optional second argument that indicates where to start searching.

Another fundamental array method is `slice`, which takes start and end indices and returns an array that has only the elements between them. The start index is inclusive, the end index exclusive.

```console.log([0, 1, 2, 3, 4].slice(2, 4));
// [2, 3]
console.log([0, 1, 2, 3, 4].slice(2));
// [2, 3, 4]```

When the end index is not given, `slice` will take all of the elements after the start index. You can also omit the start index to copy the entire array.

```function remove(array, index) {
return array.slice(0, index)
.concat(array.slice(index + 1));
}
console.log(remove(["a", "b", "c", "d", "e"], 2));
// ["a", "b", "d", "e"]```

If you pass `concat` an argument that is not an array, that value will be added to the new array as if it were a one-element array.

### Strings and their properties

We can read properties like `length` and `toUpperCase` from string values. But if you try to add a new property, it doesn’t stick.

```let kim = "Kim";
kim.age = 88;
console.log(kim.age);
// undefined```

Values of type string, number, and Boolean are not objects, and though the language doesn’t complain if you try to set new properties on them, it doesn’t actually store those properties. As mentioned earlier, such values are immutable and cannot be changed.

Every string value has a number of methods. Some very useful ones are `slice` and `indexOf`, which resemble the array methods of the same name.

```console.log("coconuts".slice(4, 7));
// nut
console.log("coconut".indexOf("u"));
// 5```

One difference is that a string’s `indexOf` can search for a string containing more than one character, whereas the corresponding array method looks only for a single element.

```console.log("one two three".indexOf("ee"));
// 11```

The `trim` method removes whitespace (spaces, newlines, tabs, and similar characters) from the start and end of a string.

```console.log("  okay \n ".trim());
// okay```

You can split a string on every occurrence of another string with `split` and join it again with `join`.

```let sentence = "Secretarybirds specialize in stomping";
let words = sentence.split(" ");
console.log(words);
// ["Secretarybirds", "specialize", "in", "stomping"]
console.log(words.join(". "));
// Secretarybirds. specialize. in. stomping```

A string can be repeated with the `repeat` method, which creates a new string containing multiple copies of the original string, glued together.

```console.log("LA".repeat(3));
// LALALA```

We have already seen the string type’s `length` property. Accessing the individual characters in a string looks like accessing array elements.

```let string = "abc";
console.log(string.length);
// 3
console.log(string[1]);
// b```

### Rest parameters

It can be useful for a function to accept any number of arguments. For example, `Math.max` computes the maximum of all the arguments it is given.

To write such a function, you put three dots before the function’s last parameter, like this:

```function max(...numbers) {
let result = -Infinity;
for (let number of numbers) {
if (number > result) result = number;
}
return result;
}
console.log(max(4, 1, 9, -2));
// 9```

When such a function is called, the rest parameter is bound to an array containing all further arguments. If there are other parameters before it, their values aren’t part of that array. When, as in `max`, it is the only parameter, it will hold all arguments.

You can use a similar three-dot notation to call a function with an array of arguments.

```let numbers = [5, 1, 7];
console.log(max(...numbers));
// 7```

This “spreads” out the array into the function call, passing its elements as separate arguments. It is possible to include an array like that along with other arguments, as in `max(9, ...numbers, 2)`

Square bracket array notation similarly allows the triple-dot operator to spread another array into the new array.

```let words = ["never", "fully"];
console.log(["will", ...words, "understand"]);
// ["will", "never", "fully", "understand"]```

### The Math object

As we’ve seen, `Math` is a grab bag of number-related utility functions, such as `Math.max` (maximum), `Math.min` (minimum), and `Math.sqrt` (square root).

The `Math` object is used as a container to group a bunch of related functionality. There is only one `Math` object, and it is almost never useful as a value. Rather, it provides a namespace so that all these functions and values do not have to be global bindings.

Having too many global bindings “pollutes” the namespace. Since JavaScript’s built-in `max`function is tucked safely inside the `Math` object, we don’t have to worry about overwriting it.

Many languages will stop you, or at least warn you, when you are defining a binding with a name that is already taken. JavaScript does this for bindings you declared with `let` or `const` but—perversely—not for standard bindings nor for bindings declared with `var` or `function`.

The number π (pi)—or at least the closest approximation that fits in a JavaScript number—is available as `Math.PI`. There is an old programming tradition of writing the names of constant values in all caps.

The previous example used `Math.random`. This is a function that returns a new pseudorandom number between zero (inclusive) and one (exclusive) every time you call it.

```console.log(Math.random());
// 0.36993729369714856
console.log(Math.random());
// 0.727367032552138
console.log(Math.random());
// 0.40180766698904335```

### Destructuring

We’d much prefer to have bindings for the elements of the array, that is, `let n00 = table[0]` and so on. Fortunately, there is a succinct way to do this in JavaScript.

```function phi([n00, n01, n10, n11]) {
return (n11 * n00 - n10 * n01) /
Math.sqrt((n10 + n11) * (n00 + n01) *
(n01 + n11) * (n00 + n10));
}```

A similar trick works for objects, using braces instead of square brackets.

```let {name} = {name: "Faraji", age: 23};
console.log(name);
// Faraji```

### JSON

Because properties only grasp their value, rather than contain it, objects and arrays are stored in the computer’s memory as sequences of bits holding the addresses—the place in memory—of their contents.

So an array with another array inside of it consists of (at least) one memory region for the inner array, and another for the outer array, containing (among other things) a binary number that represents the position of the inner array.

What we can do is serialize the data. That means it is converted into a flat description. A popular serialization format is called JSON (pronounced “Jason”), which stands for JavaScript Object Notation. It is widely used as a data storage and communication format on the Web, even in languages other than JavaScript.

JSON looks similar to JavaScript’s way of writing arrays and objects, with a few restrictions. All property names have to be surrounded by double quotes, and only simple data expressions are allowed—no function calls, bindings, or anything that involves actual computation. Comments are not allowed in JSON.

A journal entry might look like this when represented as JSON data:

```{
"squirrel": false,
"events": ["work", "touched tree", "pizza", "running"]
}```

JavaScript gives us the functions `JSON.stringify` and `JSON.parse` to convert data to and from this format. The first takes a JavaScript value and returns a JSON-encoded string. The second takes such a string and converts it to the value it encodes.

```let string = JSON.stringify({squirrel: false,
events: ["weekend"]});
console.log(string);
// {"squirrel":false,"events":["weekend"]}
console.log(JSON.parse(string));
/*
[object Object] {
event: ["weekend"],
squirrel: false
}
*/```

### The sum of a range

Write a `range` function that takes two arguments, `start` and `end`, and returns an array containing all the numbers from `start` up to (and including) `end`.

Next, write a `sum` function that takes an array of numbers and returns the sum of these numbers. Run the example program and see whether it does indeed return 55.

As a bonus assignment, modify your `range` function to take an optional third argument that indicates the “step” value used when building the array. If no step is given, the elements go up by increments of one, corresponding to the old behavior.

```function range(start, end, step = 1) {
const arr = []

if(start < end) {
for(let i = start; i <= end; i += step) {
arr.push(i)
}
}
else {
for(let i = start; i >= end; i -= step) {
arr.push(i)
}
}

return arr
}

function sum(arr) {
const sumOfArr = arr.reduce((total, num) => total + num)
return sumOfArr
}

console.log(range(1, 10, 2))
// [1, 3, 5, 7, 9]
console.log(sum(range(1, 10, 2)))
// 25
console.log(range(10, -2, 2))
// [10, 8, 6, 4, 2, 0, -2]
console.log(sum(range(10, -2, 2)))
// 28```

### Reversing an array

```function reverseArray(arr) {
const newArr = []
for(let i = arr.length - 1; i >= 0; i--) {
newArr.push(arr[i])
}
return newArr
}
console.log(reverseArray(["A", "B", "C"]))
// ["C", "B", "A"]

function reverseArrayInPlace(arr) {
for(let i = 0; i <= Math.floor((arr.length - 1) / 2); i++) {
let tempArrElement = arr[i]
arr[i] = arr[arr.length - 1 - i]
arr[arr.length - 1 - i] = tempArrElement
}
return arr
}
console.log(reverseArrayInPlace([1, 2, 3, 4, 5]))
// [5, 4, 3, 2, 1]```

### A list

Objects, as generic blobs of values, can be used to build all sorts of data structures. A common data structure is the list (not to be confused with array). A list is a nested set of objects, with the first object holding a reference to the second, the second to the third, and so on.

```let list = {
value: 1,
rest: {
value: 2,
rest: {
value: 3,
rest: null
}
}
};```

Write a function `arrayToList` that builds up a list structure like the one shown when given `[1, 2, 3]` as argument.

```function arrayToList(array) {
let list = null;
for (let i = array.length - 1; i >= 0; i--) {
list = {value: array[i], rest: list};
}
return list;
}

console.log(arrayToList([1, 2, 3]))
/*
{
value: 1,
rest: {
value: 2,
rest: {
value: 3,
rest: null
}
}
}

*/```

Also write a `listToArray`function that produces an array from a list.

```function arrayToList(array) {
let list = null;
for (let i = array.length - 1; i >= 0; i--) {
list = {value: array[i], rest: list};
}
return list;
}

const newList = arrayToList([1, 2, 3])

function listToArray(list) {
const arr = []
for(let node = list; node; node = node.rest) {
arr.push(node.value)
}
return arr
}

console.log(listToArray(newList))
// [1, 2, 3]```

### Deep comparison

Write a function `deepEqual` that takes two values and returns true only if they are the same value or are objects with the same properties, where the values of the properties are equal when compared with a recursive call to `deepEqual`.