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