4
\$\begingroup\$
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
\$\endgroup\$
0
4
\$\begingroup\$
  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.

\$\endgroup\$
2
  • \$\begingroup\$ Regarding(2) Struct vs Named class, what is the real benefit? \$\endgroup\$
    – aarti
    Sep 8 '14 at 1:22
  • \$\begingroup\$ @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. \$\endgroup\$
    – Flambino
    Sep 8 '14 at 8:56
3
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.