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
returnsundefined
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 theArray
deleteCount
- this is the number of values you would like to remove from theArray
(starting from thestart
argument)
items
- this is the values you would like to add to theArray
, starting from thestart
argumentIf the
items
argument is empty, thespice
method will only remove items
We pass 3 arguments to splice
:
-
5
: we want to start changing thejediCouncil
Array
at index position5
-
0
: we do not want to delete anything fromjediCouncil
; therefore, this value is0
-
"obi wan"
: this is the value we would like to add to index position5
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
: anumber
that is initialized with the value of0
-
data
: anobject
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 thisMyOwnArray
class? This explains why the last index position and your length always have a difference of1
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 Array
s 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!
Top comments (2)
Good guide lots of useful information. These data structures take a while to get used to.
appreciate that!