Creating Linked Lists In Ruby

linked_list.rb

# Creating a linked list in Ruby, based on this tutorial
# http://www.commandercoriander.net/blog/2012/12/23/reversing-a-linked-list-in-ruby/

require 'benchmark'

class Entry
  attr_accessor :next, :data

  def initialize(data)
    @next = nil
    @data = data
  end
end

class List
  attr_accessor :name, :head, :tail

  def initialize
    @head = nil
    @tail = nil
  end

  def unshift(entry)
    if @head.nil?
      @head = entry
      @tail = entry
    else
      entry.next = @head
      @head = entry
    end
  end

  def push(entry)
    if @head.nil?
      @head = entry
      @tail = entry
    else
      @tail.next = entry
      @tail = entry
    end
  end

  def pop
    return nil if @head.nil?
    entry = @head
    @head = @head.next
    entry
  end
end


list_1 = Array.new(1_000_000).map{|x| rand(10_000)}
list_2 = List.new

1_000_000.times do |entry|
  entry = Entry.new rand(10_000)
  list_2.push entry
end


Benchmark.bm do |x|
  x.report { list_1.unshift 10 }
  x.report { list_1.pop }
  x.report { list_1.push 10 }
  x.report { list_2.unshift Entry.new(10) }
  x.report { list_2.pop }
  x.report { list_2.push Entry.new(10) }
end

# $ ruby linked_list.rb
#        user     system      total        real
#    0.000000   0.000000   0.000000 (  0.032085)
#    0.000000   0.000000   0.000000 (  0.000005)
#    0.000000   0.000000   0.000000 (  0.000004)
#    0.000000   0.000000   0.000000 (  0.000010)
#    0.000000   0.000000   0.000000 (  0.000006)
#    0.000000   0.000000   0.000000 (  0.000008)

As expected, it is a large overhead to use #unshift and put something into the front of a dynamic array. Ruby has to move each element down the array, creating an O(n) time complexity. However, Ruby is smart in the way it handles popping, and simply moves the pointer that is pointing to the front of the array, instead of again shifting all the items [1].

Conversely, creating a linked list removes any of the overhead from putting an item to the front of an array, with a time complexity of O(1). However, linked lists are not able to handle indexing in the same optimized fashion as an array [2], and should really only be used when pushing (or 'unshifting') items to the front of a list is required.

[1] http://www.sitepoint.com/rubys-missing-data-structure/
[2] http://bigocheatsheet.com/