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
\$\begingroup\$
\$\endgroup\$
0
Add a comment
|
2 Answers
\$\begingroup\$
\$\endgroup\$
2
I'm very confused by your naming - or perhaps you are. When pushing something onto a non-empty deque, you create a new
Elementand set its next element to be the preceding one. I.e. when examining the appended element, I'd see that itsnextis in fact the one before it. And vice-versa forunshift. 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 gotpushandunshift(andpopandshiftbackwards. Which is think is the case.You could make good use of
Structfor yourElementclass. And I'd make it a private inner class, since it's not meant for external useclass Deque # ... private Element = Struct.new(:datum, :prev, :next) endSaves you having to type the whole class declaration.
While
popandshiftreturn the actual data, yourfirstandlastaccessors returnElementinstances. I'd suggest thatpop/push/shift/unshift/first/lastall return data, while you use different methods/variables internally to get theElement-wrapped data. Sayheadandtail.You don't need to check for
nilas often as you do. Forgetting for at moment theprev/nextconfusion, yourpushmethod could be justdef 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.
-
\$\begingroup\$ Regarding(2) Struct vs Named class, what is the real benefit? \$\endgroup\$aarti– aarti2014-09-08 01:22:30 +00:00Commented Sep 8, 2014 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.newreturns 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– Flambino2014-09-08 08:56:41 +00:00Commented Sep 8, 2014 at 8:56
\$\begingroup\$
\$\endgroup\$
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