martincartledge.github.io

This is the second post in my series Data Structures and Algorithms using JavaScript. Last week, I discussed Time Complexity, Space Complexity, and Big O Notation. This week I am going to talk about a very popular data structure that most programmers use on a daily basis, the Array. In this post, I will cover the Big O of common Array actions (push, pop, etc) and we will also walk through the process of creating our very own Array data structure! Let’s get started.

What is an Array?

A collection of multiple values that can be stored using a single variable

The length can not be fixed
The types of values can not be fixed
Can not use strings as an index to an element, must use an integer

Static vs Dynamic Arrays

Static

Fixed in size

Dynamic

Copy and rebuild Array in new location with more memory, expands as you add elements

Common Array actions

Push O(1)

Appends a new value at the end of an Array and returns the new length

Relies on the length property to know where to insert new values
If length does not exist or can not be converted to a number, 0 is used

const jediCouncil = ["yoda", "mace windu", "plo koon", "ki-adi-mundi"];

jediCouncil.push("anakin");

console.log(jediCouncil);

// 'yoda', 'mace windu', 'plo koon', 'ki-adi-mundi', 'anakin'

First, we use the const keyword to create a new variable with the identifier jediCouncil. The value assigned to jediCouncil is an Array of values that are of type string.

const jediCouncil = ["yoda", "mace windu", "plo koon", "ki-adi-mundi"];

Next, we call the push method on the jediCouncil Array with a single argument anakin.

jediCouncil.push("anakin");

When we log our jediCouncil on the next line, we see that the value anakin is now the last value in our jediCouncil Array.

console.log(jediCouncil);
// 'yoda', 'mace windu', 'plo koon', 'ki-adi-mundi', 'anakin'

Since there is only one action taken and we don’t have to iterate through our Array for this operation the Big O of the push method is O(1).

Pop O(1)

Removes the last value in Array and returns that value

If you call on an empty Array, pop returns undefined

For this example, we want anakin out of the jediCouncil, we can use the pop method for that:

const jediCouncil = [
  "yoda",
  "mace windu",
  "plo koon",
  "ki-adi-mundi",
  "anakin",
];

jediCouncil.pop();

console.log(jediCouncil);

// 'yoda', 'mace windu', 'plo koon', 'ki-adi-mundi'

First, we use the const keyword to create a new variable with the identifier jediCouncil. The value assigned to jediCouncil is an Array of values that are of type string.

const jediCouncil = [
  "yoda",
  "mace windu",
  "plo koon",
  "ki-adi-mundi",
  "anakin",
];

Next, we call the pop method on the jediCouncil Array, we do not need an argument when calling this method.

jediCouncil.pop();

Now, when we log our jediCouncil on the next line, we should see that the value anakin is no longer in our jediCouncil Array

console.log(jediCouncil);
// 'yoda', 'mace windu', 'plo koon', 'ki-adi-mundi'

Later, anakin 👋🏻

Using pop makes removing the last item from your Array very quick and painless. Since this is the only operation that is performed, the Big O of the pop method is O(1).

Shift O(n)

Removes the first value in Array and returns that value

Shifts the values and their indexes consecutively

const jediCouncil = ["yoda", "mace windu", "plo koon", "ki-adi-mundi"];

jediCouncil.shift();

console.log(jediCouncil);

// 'mace windu', 'plo koon', 'ki-adi-mundi'

First, we use the const keyword to declare a new variable with the identifier jediCouncil. The value assigned to jediCouncil is an Array of values that are of type string.

Note: I am noting the index position of each value, this will help illustrate what shift does under the hood later

const jediCouncil = ["yoda", "mace windu", "plo koon", "ki-adi-mundi"];
//index: 0 //index: 1    //index: 2  //index: 3

Next, I call the shift method on our jediCouncil variable.

jediCouncil.shift();

On the next line, I use console.log to log the new value of jediCouncil. Notice how the index positions have changed. Why is that?

When shift is called on our jediCouncil Array, the value yoda is removed. Since this value was in index position 0, we have to iterate through the Array and update each value’s index position. This is why the shift method has a Big O of O(n).

console.log(jediCouncil);
// 'mace windu', 'plo koon', 'ki-adi-mundi'
// index: 0       index: 1     index: 2

Now we can see that yoda has been removed and all of the other values in jediCouncil have been shifted over to 1 less index position.

Splice O(n)

Remove, replace, or add new values to an Array

const jediCouncil = ["yoda", "mace windu", "plo koon", "ki-adi-mundi"];

jediCouncil.splice(4, 0, "obi wan");

console.log(jediCouncil);

// 'yoda', 'mace windu', 'plo koon', 'ki-adi-mundi', 'obi wan'

First, we use the const keyword to create a new variable with the identifier jediCouncil. The value assigned to jediCouncil is an Array of values that are of type string.

const jediCouncil = ["yoda", "mace windu", "plo koon", "ki-adi-mundi"];

Next, we call the splice method on the jediCouncil Array.

Note: the splice method takes 3 arguments:

start - this is the index you would like to start changing the Array

deleteCount - this is the number of values you would like to remove from the Array (starting from the start argument)

items - this is the values you would like to add to the Array, starting from the start argument

If the items argument is empty, the spice method will only remove items

We pass 3 arguments to splice:

5: we want to start changing the jediCouncil Array at index position 5
0: we do not want to delete anything from jediCouncil; therefore, this value is 0
"obi wan": this is the value we would like to add to index position 5

jediCouncil.splice(5, 0, "obi wan");

When we log our jediCouncil on the next line, we can see that obi wan has been added to jediCouncil in index position 5; which, in this case, is the last position.

console.log(jediCouncil);
// 'yoda', 'mace windu', 'plo koon', 'ki-adi-mundi', 'obi wan'

Welcome aboard, obi wan 👍🏻, I think you will fit in nicely

Although we did not shift any values or their index positions, we always take the worst case when determining Big O; therefore, the Big O of splice is O(n)

Let’s Create an Array Data Structure

This section assumes you have some knowledge of how classes work for JavaScript. If classes are new for you, fear not! I will be writing a post on those in the near future. In the meantime, you can read more about them right here.

We know how the core pieces of an Array work, so let’s build our own Array data structure!

class MyOwnArray {
  constructor() {
    this.length = 0;
    this.data = {};
  }

  push(item) {
    this.data[this.length] = item;
    this.length++;
    return this.length;
  }

  get(index) {
    return this.data[index];
  }

  pop() {
    const lastItem = this.data[this.length - 1];
    delete this.data[this.length - 1];
    this.length--;
    return lastItem;
  }
}

const myOwnArray = new MyOwnArray();

myOwnArray.push("phantom menace");

myOwnArray.get(0);

myOwnArray.pop();

We start by using the class keyword to create a new JavaScript class. We give our new class the identifier MyOwnArray.

class MyOwnArray {

Constructor

Inside of our MyOwnArray class we write our constructor function. The constructor is a method that is responsible for creating an object for that class.

We use the this keyword to create and bind two fields to the scope of our MyOwnArray class:

length: a number that is initialized with the value of 0
data: an object that is initialized with the value of an empty object {}

constructor() {
  this.length = 0;
  this.data = {};
}

Push

We create a method with the identifier push that has a single parameter, item. Keep in mind, this item parameter can be any value that we want to append to our Array. In our example, we are calling the push method with the value 'phantom menace' as the only argument (myOwnArray.push('phantom menace')).

push(item) { // item = 'phantom menace'

Inside of our push method, we assign a key-value pair for our data field.

To assign the key value, we use the length field value inside of bracket notation [].

Next, we assign our value to item

this.data[this.length] = item;
// { 0: 'phantom menace' }

We increment the value of our length field by 1 and return the value of length

this.length++;
// length = 1
return this.length;

Note: Did you notice that I incremented the length field in this MyOwnArray class? This explains why the last index position and your length always have a difference of 1

Let me show you an example:

const starWarsMovies = [
  "phantom menace",
  "attack of the clones",
  "revenge of the sith",
  "a new hope",
  "empire strikes back",
  "return of the jedi",
];

console.log(starWarsMovies.length);
// 6

console.log(starWarsMovies[6]);
// undefined

console.log(starWarsMovies[5]);
// return of the jedi

As you can see, we the starWarsMovies Array with 6 items. When we console.log the length it returns 6 as we would expect. What happens when we try to retrieve the value at the 6th index position? We get undefined. This is because we always increment our length after we add an item to an Array.

Get

Next, we create a method with an identifier of get. This method will be responsible for returning a value from our data field.

Our get method has a single parameter, index. Inside of our get method, we use the index parameter and bracket notation [] to return that value from the data field.

In our example, we want to retrieve the value that is index position 0 (myOwnArray.get(0))

get(index) { // index = 0
  return this.data[index];
  // 'phantom menace'
}

Pop

Next, we create a method with the identifier pop. As you might suspect, this method will be responsible for removing the last item in an Array. This method takes no arguments.

pop() {

Inside of our pop method we use the const keyword to create a new variable with the identifier lastItem. You can probably guess what we will use this for. We use bracket notation [] and the value of our length field (decremented by one) to pull off the value of our last item in the data field.

const lastItem = this.data[this.length - 1];

Since data is an object, we can use the delete operator, followed by the property of the last item in our data object to remove it.

We want to make sure we decrement the value of our length field by 1, and then we return the value of lastItem.

delete this.data[this.length - 1];
this.length--;
return lastItem;

In Summary

I hope you found diving into how Arrays work in regards to their methods, Big O, and under the hood to be as illuminating as I did. Now we have a much stronger grasp on how we can harness the power of these important data structures. Next week I will be talking about Hash Tables. Can’t wait, see you then!