Deque implementation in Ruby

Question

class Element
 attr_accessor :datum, :prev , :next
 def initialize(datum,next_element=nil, prev_element=nil)
 @datum = datum
 @next = next_element
 @prev = prev_element
 end
end
class Deque
 attr_reader :first, :last
 def push(datum)
 if @last.nil?
 @last = Element.new(datum)
 @first = @last
 elsif @last == @first
 @last = Element.new(datum,@first)
 @first.prev = @last 
 else
 prev = @last
 @last = Element.new(datum,prev) 
 prev.prev = @last
 end 
 end
 def pop
 datum = @last.datum
 @last = @last.next if @last
 datum
 end
 def shift
 datum = @first.datum
 @first = @first.prev
 @first.next = nil if @first
 datum
 end
 def unshift(datum)
 if @last.nil?
 @last = Element.new(datum)
 @first = @last
 elsif @last == @first
 @first = Element.new(datum,nil,@last)
 @last.next = @first
 else
 prev = @first
 @first = Element.new(datum,nil, prev) 
 end 
 end 
end

Answer 1

1. I'm very confused by your naming - or perhaps you are. When pushing something onto a non-empty deque, you create a new Element and set its next element to be the preceding one. I.e. when examining the appended element, I'd see that its next is in fact the one before it. And vice-versa for unshift. It seems to work out (or I think it does) because you're at least consistent about the next-means-previous, and previous-means-next.
   Or you've simply got push and unshift (and pop and shift backwards. Which is think is the case.

2. You could make good use of Struct for your Element class. And I'd make it a private inner class, since it's not meant for external use

   class Deque
    # ...
    private
    Element = Struct.new(:datum, :prev, :next)
   end
   

   Saves you having to type the whole class declaration.

3. While pop and shift return the actual data, your first and last accessors return Element instances. I'd suggest that pop/push/shift/unshift/first/last all return data, while you use different methods/variables internally to get the Element-wrapped data. Say head and tail.

4. You don't need to check for nil as often as you do. Forgetting for at moment the prev/next confusion, your push method could be just

   def push(datum)
    if @last.nil?
    @last = @first = Element.new(datum)
    else
    @last = Element.new(datum, @last)
    end 
   end
   

As an alternative to your current approach, you could put some more logic into Element to clean up the code in Deque. I.e. give Element methods like append and prepend which create a new Element instance that's properly linked to the receiver. It avoids you having to set things from the outside.

class Deque
 def initialize
 @head = nil
 @tail = nil
 end
 def push(datum)
 if @tail
 @tail = @tail.append(datum)
 else
 @head = @tail = Element.new(datum)
 end
 end
 def pop
 return nil unless @tail
 datum, @tail = @tail.datum, @tail.prev
 datum
 end
 def unshift(datum)
 if @head
 @head = @head.prepend(datum)
 else
 @head = @tail = Element.new(datum)
 end
 end
 def shift
 return nil unless @head
 datum, @head = @head.datum, @head.next
 datum
 end
 def first
 @head ? @head.datum : nil
 end
 def last
 @tail ? @tail.datum : nil
 end
 private
 Element = Struct.new(:datum, :prev, :next) do
 def prepend(datum)
 raise "Can't prepend here" if self.prev
 self.prev = self.class.new(datum, nil, self)
 end
 def append(datum)
 raise "Can't append here" if self.next
 self.next = self.class.new(datum, self, nil)
 end
 end
end

The exceptions being raised in prepend/append are there to catch cases where you try to append/prepend something "in the middle" if the deque. Doing so would only modify one side of the linkage, causing the list to branch and things to go weird.

Of course, the simplest deque in Ruby is the built-in Array.

deque_instance = []

And done.

• aarti: Regarding(2) Struct vs Named class, what is the real benefit?
• Flambino: @user663848 It's mostly syntactic sugar. You can either declare your own very basic class just to hold 3 read/writable variables, or you can use Struct to make such a class for you. It's still a named class (Struct.new returns a class), it's just a quicker way to create one when all you need it to do is hold a few variables.

Answer 2

I'll second some of @Flambino's remarks: your next/prev naming convention is backwards, the Element class could be simplified down to a Struct, and your return types are inconsistent.

With linked lists, the special cases can be reduced by introducing a dummy element for the head. This is doubly useful for a doubly linked list, which is what you have.

class Deque
 Element = Struct.new(:datum, :next, :prev)
 def initialize
 @head = Element.new(nil, nil, nil)
 @head.prev = @head.next = @head
 end
 def push(datum)
 element = Element.new(datum, @head, @head.prev)
 @head.prev = @head.prev.next = element
 self
 end
 # Returns nil if the deque is empty
 def pop
 element = @head.prev
 element.prev.next = @head
 @head.prev = element.prev
 element.datum
 end
 # Returns nil if the deque is empty
 def last
 @head.prev.datum
 end
 def unshift(datum)
 element = Element.new(datum, @head.next, @head)
 @head.next = @head.next.prev = element
 self
 end
 # Returns nil if the deque is empty
 def shift
 element = @head.next
 element.next.prev = @head
 @head.next = element.next
 element.datum
 end
 # Returns nil if the deque is empty
 def first
 @head.next.datum
 end
end