Algorithmathon Day 4: Single Linked List Remove, Insert After, Insert Before

Created: 16 July 2013  Modified:

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, the rules for the Algorithmathon can be found here.

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

single_linked_list_spec.rb (excerpt)

= code omitted here
    it "should have method 'remove'" do
      SingleLinkedList.method_defined?(:remove).should be_true
    end
= code omitted here

     it "should return removed object  when 'remove' is called" do
      first = SingleLinkedListElement.new("first")
      @list.add(first)
      @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.

single_linked_list.rb

require 'single_linked_list_element'

class SingleLinkedList
  attr_reader :head

  def add(element)
    if @head.nil?
      @head = element
    else
      last_element=last()
      last_element.next_node=element
    end
  end

  def remove(element)
    remove_by_recursion(@head,element,nil)
  end

  def last()
    last_element=SingleLinkedListElement.new()
    last_by_recursion(@head,last_element)
    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?
          @head=element.next_node
        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.

single_linked_list_spec.rb (excerpt)

= code omitted here
     it "should return removed object  when 'remove' is called and object is the head among many" do
      first = SingleLinkedListElement.new("first")
      @list.add(first)
      add_elements(@list)
      @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?

single_linked_list_spec.rb (excerpt)

= code omitted here
    it "should return removed object  when 'remove' is called and object is the last among many" do
      last = SingleLinkedListElement.new("last")
      add_elements(@list)
      @list.add(last)
      @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.

single_linked_list.rb

= 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?
          @head=element.next_node
        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.

single_linked_list_spec.rb (excerpt)

= code omitted here
    it "should return removed object  when 'remove' is called and object is the in the middle of many" do
      last = SingleLinkedListElement.new("last")
      add_elements(@list)
      @list.add(last)
      add_elements(@list)
      @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.

single_linked_list_spec.rb (excerpt)

= code omitted here
     it "should return the parent object  when 'insert_after' targets the middle of a list" do
      middle = SingleLinkedListElement.new("middle")
      after = SingleLinkedListElement.new("after")
      add_elements(@list)
      @list.add(middle)
      add_elements(@list)
      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
      head = SingleLinkedListElement.new("head")
      after = SingleLinkedListElement.new("after")
      @list.add(head)
      add_elements(@list)
      head_next=head.next_node
      @list.length().should == 5
      @list.insert_after(head,after).eql?(head).should be_true
      head.next_node.eql?(after).should be_true
      after.next_node.eql?(head_next).should be_true
      @list.length().should == 6
    end

    it "should return the parent object  when 'insert_after' targets the tail of a list" do
      last = SingleLinkedListElement.new("last")
      after = SingleLinkedListElement.new("after")
      add_elements(@list)
      @list.add(last)
      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.

single_linked_list.rb (excerpt)

= code omitted here
  def insert_after(target_element, new_element)
    if new_element.nil?
      new_element
    else
      insert_after_by_recursion(@head, target_element, new_element)
    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.

single_linked_list_spec.rb (excerpt)

= code omitted here
     it "should return the parent object  when 'insert_after' targets the middle of a list" do
      middle = SingleLinkedListElement.new("middle")
      after = SingleLinkedListElement.new("after")
      add_elements(@list)
      @list.add(middle)
      add_elements(@list)
      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
      head = SingleLinkedListElement.new("head")
      after = SingleLinkedListElement.new("after")
      @list.add(head)
      add_elements(@list)
      head_next=head.next_node
      @list.length().should == 5
      @list.insert_after(head,after).eql?(head).should be_true
      head.next_node.eql?(after).should be_true
      after.next_node.eql?(head_next).should be_true
      @list.length().should == 6
    end

    it "should return the parent object  when 'insert_after' targets the tail of a list" do
      last = SingleLinkedListElement.new("last")
      after = SingleLinkedListElement.new("after")
      add_elements(@list)
      @list.add(last)
      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.

single_linked_list.rb (excerpt)

= code omitted here
  def insert_before(target_element, new_element)
    if new_element.nil?
      new_element
    else
      insert_before_by_recursion(@head, target_element, new_element, nil)
    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?
          @head = new_element
        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.

tags: Algorithm - Algorithmathon - RSpec - Ruby - Single Linked List
   Less Is More