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 an array and a hash, as well as my unfamiliarity of some pretty important CS principles such as Big O Notation. Once realizing my weaknesses, I sought out to strengthen them so that I could
- better increase my chances of landing my first role
- become a better and more well rounded dev
In December of 2019, I enrolled in Andrei Neagoie's course Mastering 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 in JavaScript 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 an array from scratch is to create the class, so let's get that done.
class MyArray
end
Awesome! Now let's move on to the next step.
Initialize the Class
The next step is to initialize our class. Before doing this, we need to think about what variables should be included in every instance of an array. One thing we know that is kept track of in regards to arrays is the amount of elements within the array, also known as the length of the array. We will implement an attr_reader for the length so that we can access the length of our array using .length outside of our class.
We also know that we must keep track of the elements that exist within the array. To do this, I’m going to have us save the elements within the array as a hash (the next data structure in this series!!). Why? Well, I don’t really see the purpose of using an array in my demonstration of creating an array 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.
class MyArray
attr_reader :length
def initialize
@length = 0
@elements = {}
end
end
We initialize the class with a length of 0 because when the array is created, no elements are present. The same logic is used for the @elements variable that is set to an empty hash. With that done, let's move on to the next step.
Array Methods
The next step in the process of building out our array is to consider which methods we should build out. There are so many array methods and for the purpose of this blog post we are only going to cover a few. Please feel free to explore other array 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 the
array-.push(element) - returning the element at a given index -
.at(index) - removing the last element of the
array-.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 maintaining DRY code, we will also create an additional method called shift_elements(index), which will shift the elements within the array 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 our array, we are going to create the .push(element) method which adds the new element to the end of our array. In this method, we need to make sure to add the element to the array as well as increasing that @length count by 1.
def push(element)
@elements[@length] = element
@length += 1
end
If you are wondering why I set the element's index to the @length of the array, 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 the array plus 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:
def at(index)
if index < @length
@elements[index]
else
return nil
end
end
Example 2:
def at(index)
if index < @length
@elements.each_value.with_index { |value, i| return value if i == index }
else
return nil
end
end
In both examples we check to make sure that the index we are attempting to access is not out of range for our array using a conditional. If the index does not exist, we want our method to return nil as that is the normal functionality of the .at(index) method.
Now, in the first example, we are using an array method referred to as an element referrence to access the element. In the second example, we use the hash method .each_value in combination with .with_index to traverse over each value in our array 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 in array 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 our array.
.pop()
If there is ever a need to remove and return the last element in an array, .pop() is the way to go. There are three things that we need to accomplish when building out this method. We need to
- remove the last element from the
array - update the length of our
arrayby subtracting 1 - return that element
In order to return the last element in the array once the other two steps have been completed, we must save the element to a new variable before removing it from the array. Let's build it out!
def pop()
# save the last element to a new variable
last_element = @elements[@length - 1]
# delete the last element
@elements.delete(@length - 1)
# subtract 1 from the length
@length -= 1
# return the last element
return last_element
end
.delete_at(index)
The next method we are going to build that removes an element from our array is the lovely .delete_at(index) method. With this method, we can provide the index of the element we wish to remove from the array. 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 the array. We will need to shift the index of all remaining elements in the array up by 1. To do this, we are going to create the shift_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.
def shift_elements(index)
counter = index
while counter < @length - 1 do
@elements[counter] = @elements[counter + 1]
counter += 1
end
@elements.delete(@length - 1)
@length -= 1
end
At the end of our while loop, our array will look a little funky. The last element in the array will be repeated two times which means we need to remove one of them, hence our deletion of the last element in the array. If you'd like to take a closer look yourself, feel free to throw in a print statement.
Now that we have that method built, let's move on to the implementation of our .delete_at(index).
def delete_at(index)
# make sure index given is within range
if index < @length
# save the to be deleted element for return
element = @elements[index]
# shift and remove desired element
self.shift_elements(index)
return element
else
return nil
end
end
.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 our shift_elements(index) method. Let's build it out!
def delete(element)
@elements.each_value.with_index do |value, index|
if value == element
self.shift_elements(index)
# if given element does not exist in array
elsif index == @length - 1
return nil
end
end
return element
end
.includes?(element)
Now for the final method we'll be building in this tutorial, and my personal favorite: .includes?(element). This method will traverse our array looking for the given element and return a boolean. If our array does not include the given element, the method will return false. If it does include the element, the method will return true. Let's go ahead and build out our final array method!
def includes?(element)
result = false
@elements.each_value { |value| result = true if value == element }
return result
end
Final Product
Awesome! We've gone through and built out all of the methods for an array that we planned to build. Again, there are many other array 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.
class MyArray
attr_reader :length
def initialize
@length = 0
@elements = {}
end
def push(element)
@elements[@length] = element
@length += 1
end
def at(index)
if index < @length
@elements.each_value.with_index { |value, i| return value if i == index }
else
return nil
end
end
def pop()
last_element = @elements[@length - 1]
@elements.delete(@length - 1)
@length -= 1
return last_element
end
def shift_elements(index)
counter = index
while counter < @length - 1 do
@elements[counter] = @elements[counter + 1]
counter += 1
end
@elements.delete(@length - 1)
@length -= 1
end
def delete_at(index)
if index < @length
element = @elements[index]
self.shift_elements(index)
return element
else
return nil
end
end
def delete(element)
@elements.each_value.with_index do |value, index|
if value == element
self.shift_elements(index)
elsif index == @length - 1
return nil
end
end
return element
end
def includes?(element)
result = false
@elements.each_value { |value| result = true if value == element }
return result
end
end
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 favorite array 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 recent hike that my fiancé and I did near Los Gatos, Ca.
Top comments (5)
Great post! Although of course
arrayis actually an abstraction providing access to contiguous memory with boundary checks on pointer arithmetics and automatic reallocation on overflow, that is not the low level Ruby can go down to, and implementingarraywith Ruby hash is really a brilliant compromise. Hope you have fun learning the many many many other data structures!(Blockchain is just a hash linked list)
Nice post! I read through the post kind of missing the first part, and was thinking to myself, the way you have written your algorithm is really neat, it looks to have such nice structure, then I went back up trying to find if there is a specification you were using to write the algorithm and then bam! it's actually ruby! Either the syntax of ruby is really nice to read or I am really dumb (I think it's a bit of both!).
Ruby syntax is really nice to read 100%. 😊
Great post! Looking forward to reading the next one on hashmaps. Keep it up!
YOU ARE AN INSPIRATION. THANK YOU FOR THIS!!