Data Structures From Scratch: Array
Tags: ruby, codenewbie, computerscience, tutorial
Published: 2020-06-11 16:16:23

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](https://dev.to/sarah_chima/the-big-o-notation-an-introduction-34f7). 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](https://www.udemy.com/course/master-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](https://developer.mozilla.org/en-US/docs/Web/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](https://www.ruby-lang.org/en/documentation/). 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`](https://ruby-doc.org/core-2.7.0/Array.html) from scratch is to create the class, so let's get that done. 
```ruby
class MyArray
end 
```

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

## Initialize the Class

The next step is to [initialize](https://www.geeksforgeeks.org/the-initialize-method-in-ruby/#:~:text=The%20initialize%20method%20is%20part,not%20used%20inside%20initialize%20method) 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`](https://www.rubyguides.com/2018/11/attr_accessor/) 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`](https://ruby-doc.org/core-2.7.0/Hash.html) (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.
```ruby
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` - [<code>.push(<i>element</i>)</code>](https://ruby-doc.org/core-2.7.0/Array.html#method-i-push)
* returning the element at a given index - [<code>.at(<i>index</i>)</code>](https://ruby-doc.org/core-2.7.0/Array.html#method-i-at)
* removing the last element of the `array` - [`.pop()`](https://ruby-doc.org/core-2.7.0/Array.html#method-i-pop)
* removing an element at a given index - [<code>.delete_at(<i>index</i>)</code>](https://ruby-doc.org/core-2.7.0/Array.html#method-i-delete_at)
* removing a given element - [<code>.delete(<i>element</i>)</code>](https://ruby-doc.org/core-2.7.0/Array.html#method-i-delete)
* checking to see if an element exists in the array - [<code>.includes?(<i>element</i>)</code>](https://ruby-doc.org/core-2.7.0/Array.html#method-i-include-3F)

For the sake of restricting all of our methods to one purpose as well as maintaining [DRY](https://en.wikipedia.org/wiki/Don%27t_repeat_yourself) code, we will also create an additional method called <code>shift_elements(<i>index</i>)</code>, which will shift the elements within the `array` when an element is deleted using our <code>.delete(<i>element</i>)</code> or <code>.delete_at(<i>index</i>)</code> methods.

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

#### <code>.push(<i>element</i>)</code>

In order to add an element to our `array`, we are going to create the <code>.push(<i>element</i>)</code> 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. 

```ruby
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**. 

#### <code>.at(<i>index</i>)</code>

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

Example 1:
```ruby
def at(index)
  if index < @length
    @elements[index]
  else 
    return nil
  end
end 
```

Example 2:
```ruby
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](https://www.rubyguides.com/ruby-tutorial/ruby-if-else/). If the index does not exist, we want our method to return `nil` as that is the normal functionality of the <code>.at(<i>index</i>)</code> method. 

Now, in the first example, we are using an `array` method referred to as an [element referrence](https://ruby-doc.org/core-2.7.0/Array.html#method-i-5B-5D) to access the element. In the second example, we use the `hash` method [`.each_value`](https://ruby-doc.org/core-2.7.0/Hash.html#method-i-each_value) in combination with [`.with_index`](https://www.rubydoc.info/stdlib/core/Enumerator: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!
```ruby
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 
```

#### <code>.delete_at(<i>index</i>)</code>

The next method we are going to build that removes an element from our `array` is the lovely <code>.delete_at(<i>index</i>)</code> 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 <code>shift_elements(<i>index</i>)</code> method that I mentioned earlier. 

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

```ruby
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`](https://www.w3resource.com/ruby/ruby-loops-statements.php), 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`](https://www.rubyguides.com/2018/10/puts-vs-print/) statement.  

Now that we have that method built, let's move on to the implementation of our <code>.delete_at(<i>index</i>)</code>.
```ruby
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 
```

#### <code>.delete(<i>element</i>)</code>

The last removal method we'll be covering in this tutorial is <code>.delete(<i>element</i>)</code> 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 <code>shift_elements(<i>index</i>)</code> method. Let's build it out!
```ruby
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
```

#### <code>.includes?(<i>element</i>)</code>

Now for the final method we'll be building in this tutorial, and my personal favorite: <code>.includes?(<i>element</i>)</code>. This method will traverse our `array` looking for the given element and return a [`boolean`](https://www.rubyguides.com/2019/02/ruby-booleans/). 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!
```ruby
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. 
```ruby
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](https://www.alltrails.com/trail/us/california/aquinas-trail) that my fiancé and I did near Los Gatos, Ca.*