I'm preparing for a technical interview and will be asked to write the algorithm for a linked list in ruby. I understand linked lists completely, but have struggled writing the code. Can someone show me how this is done? I started it below..
class Node
def initialize(item)
@item = item
@next = nil
end
end
You almost did it, really. I can give you very old-school, Lisp-like implementation, if you are brave enough to show it to your interviewer. In this approach, list is a pair (two elements touple), which first element contains the element, and second contains another pair, etc, etc. The last pair have nil as a second element. And here is the whole implementation of the list in Ruby:
class Pair
attr_reader :car, :cdr
def initialize(car, cdr=nil)
@car = car
@cdr = cdr
end
end
To construct the list, just use a lot of parenthesis, like in old, good Lisp:
list = Pair.new(1, Pair.new(2, Pair.new(3)))
Now, the world is yours. You can do whatever you want with the list, using simple recursion. Here is an example of recursive inspect:
class Pair
def inspect
if cdr.nil?
car.inspect
else
"#{car.inspect}, #{cdr.inspect}"
end
end
end
pry(main)> list = Pair.new(1, Pair.new(2, Pair.new(3)))
=> 1, 2, 3
As you mentioned in a comment, you want to search the list. Here is the code for this:
class Pair
def find(index)
find_ index, 0
end
def find_(index, i)
if index == i
car
else
cdr.find_ index, i+1
end
end
end
pry(main)> list.find 2
=> 3
This is the standard Church Encoding of Lists (and Booleans):
True = ->(iff, _) { iff }
False = ->(_, els) { els }
Pair = ->(first, rest) { -> x { x.(first, rest) }}
First = -> list { list.(True ) }
Rest = -> list { list.(False) }
List = Pair.(1, Pair.(2, nil))
First.(Rest.(List))
# => 2
It's not what you would actually write in Ruby, of course, but it is very simple and demonstrates an understanding of one of the most important principles of programming: code is data and data is code.
Here's a more realistic object-oriented encoding of lists:
class List
include Enumerable
def self.[](*els) els.reverse_each.inject(Empty, &:cons) end
def cons(el) Pair[el, self] end
def prepend(prefix)
case
when empty? then prefix
when prefix.empty? then self
else prepend(prefix.rest).cons(prefix.first)
end
end
def to_s; "List[#{map(&:to_s).join(', ')}]" end
def inspect; "List[#{map(&:inspect).join(', ')}]" end
def each; return enum_for(__method__) unless block_given? end
class << Empty = new
def empty?; true end
alias_method :inspect, def to_s; 'Empty' end
freeze
end
Empty.freeze
class Pair < self
def initialize(first, rest=Empty)
self.first, self.rest = first, rest
freeze
end
def empty?; false end
def each(&blk)
return super unless block_given?
yield first
rest.each(&blk)
end
private
attr_writer :first, :rest
protected
attr_reader :first, :rest
class << self; alias_method :[], :new end
freeze
end
freeze
end
Note that there are absolutely no conditionals and no loops in the code. That is always a good sign for object-oriented code: polymorphic method calls are more powerful than conditionals anyway, oftentimes, there simply is no need for conditionals.
Some examples:
list1 = List::Pair[1, List::Pair[2, List::Pair[3, List::Empty]]]
# => List[1, 2, 3]
list2 = List::Empty.cons(6).cons(5).cons(4)
# => List[4, 5, 6]
list3 = List[7, 8, 9]
# => List[7, 8, 9]
list4 = list3.prepend(list2).prepend(list1)
# => List[1, 2, 3, 4, 5, 6, 7, 8, 9]
list4.partition(&:odd?)
# => [[1, 3, 5, 7, 9], [2, 4, 6, 8]]
Unfortunately, this object-oriented encoding will blow the stack for larger lists (on my system List[*(1..9338)].each {} still works, but 9339 doesn't), even though each is tail-calling itself and thus should run in O(1) stack space. As Guy L. Steele pointed out multiple times, OO languages must support proper tail calls, otherwise you are required to break OO in order to avoid blowing the stack. (prepend is not coded for tail-calls, but it can be rewritten that way.)
