Just recently, I transitioned careers to become a Software Developer using mainly Ruby and Ruby on Rails and wanted to strengthen my understanding of Data Structures & Algorithms, which I am sure would allow me to become a better programmer. So with this in mind, I decided to read The Well-Grounded Rubyist, Third Edition to better understand the basics of the Ruby language and A Common-Sense Guide to Data Structures and Algorithms, Second Edition to start implementing algorithms with Space and Time Complexity in mind.

While working through these books and a few blog posts from amazing people, I learned how to implement data structures from scratch in Ruby and in this post, we will do just that by trying to replicate the inner workings and methods of the array

What is an Array?

When a program declares an array, it allocates a contiguous set of empty cells for use in the program (Ruby implements dynamic arrays). This translates to an ordered collection of objects.

Ruby provides us with the class Array which we can instantiate, among other ways, by explicitly calling Array.new or by using the literal constructor [].

Building an Array from scratch

Let's begin by creating and initializing our class MyArray using a Hash to keep track of the elements within the collection. Also, Arrays keep track of the number of objects the collection contains at all times. We will implement an attr_reader to be able to query instances of MyArray about this information using MyArray#length.

class MyArray
  attr_reader :length

  def initialize(enum = nil)
    @length = 0
    @elements = Hash.new(nil)

    return if enum.nil?

    enum.each do |val|
      @elements[@length] = val
      @length += 1
    end
  end
end

We initialize our class with two instance variables, @length, set to 0 by default and @elements which is set to an empty Hash. Also, with this implementation, we can create a new MyArray containing the elements of a given enumerable object, increasing the @length on each iteration.

Before we move on, let's replicate even more the behavior and terminal output by creating a method that will allow us to instantiate our class like the way we instantiate arrays with literal constructors and specially similar to the class Set.

def self.[](*ary)
  new(ary)
end

def inspect
  sprintf('#<%s: [%s]>', self.class, @elements.values.inspect[1..-2])
end

alias to_s inspect

self.[](*ary) defines a class method and thanks to Ruby's syntactic sugar, we can now create instances of our class by calling MyArray['foo', 'bar']. The implementation of inspect was inspired by the way the Set class implements it. Resulting in a terminal output as shown below.

irb(main):001:0> MyArray['foo', 'bar']
=> #<MyArray: ["foo", "bar"]>

Now, let's start creating the methods we are going to need in order to cover the basic operations of reading, searching, inserting and deleting.

#[] (aliased as #slice)

When you have objects in an array you can retrieve those objects by using the #[] or #slice(index) methods. Retrieving single elements like this takes constant time in terms of Time Complexity analysis: O(1).

# Returns the element at the given index.
def [](index)
  @elements[index]
end

alias slice []

#[]=(index, element)

Let's now implement its setter equivalent #[]=(index, element) which allows us to set an element at a given index. In the case the given index is out of range for MyArray we set those slots between the given index and the last element to nil.

def []=(index, element)
  while index > @length
    @elements[@length] = nil
    @length += 1
  end
  @elements[index] = element
  @length += 1 if index == @length
end

#push(element) (aliased as #<<)

To add an element to the end of the collection, you can use #push(element) or #<<. Returning the collection itself. Here, knowing arrays have zero based indexing, we can implement it by setting the given element at the @length index, which is one slot to the right of the last element in the collection.

# Constant Time to add element to the end of collection
# Time Complexity: O(1)
def push(element)
  @elements[@length] = element
  @length += 1
  return self
end

alias << push

#pop

Here we remove the last element of the collection, reduce the @length instance variable by 1, and return the deleted element back which is accomplished by saving said element in a variable before removing it.

# Constant time to remove last element. Time Complexity: O(1)
def pop
  latest_element = @elements[@length -1]
  @elements.delete(@length -1)
  @length -= 1

  return latest_element
end

#unshift(value) and #shift

As you have seen, appending and removing elements from the end of the collection is fairly straight forward. Now, to accomplish the same operations at the beginning of the collection, we have to shift the remaining elements either to the right (if we are appending #unshift(value)) or to the left (if we are removing #shift). So, we will be creating a couple of private methods that will help us do just that.

#unshift(value)

class MyArray
  ...

  # Linear time to add at the beginning of collection.
  # Moves other values. Time Complexity: O(n)
  def unshift(value)
    self.unshift_elements(0, value)
    return self
  end

  private

  def unshift_elements(index, value)
    counter = @length - 1
    while counter >= index
      @elements[counter + 1] = @elements[counter]
      counter -= 1
    end
    @elements[index] = value
    @length += 1
  end
end

Here, when we call #unshift(value), we start shifting by 1 index to the right all elements of the collection, starting from the last one so we don't lose any value in the process. Once all elements are shifted, we set the element at index 0 to the value being inserted and increment the collection's length by 1.

#shift

Similarly, to remove the first element from the collection, we need to shift all elements but this time to the left. Basically, we start shifting left from index 1 until we have shifted the last element which will be duplicated, so we remove it and decrease our collection's length by 1.

class MyArray
  ...

  # Linear time to remove at the beginning of the collection.
  # Shifts other values. Time Complexity: O(n)
  def shift
    first_element = @elements[0]
    self.shift_elements(0)
    return first_element
  end

  private

  ...

  def shift_elements(index)
    counter = index
    while counter < (@length - 1)
      @elements[counter] = @elements[counter + 1]
      counter += 1
    end
    @elements.delete(@length - 1)
    @length -= 1
  end
end

Iterating over MyArray

In order to iterate over the collection, we need to implement the #each method. The idea behind #each is simple: by calling it on #MyArray collection it will yield back each item in it to the code block provided, one at a time. The return value of #each, when it’s given a block, is its receiver, the original collection. When it isn’t given a block, it returns an enumerator, which is what allows us to chain other methods like Enumerator#with_index.

# Calls the given block once for each element in the collection, passing
# the element as a parameter. Return an enumerator if no block is given.
def each
  return self.enum_for(__method__) unless block_given?

  counter = 0
  while counter < @length
    yield @elements[counter]
    counter += 1
  end

  return self
end

Having done that, we can implement the method #delete, which makes use of #each by first finding the index of the given element, removing it from the collection, and then shifting all remaining elements to the left.

#delete(element)

# Linear time to remove at an arbitrary location. Shifts other values.
# Time Complexity: O(n)
def delete(element)
  self.each.with_index do |value, index|
    if value == element
      self.shift_elements(index)
      return value
    end
  end

  return nil
end

The journey of learning the basics of Ruby and the inner working of collection classes like the Array has been an amazing experience and I'm looking forward to share all my learnings in subsequent posts like this one. I'll let you with the code for our entire MyArray class below and a link to the Github repo:

class MyArray
  attr_reader :length

  def initialize(enum = nil)
    @length = 0
    @elements = Hash.new(nil)

    return if enum.nil?

    enum.each do |val|
      @elements[@length] = val
      @length += 1
    end
  end

  def self.[](*ary)
    new(ary)
  end

  def inspect
    sprintf('#<%s: [%s]>', self.class, @elements.values.inspect[1..-2])
  end

  alias to_s inspect

  # Returns the element at the given index.
  def [](index)
    @elements[index]
  end

  alias slice []

  def []=(index, element)
    while index > @length
      @elements[@length] = nil
      @length += 1
    end
    @elements[index] = element
    @length += 1 if index == @length
  end

  # Constant Time to add element to the end of collection
  # Time Complexity: O(1)
  def push(element)
    @elements[@length] = element
    @length += 1
    return self
  end

  alias << push

  # Constant time to remove last element. Time Complexity: O(1)
  def pop
    latest_element = @elements[@length -1]
    @elements.delete(@length -1)
    @length -= 1

    return latest_element
  end

  # Linear time to add at the beginning of collection.
  # Moves other values. Time Complexity: O(n)
  def unshift(value)
    self.unshift_elements(0, value)
    return self
  end

  # Linear time to remove at the beginning of the collection.
  # Shifts other values. Time Complexity: O(n)
  def shift
    first_element = @elements[0]
    self.shift_elements(0)
    return first_element
  end

  # Calls the given block once for each element in the collection, passing
  # the element as a parameter. Return an enumerator if no block is given.
  def each
    return self.enum_for(__method__) unless block_given?

    counter = 0
    while counter < @length
      yield @elements[counter]
      counter += 1
    end

    return self
  end

  # Linear time to remove at an arbitrary location. Shifts other values.
  # Time Complexity: O(n)
  def delete(element)
    self.each.with_index do |value, index|
      if value == element
        self.shift_elements(index)
        return value
      end
    end

    return nil
  end

  private

  def unshift_elements(index, value)
    counter = @length - 1
    while counter >= index
      @elements[counter + 1] = @elements[counter]
      counter -= 1
    end
    @elements[index] = value
    @length += 1
  end

  def shift_elements(index)
    counter = index
    while counter < (@length - 1)
      @elements[counter] = @elements[counter + 1]
      counter += 1
    end
    @elements.delete(@length - 1)
    @length -= 1
  end
end

Sources of Inspiration

Data Structures From Scratch: Array
Exploring Data Structures From a Ruby Background, Pt. 1: Arrays
Ruby's Set source code