patternrubyMinor

Deque implementation in Ruby

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

implementationdequeruby

Problem

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

Solution

-
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.

-
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.

-
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.

-
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.

Code Snippets

class Deque
  # ...

  private

  Element = Struct.new(:datum, :prev, :next)
end

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

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

deque_instance = []

Context

StackExchange Code Review Q#62176, answer score: 4

Revisions (0)

No revisions yet.