Avatar of w1zeman1p

w1zeman1p's solution

to Simple Linked List in the Ruby Track

Published at Jul 13 2018 · 0 comments
Instructions
Test suite
Solution

Note:

This solution was written on an old version of Exercism. The tests below might not correspond to the solution code, and the exercise may have changed since this code was written.

Write a simple linked list implementation that uses Elements and a List.

The linked list is a fundamental data structure in computer science, often used in the implementation of other data structures. They're pervasive in functional programming languages, such as Clojure, Erlang, or Haskell, but far less common in imperative languages such as Ruby or Python.

The simplest kind of linked list is a singly linked list. Each element in the list contains data and a "next" field pointing to the next element in the list of elements.

This variant of linked lists is often used to represent sequences or push-down stacks (also called a LIFO stack; Last In, First Out).

As a first take, lets create a singly linked list to contain the range (1..10), and provide functions to reverse a linked list and convert to and from arrays.

When implementing this in a language with built-in linked lists, implement your own abstract data type.


For installation and learning resources, refer to the exercism help page.

For running the tests provided, you will need the Minitest gem. Open a terminal window and run the following command to install minitest:

gem install minitest

If you would like color output, you can require 'minitest/pride' in the test file, or note the alternative instruction, below, for running the test file.

Run the tests from the exercise directory using the following command:

ruby simple_linked_list_test.rb

To include color from the command line:

ruby -r minitest/pride simple_linked_list_test.rb

Source

Inspired by 'Data Structures and Algorithms with Object-Oriented Design Patterns in Ruby', singly linked-lists. http://www.brpreiss.com/books/opus8/html/page96.html#SECTION004300000000000000000

Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

simple_linked_list_test.rb

require 'minitest/autorun'
require_relative 'simple_linked_list'

class LinkedListTest < Minitest::Test
  def test_element
    element = Element.new(1)
    assert_equal 1, element.datum
  end

  def test_element_can_hold_a_different_value
    skip
    element = Element.new(10)
    assert_equal 10, element.datum
  end

  def test_element_next
    skip
    element = Element.new(1)
    assert_nil element.next
  end

  def test_element_next_can_be_assigned_to
    skip
    first  = Element.new(1)
    second = Element.new(2)
    first.next = second
    assert_equal second, first.next
  end

  def test_list_push
    skip
    list = SimpleLinkedList.new
    element = Element.new(1)
    assert_equal list, list.push(element)
  end

  def test_list_pop
    skip
    list = SimpleLinkedList.new
    element = Element.new(1)
    list.push(element)
    assert_equal element, list.pop
  end

  def test_list_pop_empty
    skip
    list = SimpleLinkedList.new
    assert_nil list.pop
  end

  def test_list_pop_is_last_in_first_out
    skip
    list = SimpleLinkedList.new
    first = Element.new(1)
    second = Element.new(2)
    list.push(first).push(second)
    assert_equal second, list.pop
  end

  def test_list_empty_to_array
    skip
    list = SimpleLinkedList.new
    assert_equal [], list.to_a
  end

  def test_list_single_to_array
    skip
    list = SimpleLinkedList.new
    first = Element.new(1)
    list.push(first)
    assert_equal [1], list.to_a
  end

  def test_list_multiple_to_array
    skip
    list = SimpleLinkedList.new
    first = Element.new(1)
    second = Element.new(2)
    third = Element.new(3)
    list.push(first).push(second).push(third)
    assert_equal [3, 2, 1], list.to_a
  end

  def test_list_create_from_array
    skip
    array = [1, 2, 3]
    list = SimpleLinkedList.new(array)
    assert_equal [3, 2, 1], list.to_a
  end

  def test_list_created_from_array_still_made_up_of_elements
    skip
    array = [1, 2, 3]
    list = SimpleLinkedList.new(array)
    assert_equal Element, list.pop.class
  end

  def test_list_from_array_still_acts_as_lifo
    skip
    array = [1, 2, 3]
    list = SimpleLinkedList.new(array)
    element = list.pop
    assert_equal 3, element.datum
  end

  def test_list_in_place_reverse!
    skip
    first = Element.new(1)
    second = Element.new(2)
    third = Element.new(3)
    list = SimpleLinkedList.new
    list.push(first).push(second).push(third)

    assert_equal [1, 2, 3], list.reverse!.to_a
  end

  def test_list_in_place_reverse_are_the_same_elements
    skip
    first = Element.new(1)
    second = Element.new(2)
    list = SimpleLinkedList.new
    list.push(first).push(second)

    list.reverse!

    assert_equal first, list.pop
    assert_equal second, list.pop
  end

  def test_list_reverse_empty_list
    skip
    list = SimpleLinkedList.new
    assert_equal list, list.reverse!
  end

  def test_works_for_1_through_10
    skip
    list = SimpleLinkedList.new(1..10)
    expected = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
    assert_equal expected, list.to_a
  end

  # Problems in exercism evolve over time, as we find better ways to ask
  # questions.
  # The version number refers to the version of the problem you solved,
  # not your solution.
  #
  # Define a constant named VERSION inside of the top level BookKeeping
  # module.
  #  In your file, it will look like this:
  #
  # module BookKeeping
  #   VERSION = 1 # Where the version number matches the one in the test.
  # end
  #
  # If you are curious, read more about constants on RubyDoc:
  # http://ruby-doc.org/docs/ruby-doc-bundle/UsersGuide/rg/constants.html

  def test_bookkeeping
    skip
    assert_equal 1, BookKeeping::VERSION
  end
end
class Element
  attr_accessor :next
  attr_reader :datum

  def initialize(datum, nxt=nil)
    @datum = datum
    @next = nxt
  end

  def tail?
    @next.nil?
  end
end

class SimpleLinkedList
  attr_reader :size, :head

  def self.from_a(array)
    (array || []).reverse.inject(SimpleLinkedList.new, &:push)
  end

  def initialize
    @size = 0
  end

  def empty?
    size.zero?
  end

  def push(datum)
    @head = Element.new(datum, head)
    @size += 1
    self
  end

  def pop
    @size -= 1
    value = @head.datum
    @head = @head.next
    value
  end

  def peek
    empty? ? nil : @head.datum
  end

  def to_a
    result = []
    current = @head
    until current.nil?
      result << current.datum
      current = current.next
    end
    result
  end

  def reverse
    current = @head
    runner = current.next
    until runner.nil?
      temp = current
      current = runner
      runner = current.next
      current.next = temp
    end
    @head.next = nil
    @head = current
    self
  end
end

Community comments

Find this solution interesting? Ask the author a question to learn more.

What can you learn from this solution?

A huge amount can be learned from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

  • What compromises have been made?
  • Are there new concepts here that you could read more about to improve your understanding?