From: Robert Klemme <bob.news@...>
Date: 2005-04-05T04:14:53+09:00
Subject: Re: doubly linked list in Ruby?


"ed_davis2" <ed_davis2@yahoo.com> schrieb im Newsbeitrag 
news:1112639817.909110.94480@z14g2000cwz.googlegroups.com...
> I've gone through a Ruby tutorial, and have been writing some
> simple programs.
>
> But I have a question:  how would I implement a simple doubly
> linked list of strings in Ruby?

You would do it like in any other language.  You need a class for the list 
and a class for list elements.

>  I have some data that I need to
> access as if it were an array, but I also need to insert/delete
> items frequently.  If I was using C, I'd just create a doubly
> linked list.  But I don't have a good idea of how to create one
> in Ruby.

Use an array, that's likely the most efficient solution and needs the least 
programming on your side:

>> list = %w{foo bar test dada}
=> ["foo", "bar", "test", "dada"]
>> list.insert(2,"HELLO")
=> ["foo", "bar", "HELLO", "test", "dada"]
>> list.delete_at 3
=> "test"
>> list
=> ["foo", "bar", "HELLO", "dada"]

If you really need a list, you can look in the RAA
http://raa.ruby-lang.org

Or you probably do something like this:

class List
  include Enumerable

  ListElem = Struct.new(:obj, :prev, :next)

  def initialize(*enum)
    @head = @tail = ListElem.new
    @head.next = @head
    @head.prev = @head

    (enum.size == 1 && Enumerable === enum[0] ?
     enum[0] :
     enum).each {|e| append e}
  end

  def append(e)
    tmp = ListElem.new e, @tail.prev, @tail
    tmp.prev.next = tmp
    tmp.next.prev = tmp
    self
  end

  alias :<< :append

  # prepend, remove etc.

  def each
    i = @head.next

    while @tail != i
      yield i.obj
      i = i.next
    end
  end

end

Kind regards

    robert