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.

``````require 'spec_helper'

describe "Class" do
it "should have a 'next_node' method" do
end
it "should have a 'prev_node' method" do
end
it "should have a 'data' method" do
end

end
end
```
```
``````require 'spec_helper'

describe "Class" do
it "should have method 'last'" do
end

it "should have method 'add'" do
end

it "should have method 'length'" do
end

it "should have method 'element_at'" do
end
end

describe "Instance" do

before(:each) do
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
@list.last().should_not be_nil
end

it "should return 'four' when 'last().data' is called" do
@list.last().data.should == "four"
end

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

it "should return 'one' when 'element_at(0).data' is called" do
@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.

``````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
```
```
``````require 'double_linked_list_element'

def initialize()
@length=0
end

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

Less Is More ~ Older posts are available in the archive.