16 July 2013

Algorithmathon

Once again we will be working with a Single Linked List (SLL) starting with the SLL Base found here. Our goal for today will be to add remove, insert_after and insert_before methods the SLL base class. Source code found here on GitHub. If you havenâ€™t already read them, rules for the Algorithmathon can be found here.

As a first step we should create our first RSpec tests for remove.

``````#code omitted here
it "should have method 'remove'" do
end
#code omitted here

it "should return removed object  when 'remove' is called" do
@list.remove(first).eql?(first).should be_true
end

#code omitted here
```
```

Now that we have our failing tests lets update the SLL so that they will pass.

``````require 'single_linked_list_element'

else
last_element=last()
last_element.next_node=element
end
end

def remove(element)
end

def last()
last_element.next_node
end

private
def last_by_recursion(element,last_element)
unless element.nil?
last_element.next_node=element
unless element.next_node.nil?
last_by_recursion(element.next_node,last_element)
end
end
end

def remove_by_recursion(element,match_element,previous_element)
if element.nil?
element
else
if element == match_element
if previous_element.nil?
else
previous_element.next_node=element.next_node
end
element
end
end
end
end
```
```

Having added the remove and the remove_by_recursion methods our tests are now passing. Now lets add multiple objects in a new test to make sure it still works under those conditions. Our new test add elements after the first/head element.

``````#code omitted here
it "should return removed object  when 'remove' is called and object is the head among many" do
@list.length().should == 5
@list.remove(first).eql?(first).should be_true
@list.length().should == 4
end
#code omitted here
```
```

Whew! That one passed. What about if we try to remove the tail of the list?

``````#code omitted here
it "should return removed object  when 'remove' is called and object is the last among many" do
@list.length().should == 5
@list.remove(last).eql?(last).should be_true
@list.length().should == 4
end
#code omitted here
```
```

Ooops! It failed this test. We need to go back and look at our method. Looks like we had some faulty logic in remove_by_recursion so lets update it to the below.

``````#code omitted here
def remove_by_recursion(element,match_element,previous_element)
if element.nil?
element
else
if element.eql?(match_element)
if previous_element.nil?
else
previous_element.next_node=element.next_node
end
element
else
remove_by_recursion(element.next_node,match_element,element)
end
end
end

#code omitted here
```
```

Rerunning our RSpec test we see that they are all now passing. What if our element is placed in the middle of several other elements? We should add another test to see if our remove method still works under these conditions.

``````#code omitted here
it "should return removed object  when 'remove' is called and object is the in the middle of many" do
@list.length().should == 9

@list.remove(last).eql?(last).should be_true
@list.length().should == 8
end
#code omitted here
```
```

Yay! This test passed so we are looking pretty good. Lets move one to insert_after. For the sake of brevity I will add all the tests at once.

``````#code omitted here
it "should return the parent object  when 'insert_after' targets the middle of a list" do
middle_next=middle.next_node
@list.length().should == 9
@list.insert_after(middle,after).eql?(middle).should be_true
middle.next_node.eql?(after).should be_true
after.next_node.eql?(middle_next).should be_true
@list.length().should == 10
end

it "should return the parent object  when 'insert_after' targets the head of a list" do
@list.length().should == 5
@list.length().should == 6
end

it "should return the parent object  when 'insert_after' targets the tail of a list" do
last_next=last.next_node
@list.length().should == 5
@list.insert_after(last,after).eql?(last).should be_true
last.next_node.eql?(after).should be_true
after.next_node.eql?(last_next).should be_true
@list.length().should == 6
end
#code omitted
```
```

With three failing tests we code our method so that it will pass.

``````#code omitted here
def insert_after(target_element, new_element)
if new_element.nil?
new_element
else
end
end
#code omitted here
def insert_after_by_recursion(current_element,target_element,new_element)
if current_element.nil?
current_element
else
if current_element.eql?(target_element)
new_element.next_node=current_element.next_node
current_element.next_node=new_element
current_element
else
insert_after_by_recursion(current_element.next_node,target_element,new_element)
end
end
end

#code omitted here
```
```

Repeat and rinse for insert_before.

``````#code omitted here
it "should return the parent object  when 'insert_after' targets the middle of a list" do
middle_next=middle.next_node
@list.length().should == 9
@list.insert_after(middle,after).eql?(middle).should be_true
middle.next_node.eql?(after).should be_true
after.next_node.eql?(middle_next).should be_true
@list.length().should == 10
end

it "should return the parent object  when 'insert_after' targets the head of a list" do
@list.length().should == 5
@list.length().should == 6
end

it "should return the parent object  when 'insert_after' targets the tail of a list" do
last_next=last.next_node
@list.length().should == 5
@list.insert_after(last,after).eql?(last).should be_true
last.next_node.eql?(after).should be_true
after.next_node.eql?(last_next).should be_true
@list.length().should == 6
end
#code omitted
```
```

With three failing tests we code our method so that it will pass.

``````#code omitted here
def insert_before(target_element, new_element)
if new_element.nil?
new_element
else
end
end
#code omitted here
def insert_before_by_recursion(current_element,target_element,new_element,previous_element)
if current_element.nil?
current_element
else
if current_element.eql?(target_element)
new_element.next_node=current_element
if previous_element.nil?
else
previous_element.next_node=new_element
end
new_element
else
insert_before_by_recursion(current_element.next_node,target_element,new_element,current_element)
end
end
end

#code omitted here
```
```

This seems more than enough for today so we will pick back up tomorrow with a new challenge.

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