5 Basic Data Structures - theoriginalvisagie/JavaScript-Algorithms-and-Data-Structures GitHub Wiki
Data can be stored and accessed in many ways. You already know some common JavaScript data structures — arrays and objects.
Arrays:
Basic Arrays:
The below is an example of the simplest implementation of an array data structure. This is known as a one-dimensional array, meaning it only has one level, or that it does not have any other arrays nested within it. Notice it contains booleans, strings, and numbers, among other valid JavaScript data types:
let simpleArray = ['one', 2, 'three', true, false, undefined, null];
console.log(simpleArray.length);
A multi-dimensional array, or an array that contains other arrays looks like the following:
let complexArray = [
[
{
one: 1,
two: 2
},
{
three: 3,
four: 4
}
],
[
{
a: "a",
b: "b"
},
{
c: "c",
d: "d"
}
]
];
Bracket Notation:
The fundamental feature of any data structure is, of course, the ability to not only store data, but to be able to retrieve that data on command. In an array, each array item has an index. This index doubles as the position of that item in the array, and how you reference it. However, it is important to note, that JavaScript arrays are zero-indexed, meaning that the first element of an array is actually at the zeroth position.
In order to retrieve an element from an array we can enclose an index in brackets and append it to the end of an array, this is known as bracket notation.
let ourArray = ["a", "b", "c"];
let ourVariable = ourArray[0];
// Output is "a".
Adding to an array:
We have to ways of adding elements to an array. The one is the .push() method and the other is .unshift().
"Push" adds an item to the end of an array and "unshit" adds an item to the beginning of an array.
let romanNumerals = ['XXI', 'XXII'];
romanNumerals.unshift('XIX', 'XX');
// Output ['XIX', 'XX','XXI', 'XXII'].
romanNumerals.push('XXX');
// Output ['XIX', 'XX','XXI', 'XXII','XXX'].
Removing Items:
Just as we can add items to an array, we can also move them. .pop() removes the last item in an array and .shift() removes the first item in an array.
let greetings = ['whats up?', 'hello', 'see ya!'];
greetings.pop();
// Output = ['whats up?', 'hello'].
greetings.shift();
// Output = ['hello'].
Splice():
What if we want to remove an element from somewhere in the middle? Or remove more than one element at once? Well, that's where splice() comes in. splice() allows us to do just that: remove any number of consecutive elements from anywhere in an array.
splice() can take up to 3 parameters, but for now, we'll focus on just the first 2. The first two parameters of splice() are integers which represent indexes, or positions, of items in the array that splice() is being called upon. And remember, arrays are zero-indexed, so to indicate the first element of an array, we would use 0. splice()'s first parameter represents the index on the array from which to begin removing elements, while the second parameter indicates the number of elements to delete. For example:
let array = ['today', 'was', 'not', 'so', 'great'];
array.splice(2, 2);
// Output = ['today', 'so', 'great'].
You can use the third parameter, comprised of one or more element(s), to add to the array. This can be incredibly useful for quickly switching out an element, or a set of elements, for another.
const numbers = [10, 11, 12, 12, 15];
const startIndex = 3;
const amountToDelete = 1;
numbers.splice(startIndex, amountToDelete, 13, 14);
console.log(numbers);
// Output = [10, 11, 12, 13, 14, 15].
Copy Array Items:
There are multiple ways to copy the elements of an array. We are going to look at .slice() in this example. Rather than modifying an array, slice() copies or extracts a given number of elements to a new array, leaving the array it is called upon untouched.
slice() takes only 2 parameters:
- The index at which to begin extraction
- the second is the index at which to stop extraction (extraction will occur up to, but not including the element at this index).
let weatherConditions = ['rain', 'snow', 'sleet', 'hail', 'clear'];
let todaysWeather = weatherConditions.slice(1, 3);
// todaysWeather will be equal to ['snow', 'sleet'].
Another way we can copy items it si by using the spread operator. This allows us to easily copy all of an array's elements, in order, with a simple and highly readable syntax. The spread syntax simply looks like this: ....
let thisArray = [true, true, undefined, false, null];
let thatArray = [...thisArray];
Combine Arrays:
Another huge advantage of the spread operator is the ability to combine arrays, or to insert all the elements of one array into another, at any index. With more traditional syntaxes, we can concatenate arrays, but this only allows us to combine arrays at the end of one, and at the start of another.
let thisArray = ['sage', 'rosemary', 'parsley', 'thyme'];
let thatArray = ['basil', 'cilantro', ...thisArray, 'coriander'];
Array Operations:
indexOf():
Since arrays can be changed, or mutated, at any time, there's no guarantee about where a particular piece of data will be on a given array, or if that element even still exists. Luckily, JavaScript provides us with another built-in method, indexOf(), that allows us to quickly and easily check for the presence of an element on an array.
let fruits = ['apples', 'pears', 'oranges', 'peaches', 'pears'];
fruits.indexOf('dates'); // returns -1
fruits.indexOf('oranges'); // returns 2
fruits.indexOf('pears'); // returns 1
Iterate Through An Array:
Sometimes when working with arrays, it is very handy to be able to iterate through each item to find one or more elements that we might need, or to manipulate an array based on which data items meet a certain set of criteria. Below we are going to look at the for() loop.
function greaterThanTen(arr) {
let newArr = [];
for (let i = 0; i < arr.length; i++) {
if (arr[i] > 10) {
newArr.push(arr[i]);
}
}
return newArr;
}
greaterThanTen([2, 12, 8, 14, 80, 0, 1]);
Multi-Dimensional Arrays:
One of the most powerful features when thinking of arrays as data structures, is that arrays can contain, or even be completely made up of other arrays.
let nestedArray = [
['deep'],
[
['deeper'], ['deeper']
],
[
[
['deepest'], ['deepest']
],
[
[
['deepest-est?']
]
]
]
];
The deep array is nested 2 levels deep. The deeper arrays are 3 levels deep. The deepest arrays are 4 levels, and the deepest-est? is 5.
Objects:
At their most basic, objects are just collections of key-value pairs. In other words, they are pieces of data (values) mapped to unique identifiers called properties (keys).
const tekkenCharacter = {
player: 'Hwoarang',
fightingStyle: 'Tae Kwon Doe',
human: true
};
The above code defines a Tekken video game character object called tekkenCharacter. It has three properties, each of which map to a specific value. We can assign additional properties to the object by using dot or bracket notation.
Nested Objects:
Now let's take a look at a slightly more complex object. Object properties can be nested to an arbitrary depth, and their values can be any type of data supported by JavaScript, including arrays and even other objects.
let nestedObject = {
id: 28802695164,
date: 'December 31, 2016',
data: {
totalUsers: 99,
online: 80,
onlineStatus: {
active: 67,
away: 13,
busy: 8
}
}
};
While structures can quickly become complex, we can still use the same notations to access the information we need.
nestedObject.data.onlineStatus.busy = 10;
Removing Items from an object:
Let's revisit our foods object example one last time. If we wanted to remove the apples key, we can remove it by using the delete keyword like this:
let foods = {
apples: 25,
oranges: 32,
plums: 28,
bananas: 13,
grapes: 35,
strawberries: 27
};
delete foods.apples;
Checking For A Property:
avaScript provides us with two different ways to do this. One uses the hasOwnProperty() method and the other uses the in keyword. If we have an object users with a property of Alan, we could check for its presence in either of the following ways:
users.hasOwnProperty('Alan');
'Alan' in users;
Iterate Through An Object:
Sometimes you may need to iterate through all the keys within an object. This requires a specific syntax in JavaScript called a for...in statement
for (let user in users) {
console.log(user);
}