Singly Linked List with ruby

linked_list.rb

class Node
  def initialize(value, next_node = nil)
    @value = value
    @next_node = next_node
  end

  attr_reader :value
  attr_accessor :next_node
end

class LinkedList
  def initialize
    @first_node = nil
  end

  attr_accessor :first_node

  def add(value)
    if @first_node
      find_last_node.next_node = Node.new(value)
    else
      @first_node = Node.new(value)
    end
  end

  def add_with_index(index, value)
    prev_node = get(index - 1)
    return if !prev_node

    new_node = Node.new(value)
    new_node.next_node = prev_node.next_node
    prev_node.next_node = new_node
  end

  def delete(index)
    target_node = get(index)
    return if !target_node

    if target_node == @first_node
      @first_node = target_node.next_node
      return
    end

    prev_node = get(index - 1)
    prev_node.next_node = target_node.next_node
  end

  def get(index)
    node = @first_node
    return node if index == 0

    counter = 0
    while counter < index
      if !node.next_node
        return nil
      else
        node = node.next_node
      end
      counter += 1
    end

    return node
  end

  private

  def find_last_node
    node =  @first_node
    return node if !node.next_node

    while node.next_node
      node = node.next_node
    end

    return node
  end
end

# test code
linked_list = LinkedList.new
linked_list.add(10)
linked_list.add(20)
linked_list.add(30)
linked_list.add_with_index(1, 15)
linked_list.add_with_index(3, 25)
linked_list.delete(2)
# p linked_list #=> #<LinkedList:0x00007f9fe6090a78 @first_node=#<Node:0x00007f9fe6090a28 @value=10, @next_node=#<Node:0x00007f9fe60908e8 @value=15, @next_node=#<Node:0x00007f9fe6090898 @value=25, @next_node=#<Node:0x00007f9fe6090960 @value=30, @next_node=nil>>>>>

# Comparison with array
require 'benchmark'

# insert
Benchmark.bm 30 do |r|
  arr = Array.new
  r.report "insert Array(ArrayList)" do
    (1..10000).each do |num|
      arr.insert(0, num)
    end
  end

  linked_list = LinkedList.new
  r.report "insert LinkedList" do
    (1..10000).each do |num|
      linked_list.add_with_index(0, num)
    end
  end
end

# delete
Benchmark.bm 30 do |r|
  arr = (1..10000).to_a
  r.report "delete Array(ArrayList)" do
    (2..1000).each do |num|
      arr.delete_at(num)
    end
  end

  linked_list = LinkedList.new
  (1..10000).each { |num| linked_list.add(num) }
  r.report "delete LinkedList" do
    (2..1000).each do |num|
      linked_list.delete(num)
    end
  end
end

# find
Benchmark.bm 30 do |r|
  arr = (1..10000).to_a
  r.report "find Array(ArrayList)" do
    arr = Array.new
    (1..1000).each do |num|
      arr.index(num)
    end
  end

  linked_list = LinkedList.new
  (1..10000).each { |num| linked_list.add(num) }
  r.report "find LinkedList" do
    (1..1000).each do |num|
      linked_list.get(num)
    end
  end
end

Below is the result of benchmarks. The benchmark of delete LinkedList could be improved if we use Doubly Linked List.

$ ruby linked_list.rb
                                     user     system      total        real
insert Array(ArrayList)          0.007941   0.000032   0.007973 (  0.007977)
insert LinkedList                0.001574   0.000011   0.001585 (  0.001595)
                                     user     system      total        real
delete Array(ArrayList)          0.001783   0.000009   0.001792 (  0.001799)
delete LinkedList                0.056874   0.000923   0.057797 (  0.060714)
                                     user     system      total        real
find Array(ArrayList)            0.000083   0.000005   0.000088 (  0.000216)
find LinkedList                  0.029039   0.000500   0.029539 (  0.031491)