Data Structures From Scratch: Array

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

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 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

1. remove the last element from the array
2. update the length of our array by subtracting 1
3. 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.