Algorithmathon Day 3: Single Linked List Stack

Created: 15 July 2013  Modified:

Today we will be looking into the Stack data structure and writing the push and pop methods to add and remove data from the stack. While we will need to change it quite a bit we will start with the Single Linked List (SLL) Base found here. If you haven’t already read them, the rules for the Algorithmathon can be found here. The code can be found here on GitHub. First we write our failing tests.

single_linked_list_spec.rb

require 'spec_helper'
require 'single_linked_list_spec_helper'

describe SingleLinkedList do

  describe "Class" do
    it "should have method 'push'" do
      SingleLinkedList.method_defined?(:push).should be_true
    end

  end

  describe "Instance" do

    before(:each) do
      @list = SingleLinkedList.new()
    end

    it "should return object when 'push' is called and successful" do
      first = SingleLinkedListElement.new("first")
      @list.push(first).eql?(first).should be_true
    end
  end

end

When we run RSpec we get failing (Red) results. To pass these failing tests we can add the method push to our SLL like so.

single_linked_list.rb

require 'single_linked_list_element'

class SingleLinkedList
  attr_reader :head

  def push(element)
    unless element.nil?
      @head=element
    end
  end
end

Now when we run our test the results will be passing (Green). Writing your test before you write your code is Test Driven Development. Your goal is to write your test and then to write the minimal amount of code to satisfy the test. Now that the tests for our push method are passing we should write tests for our pop method.

single_linked_list_spec.rb

require 'spec_helper'
require 'single_linked_list_spec_helper'

describe SingleLinkedList do

  describe "Class" do
    it "should have method 'push'" do
      SingleLinkedList.method_defined?(:push).should be_true
    end

    it "should have method 'pop'" do
      SingleLinkedList.method_defined?(:pop).should be_true
    end


  end

  describe "Instance" do

    before(:each) do
      @list = SingleLinkedList.new()
    end

    it "should return first object when 'push' is called and successful" do
      first = SingleLinkedListElement.new("first")
      @list.push(first).eql?(first).should be_true
    end

    it "should return first object when 'pop' is called" do
      first = SingleLinkedListElement.new("first")
      @list.push(first)
      @list.pop().eql?(first).should be_true
    end    
  end

end

Our test for pop will of course fail and thus we should update our code so that they pass.

single_linked_list.rb

require 'single_linked_list_element'

class SingleLinkedList
  attr_reader :head

  def push(element)
    unless element.nil?
      @head=element
    end
  end

  def pop()
    element=@head
    @head=@head.next_node
    element
  end
  
end

We now have passing tests for both push and pop. Still we should add another test using multiple objects since a stack must handle multiple objects.

single_linked_list_spec.rb (exerpt)

    ...
    it "should return all objects popped in the reverse order they where pushed" do
      first = SingleLinkedListElement.new("first")
      second = SingleLinkedListElement.new("second")
      third = SingleLinkedListElement.new("third")
      fourth = SingleLinkedListElement.new("fourth")
      fifth = SingleLinkedListElement.new("fifth")
      @list.push(first).eql?(first).should be_true
      @list.push(second).eql?(second).should be_true
      @list.push(third).eql?(third).should be_true
      @list.push(fourth).eql?(fourth).should be_true
      @list.push(fifth).eql?(fifth).should be_true
      @list.pop().eql?(fifth).should be_true
      @list.pop().eql?(fourth).should be_true
      @list.pop().eql?(third).should be_true
      @list.pop().eql?(second).should be_true
      @list.pop().eql?(first).should be_true
    end    
    ...

Ooops our new test is failing! We need to go back and fix our push method to handle linking these objects. Which is simple enough as shown below.

single_linked_list.rb

require 'single_linked_list_element'

class SingleLinkedList
  attr_reader :head

  def push(element)
    unless element.nil?
      if @head.nil?
        @head=element
      else
        element.next_node=@head
        @head=element
      end
    end
  end

  def pop()
    element=@head
    @head=@head.next_node
    element
  end
  
end

All our tests are now passing and we are done with our stack for today.

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