Linked List in Ruby

.rvmrc

#!/usr/bin/env bash

# This is an RVM Project .rvmrc file, used to automatically load the ruby
# development environment upon cd'ing into the directory

# First we specify our desired <ruby>[@<gemset>], the @gemset name is optional.
environment_id="ruby-1.9.3-p0@TheOregonTwail"

#
# Uncomment following line if you want options to be set only for given project.
#
# PROJECT_JRUBY_OPTS=( --1.9 )

#
# First we attempt to load the desired environment directly from the environment
# file. This is very fast and efficient compared to running through the entire
# CLI and selector. If you want feedback on which environment was used then
# insert the word 'use' after --create as this triggers verbose mode.
#
if [[ -d "${rvm_path:-$HOME/.rvm}/environments" \
  && -s "${rvm_path:-$HOME/.rvm}/environments/$environment_id" ]]
then
  \. "${rvm_path:-$HOME/.rvm}/environments/$environment_id"

  if [[ -s "${rvm_path:-$HOME/.rvm}/hooks/after_use" ]]
  then
    . "${rvm_path:-$HOME/.rvm}/hooks/after_use"
  fi
else
  # If the environment file has not yet been created, use the RVM CLI to select.
  if ! rvm --create  "$environment_id"
  then
    echo "Failed to create RVM environment '${environment_id}'."
    exit 1
  fi
fi

#
# If you use an RVM gemset file to install a list of gems (*.gems), you can have
# it be automatically loaded. Uncomment the following and adjust the filename if
# necessary.
#
# filename=".gems"
# if [[ -s "$filename" ]]
# then
#   rvm gemset import "$filename" | grep -v already | grep -v listed | grep -v complete | sed '/^$/d'
# fi

# If you use bundler, this might be useful to you:
# if command -v bundle && [[ -s Gemfile ]]
# then
#   bundle install
# fi

linked_list.rb

require 'test/unit'
class LinkedListTest < Test::Unit::TestCase
  
  def test_an_empty_list_has_nil_head
    list = LinkedList.new()
    assert_nil list.head
  end
  
  def test_you_can_add_items_to_a_list
    list = LinkedList.new()
    list.add("A")
    list.add("B")
    assert_equal("A", list.head)
  end
  
  def test_you_can_pop_all_items_from_a_list
    list = LinkedList.new()
    list.push("A")
    list.push("B")
    
    assert_equal("B", list.pop)
    assert_equal("A", list.pop)
    assert_equal(nil, list.pop)
    assert_equal(nil, list.pop)
  end
end

class LinkedList
  def initialize
    @head = Node::EMPTY
  end
  
  def add(item)
    if @head == Node::EMPTY
      @head = Node.new(item)
    else
      tail.next_node = Node.new(item)
    end
  end
  alias :push :add
  
  def pop
    return nil if @head == Node::EMPTY
    new_tail = next_to_last(@head, @head)
    popped = nil
    if new_tail.next_node.nil?
      popped = new_tail.data
      @head = Node::EMPTY
    else
      popped = new_tail.next_node.data
      new_tail.next_node = nil
    end
    popped
  end
  
  def head
    @head.data
  end
  
  def tail
    traverse(@head)
  end
  
  private
  def traverse(node)
    return node if node.next_node.nil?
    traverse(node.next_node)
  end
  
  def next_to_last(node, previous_node)
    return previous_node if node.next_node.nil?
    next_to_last(node.next_node, node)
  end
  
  class Node
    EMPTY = Node.new()
    attr_accessor :data, :next_node
    def initialize(data, next_node=nil)
      @data = data
      @next_node = next_node
    end
  end
end

linked_list_two.rb

require 'test/unit'
require 'ostruct'
class LinkedListTwoTest < Test::Unit::TestCase

  def test_an_empty_linked_list_head_is_nil
    list = LinkedListTwo.new
    assert_nil(list.head)
  end
  
  def test_add_to_the_beginning_of_an_empty_list
    list = LinkedListTwo.new
    list.addToStart("Fun")
    assert_equal("Fun", list.head)
  end
  
  def test_remove_first_item_from_list
    list = LinkedListTwo.new
    list.addToStart("Fun")
    list.deleteFromStart
    assert_nil(list.head)
  end
  
  def test_add_multiple_items_to_the_list
    list = LinkedListTwo.new
    list.addToStart("Fun")
    list.addToStart("More Fun")
    assert_equal("More Fun", list.head)
    list.deleteFromStart
    assert_equal("Fun", list.head)
    list.deleteFromStart
    assert_nil(list.head)
  end
  
  def test_iteration_on_empty_list
    list = LinkedListTwo.new
    elements = []
    list.each {|i| elements << i}
    assert_equal([], elements)
  end
  
  def test_iteration_on_list_of_two
    list = LinkedListTwo.new
    list.addToStart("Fun")
    list.addToStart("More Fun")
    elements = []
    list.each {|i| elements << i}
    assert_equal("More Fun", elements.first)
    assert_equal("Fun", elements.last)
  end
  
  def test_size
    list = LinkedListTwo.new
    assert_equal(0, list.size)
    list.addToStart("Fun")
    list.addToStart("More Fun")
    assert_equal(2, list.size)
  end
  
  def test_two_empty_lists_equality
    list = LinkedListTwo.new
    list2 = LinkedListTwo.new
    assert_equal(list, list2)
    assert_equal(list2, list)
  end
  
  def test_two_non_empty_lists_equality
    list = LinkedListTwo.new
    list.addToStart("Fun")
    list.addToStart("More Fun")
    list2 = LinkedListTwo.new
    list2.addToStart("Fun")
    list2.addToStart("More Fun")
    list3 = LinkedListTwo.new
    assert_equal(list, list2)
    assert_equal(list2, list)
    assert(list != list3, "not equal")
    assert(list3 != list, "not equal")
  end
  
  def test_push_pop
    stack = LinkedListTwo.new
    stack.push("Fun")
    stack.push("More Fun")
    assert_equal("More Fun", stack.pop)
    assert_equal("Fun", stack.pop)
  end
end

class LinkedListTwo
  def initialize
    @sentinal = create_node(nil, nil)
    @head = @sentinal
  end
  
  def head
    @head.data
  end
  
  def addToStart(item)
    @head = create_node(item, @head)
  end
  alias :push :addToStart
  
  def deleteFromStart
    data = @head.data
    @head = @head.next_node unless @head.sentinal?
    data
  end
  alias :pop :deleteFromStart
  
  def each(&block)
    traverse(@head, block)
  end
  
  def size
    counter = 0
    each{counter += 1}
    counter
  end
  
  def ==(object)
    return false unless object.instance_of?(self.class)
    return false unless object.size == size
    node_to_compare = @head
    all_members_equal = true
    object.each do |data| 
      all_members_equal = false if node_to_compare.data != data
      node_to_compare = @head.next_node
    end
    all_members_equal
  end
  alias :eql? :==
  
  private
  
  def traverse(node, block)
    return if node.sentinal?
    block.call(node.data)
    traverse(node.next_node, block)
  end
  
  def create_node(data, next_node)
    OpenStruct.new({data: data, next_node: next_node, sentinal?: (data.nil? && next_node.nil?)})
  end
end