Algorithmathon Day 5: Single Linked List Nth to the Last Element

Created: 17 July 2013  Modified:

Our challenge today will be to retrieve the nth element from the tail of a Single Linked List (SLL). We will start with the SLL Base code found here. If you want to jump ahead and see all of the code at once the Source is found here on GitHub. Constraints and rules are also available.

We will be adding the ‘retrieve’ method which will take an integer as a parameter. If the integer is positive it will return an element counted from the head of the list. If the integer is negative it will retrieve the element counted from the tail of the list. Our first test will be the following.

single_linked_list_spec.rb (excerpt)

# code omitted here
    it "should have method 'retrieve'" do
      SingleLinkedList.method_defined?(:retrieve).should be_true
    end  
# code omitted here
    it "should return the 5th object from the tail when 'retrieve(-5)' is called" do
      target = SingleLinkedListElement.new("target")
      add_elements(@list)
      @list.add(target)
      add_elements(@list)
      @list.retrieve(-5).eql?(target).should be_true
    end
# code omitted here

With tests in the Red we need to modify the SLL so that they turn Green. While working on solving this problem I realized that I could solve the counting backwards problem by counting forward. This resulted in the code below.

single_linked_list.rb

# code omitted here
  def retrieve(position_count)
    if position_count == 0
      nil
    end
    if position_count > 0
      retrieve_forward_by_recursion(@head,position_count,0)
    else
      count = length()
      count = count + position_count + 1
      retrieve_forward_by_recursion(@head,count,0)
    end
  end
# code omitted here
    def retrieve_forward_by_recursion(element,position_count,current_count)
      unless element.nil?
        current_count=current_count + 1
        if current_count == position_count
          element
        else
          retrieve_forward_by_recursion(element.next_node,position_count,current_count)
        end
      end
    end
# code omitted here

This solution seems almost to easy. Lets add some additional tests to verify.

single_linked_list_spec.rb (excerpt)

# code omitted here
    it "should return the 5th object from the head when 'retrieve(5)' is called" do
      target = SingleLinkedListElement.new("target")
      add_elements(@list)
      @list.add(target)
      add_elements(@list)
      @list.retrieve(5).eql?(target).should be_true
    end    

    it "should return the head when 'retrieve(1)' is called" do
      target = SingleLinkedListElement.new("target")
      @list.add(target)
      add_elements(@list)
      @list.retrieve(1).eql?(target).should be_true
    end

    it "should return the tail when 'retrieve(-1)' is called" do
      target = SingleLinkedListElement.new("target")
      add_elements(@list)
      add_elements(@list)
      @list.add(target)
      @list.retrieve(-1).eql?(target).should be_true
    end

    it "should return the head when 'retrieve(-1)' is called" do
      target = SingleLinkedListElement.new("target")
      @list.add(target)
      @list.retrieve(-1).eql?(target).should be_true
    end
# code omitted here

All of the tests are passing! So we are done … yes? Maybe not. Our current solution requires almost two passes through the SLL. We could do it with only one pass if we track the nth position back from the current position. To keep the code simple I will allow myself to use an array in this solution.

single_linked_list.rb (excerpt)

# code omitted here
  def retrieve(position_count)
    if position_count == 0
      nil
    end
    if position_count > 0
      retrieve_forward_by_recursion(@head,position_count,0)
    else
#       count = length()
#       count = count + position_count + 1
#       retrieve_forward_by_recursion(@head,count,0)
      position_count = position_count * -1
      retrieve_nth_from_forward_by_recursion(@head,Array.new(),position_count,0)
    end
  end
# code omitted here
    def retrieve_nth_from_forward_by_recursion(element,nth_elements,position_count,current_count)
      unless element.nil?
        current_count = current_count + 1
        if current_count >= position_count
          nth_elements.push(element)
          if nth_elements.length > position_count
            nth_elements.delete_at(0)
          end
        end
        retrieve_nth_from_forward_by_recursion(element.next_node,nth_elements,position_count,current_count)        
      else
        if nth_elements.length > 0
          nth_elements[0]
        end
      end
    end    
# code omitted here

I think we are done for the day. Tomorrow we will start looking into list flattening.

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