Algorithmathon Day 6: Double Linked List Base
18 July 2013
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.rbdouble_linked_list_spec.rbrequire '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
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.rbdouble_linked_list.rbclass 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' 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.