David Vallner
10/22/2006 11:11:00 PM
Seth Eliot wrote:
> Hi all,
>
> I am new to Ruby but find it interesting. To teach myself the language
> I wrote a simple linked list implementation. It works just fine, but I
> suspect that my "Java is showing" and that the same logic can be written
> in a much more Ruby-ish fashion.
>
> So I'd appreciate it if you can show me the Ruby way of implementing the
> following functionality.
>
> (The one thing I know is that I am not really taking advantage of OOP by
> making my methods in LinkedListSe.rb just static utility methods… that's
> fine for now)
> (also "next_1" is just my way of not colliding with the reserved keyword
> "next")
>
> File: ElemLL.rb
>
> class ElemLL
>
> attr_accessor :data, :next_1
>
The following two lines don't in fact do anything and can be safely deleted.
> @data
> @next_1
> End
>
The following should be methods of ElemLL. (There's not *much* Java
showing, is there?)
> File: LinkedListSe.rb
>
> require 'ElemLL'
>
> # Adds element to end of linked list
> def addData(data, head=nil)
> insertData(data, head)
> end
>
> # Inserts Element at requested index in linked list.
> # Shifts the element currently at that position (if any) and any
> subsequent
> # elements to the right (adds one to their indices)
> def insertData(data, head, index=nil)
>
> # special case if list currently empty (not initialized)
> return newList(data) unless head
>
If you're doing type-checking, raise an exception. This is a potential
Mysterious Bug. ("Nothing seem to be broke, it just doesn't work!")
> # Weakly typed languages have their downsides? :-)
> return unless head.class == ElemLL
>
> # Initial values for first element
> i = 1
> prev = nil
> curr = head
> next_1 = curr.next_1
>
> # Iterate through elements until we reach insertion point (or end of
> list)
> while (curr && (!index || i<index))
> prev=curr
> curr = next_1;
> next_1 = curr.next_1 if curr;
> i=i.next
> end
>
> # when new element is inserted, the current curr will actually be
> next
> next_1 = curr
>
> # Create the new element at curr
> curr = ElemLL.new
> curr.data = data
> curr.next_1=next_1
>
> # Set the pointer *to* the new element
> if (prev)
> prev.next_1 = curr
> else
> head=curr
> end
>
> return head
> end
>
The following should be an implementation of #each:
> def traverse(head)
Axe following line.
> puts "\nLinked List contents:"
>
> curr = head
> while(curr)
Replace with "yield curr.data". For greater pleasure, have ElemLL
"include Enumerable".
> puts " #{curr.data}"
> curr = curr.next_1
> end
> end
>
The Ruby equivalent of a constructor is the "special" (i.e. not really)
method initialize.
> def newList(data)
> head = ElemLL.new
> head.data = data
> return head
> end
>
Also, I personally prefer(red) opaque linked lists (in the school
assignments where I actually implemented those.) - ones where you don't
rely on having to supply the head node of a list to functions
manipulating it, but a structure encapsulating the list. Same here, I'd
avoid leaking the internal structure of the list.
David Vallner