As many of you know, I have been searching for my first dev role for quite some time now. It took me completing quite a few technical interviews over the span of 6 or 7 months to narrow down what I thought was the main reason I wasn’t successfully making it past the technical interview round. I realized my weakness was my lack of knowledge in data structures outside of anarray and ahash, as well as my unfamiliarity of some pretty important CS principles such asBig O Notation. Once realizing my weaknesses, I sought out to strengthen them so that I could

1. better increase my chances of landing my first role
2. become a better and more well rounded dev

In December of 2019, I enrolled in Andrei Neagoie's courseMastering the Coding Interview: Data Structures + Algorithms. I still haven’t managed to complete the entire course just yet, but I have had the opportunity to make my way through the Big O section as well as the entirety of the course’s data structures portion. While working through this course, I learned how to code data structures from scratch inJavaScript which inspired me to create this blog series.

With this blog series, I will be writing tutorials on how to create some of the more popular data structures from scratch in, my favorite programming language,Ruby. This is the first installment in this series and I figured we’d cover one of the more basic data structures (and one of the very first I ever learned),arrays. Let’s dive on in and get started!

Create the Class

The first step in the process of creating anarray from scratch is to create the class, so let's get that done.

classMyArrayend

Awesome! Now let's move on to the next step.

Initialize the Class

The next step is toinitialize our class. Before doing this, we need to think about what variables should be included in every instance of anarray. One thing we know that is kept track of in regards toarrays is the amount of elements within thearray, also known as the length of thearray. We will implement anattr_reader for the length so that we can access the length of ourarray using.length outside of our class.

We also know that we must keep track of the elements that exist within thearray. To do this, I’m going to have us save the elements within thearray as ahash (the next data structure in this series!!). Why? Well, I don’t really see the purpose of using anarray in my demonstration of creating anarray from scratch, so we are going to make use of another great data structures!

Alright, let’s go ahead and build out the initialize method.

classMyArrayattr_reader:lengthdefinitialize@length=0@elements={}endend

We initialize the class with alength of0 because when thearray is created, no elements are present. The same logic is used for the@elements variable that is set to an emptyhash. With that done, let's move on to the next step.

Array Methods

The next step in the process of building out ourarray is to consider which methods we should build out. There areso manyarray methods and for the purpose of this blog post we are only going to cover a few.Please feel free to explore otherarray methods that you use frequently so that you can practice building out that functionality. The methods that I've chose to cover are

• adding an element to thearray -.push(element)
• returning the element at a given index -.at(index)
• removing the last element of thearray -.pop()
• removing an element at a given index -.delete_at(index)
• removing a given element -.delete(element)
• checking to see if an element exists in the array -.includes?(element)

For the sake of restricting all of our methods to one purpose as well as maintainingDRY code, we will also create an additional method calledshift_elements(index), which will shift the elements within thearray when an element is deleted using our.delete(element) or.delete_at(index) methods.

Let's dive on in to the first method we'll be creating:.push(element).

.push(element)

In order to add an element to ourarray, we are going to create the.push(element) method which adds the new element to the end of ourarray. In this method, we need to make sure to add the element to thearray as well as increasing that@length count by 1.

defpush(element)@elements[@length]=element@length+=1end

If you are wondering why I set the element's index to the@length of thearray, think about the differences between the way indices and length are counted. Indices start at 0, whereas length starts at 1. By setting the element to index of@length, I am setting it to the index of the last element in thearrayplus 1.

.at(index)

The next method we are going to build out is.at(index) which allows us to access and retrieve the element at a provided index. We can do this two different ways.

Example 1:

defat(index)ifindex<@length@elements[index]elsereturnnilendend

Example 2:

defat(index)ifindex<@length@elements.each_value.with_index{|value,i|returnvalueifi==index}elsereturnnilendend

In both examples we check to make sure that the index we are attempting to access is not out of range for ourarray using aconditional. If the index does not exist, we want our method to returnnil as that is the normal functionality of the.at(index) method.

Now, in the first example, we are using anarray method referred to as anelement referrence to access the element. In the second example, we use thehash method.each_value in combination with.with_index to traverse over each value in ourarray until the index of a value matches the provided index.

Note: I personally prefer to use the second example as it isn't making use of a built inarray method, however, I will be using the first example in the remainder of our methods to save myself time.

Let's move on to methods that allow us to remove elements from ourarray.

.pop()

If there is ever a need to remove and return the last element in anarray,.pop() is the way to go. There are three things that we need to accomplish when building out this method. We need to

1. remove the last element from thearray
2. update the length of ourarray by subtracting 1
3. return that element

In order to return the last element in thearray once the other two steps have been completed, we must save the element to a new variable before removing it from thearray. Let's build it out!

defpop()# save the last element to a new variablelast_element=@elements[@length-1]# delete the last element@elements.delete(@length-1)# subtract 1 from the length@length-=1# return the last elementreturnlast_elementend

.delete_at(index)

The next method we are going to build that removes an element from ourarray is the lovely.delete_at(index) method. With this method, we can provide the index of the element we wish to remove from thearray. This method returns the removed element just like.pop().

Now, this type of element removal is a bit more involved because we aren't just removing the last element in thearray. We will need to shift the index of all remaining elements in thearray up by 1. To do this, we are going to create theshift_elements(index) method that I mentioned earlier.

To build out this method, we are going to require a parameter: the index of the element being removed.

defshift_elements(index)counter=indexwhilecounter<@length-1do@elements[counter]=@elements[counter+1]counter+=1end@elements.delete(@length-1)@length-=1end

At the end of ourwhile loop, ourarray will look a little funky. The last element in thearray will be repeated two times which means we need to remove one of them, hence our deletion of the last element in thearray. If you'd like to take a closer look yourself, feel free to throw in aprint statement.

Now that we have that method built, let's move on to the implementation of our.delete_at(index).

defdelete_at(index)# make sure index given is within rangeifindex<@length# save the to be deleted element for returnelement=@elements[index]# shift and remove desired elementself.shift_elements(index)returnelementelsereturnnilendend

.delete(element)

The last removal method we'll be covering in this tutorial is.delete(element) which allows us to delete and return the provided element. This method is pretty similar to the one above except for one thing: we'll need to find the index of the given element in order to use ourshift_elements(index) method. Let's build it out!

defdelete(element)@elements.each_value.with_indexdo|value,index|ifvalue==elementself.shift_elements(index)# if given element does not exist in arrayelsifindex==@length-1returnnilendendreturnelementend

.includes?(element)

Now for the final method we'll be building in this tutorial, and my personal favorite:.includes?(element). This method will traverse ourarray looking for the given element and return aboolean. If ourarray does not include the given element, the method will returnfalse. If it does include the element, the method will returntrue. Let's go ahead and build out our finalarray method!

defincludes?(element)result=false@elements.each_value{|value|result=trueifvalue==element}returnresultend

Final Product

Awesome! We've gone through and built out all of the methods for anarray that we planned to build.Again, there are many otherarray methods, but for the purpose of this blog post we only did a select few.

Let's go ahead and take a look at the final product that we've built.

classMyArrayattr_reader:lengthdefinitialize@length=0@elements={}enddefpush(element)@elements[@length]=element@length+=1enddefat(index)ifindex<@length@elements.each_value.with_index{|value,i|returnvalueifi==index}elsereturnnilendenddefpop()last_element=@elements[@length-1]@elements.delete(@length-1)@length-=1returnlast_elementenddefshift_elements(index)counter=indexwhilecounter<@length-1do@elements[counter]=@elements[counter+1]counter+=1end@elements.delete(@length-1)@length-=1enddefdelete_at(index)ifindex<@lengthelement=@elements[index]self.shift_elements(index)returnelementelsereturnnilendenddefdelete(element)@elements.each_value.with_indexdo|value,index|ifvalue==elementself.shift_elements(index)elsifindex==@length-1returnnilendendreturnelementenddefincludes?(element)result=false@elements.each_value{|value|result=trueifvalue==element}returnresultendend

Final Thoughts

It's been a lot of fun creating this for y'all and I'm really excited to move on to the next installment in this series,hashes. I hope that this tutorial has been helpful. If there is anything that you'd like to add please feel free to do so in the discussion section below. Or if you want to build out your favoritearray method and show it off, please feel free to share that in the discussion as well!

Thank you for reading and happy coding!

Note: The cover image of this blog post is brought to you from a recenthike that my fiancé and I did near Los Gatos, Ca.