Algorithmathon Day 6: Double Linked List Base ~ Code Excursion

18 July 2013

Algorithmathon

Below is the code to be used as the base starting with Day 7 of the Algorithmathon. We have our RSpec tests along with our Double Linked List (DoLL) Element and the DoLL itself. This code will be used as the starting point for most of the Algorithms involving DoLL. The code for which can be found on GitHub.

We start with our tests.

double_linked_list_element_spec.rb

require 'spec_helper'

describe DoubleLinkedListElement do
  describe "Class" do
    it "should have a 'next_node' method" do
      DoubleLinkedListElement.method_defined?(:next_node).should be_true
    end
    it "should have a 'prev_node' method" do
      DoubleLinkedListElement.method_defined?(:prev_node).should be_true
    end    
    it "should have a 'data' method" do
      DoubleLinkedListElement.method_defined?(:data).should be_true
    end

  end
end

double_linked_list_spec.rb

require 'spec_helper'

describe DoubleLinkedList do

  describe "Class" do
    it "should have method 'last'" do
      DoubleLinkedList.method_defined?(:last).should be_true
    end

    it "should have method 'add'" do
      DoubleLinkedList.method_defined?(:add).should be_true
    end

    it "should have method 'length'" do
      DoubleLinkedList.method_defined?(:length).should be_true
    end 

    it "should have method 'element_at'" do
      DoubleLinkedList.method_defined?(:element_at).should be_true
    end   
  end

  describe "Instance" do

    before(:each) do
      @list = DoubleLinkedList.new()
    end

    it "should return nil when 'last()' is called" do
      @list.last().should be_nil
    end

    it "should not return nil when 'last()' is called" do
      add_elements(@list)
      @list.last().should_not be_nil
    end
    
    it "should return 'four' when 'last().data' is called" do
      add_elements(@list)
      @list.last().data.should == "four"
    end 

     it "should return 4 when 'length' is called" do
      add_elements(@list)
      @list.length().should == 4
    end 

     it "should return 'one' when 'element_at(0).data' is called" do
      add_elements(@list)
      @list.element_at(0).data.should == 'one'
      @list.element_at(1).data.should == 'two'
      @list.element_at(2).data.should == 'three'
      @list.element_at(3).data.should == 'four'
    end     

  end

end

Then we write our code to satisfy our tests.

double_linked_list_element.rb

class DoubleLinkedListElement
  attr_accessor :next_node, :prev_node, :data

  def initialize(data=nil,next_node=nil,prev_node=nil)
    self.data=data
    self.next_node=next_node
    self.prev_node=prev_node
  end
end

double_linked_list.rb

require 'double_linked_list_element'

class DoubleLinkedList
  attr_reader :head, :tail, :length

  def initialize()
    @length=0
  end

  def add(element)
    if @head.nil?
      @head = element
      @tail = element
      @length=1
    else
      @tail.next_node=element
      element.prev_node=@tail
      @tail=element
      @length = @length + 1
    end
  end

  def last()
    @tail
  end 

  def length()
    @length
  end

  def element_at(position_count)
    if position_count >= 0
      retrieve_forward_by_recursion(@head,position_count,0)
    end
  end

  private
    def retrieve_forward_by_recursion(element,position_count,current_count)
      unless element.nil?
        if current_count == position_count
          element
        else
          current_count=current_count + 1
          retrieve_forward_by_recursion(element.next_node,position_count,current_count)
        end
      end
    end

end

Food for thought is to consider how the Double Linked List (DoLL) would change the solutions we wrote for the Single Linked List (SLL). For example the ‘element_at’ method is basically the same method as the ‘retrieve’ method we wrote for the SLL. With the DoLL we could compare the position being requested and start from the tail or the head depending on which one is closer.