# Deque implementation in Ruby

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

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


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
@tail = nil
end

def push(datum)
if @tail
@tail = @tail.append(datum)
else
end
end

def pop
return nil unless @tail
datum, @tail = @tail.datum, @tail.prev
datum
end

def unshift(datum)
else
end
end

def shift
datum
end

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

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

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
end

def push(datum)
self
end

# Returns nil if the deque is empty
def pop
element.datum
end

# Returns nil if the deque is empty
def last
end

def unshift(datum)
self
end

# Returns nil if the deque is empty
def shift