doubly linked list in Ruby?

[ed_davis2]

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

 

[Tim Hunter]

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

Ruby arrays are incredibly more flexible than C arrays. You can insert
an element into an array _between_ two other elements.

a = [1,2,3]
a[1,0] = 4 => [1,4,2,3]

You can delete an element from an array any number of ways. The
delete_at method works if you know the index of the element you want to
delete.

 

[Adriano Ferreira]

You don't need such a thing as doubly linked lists in Ruby. You have
Array's which are as dynamic as you would like.

Try the following at irb:

a = [ 2, 3, 4 ]

a.unshift(1) # insert at front [1, 2, 3, 4]
a.shift # remove the first element

a.push(5) # insert at tail [ 2, 3, 4, 5 ]
a.pop # remove from tail

And there is yet methods to insert and remove at specified indices and
more. Say goodbye to primitive data structures implementation as we
were used in C.

Happy rubying.

Adriano.

 

[James Edward Gray II]

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

Because Array supports push, pop, shift, unshift and splice, we tend to
just use Arrays for this kind of thing. Can you give us an example of
what you're trying to do?

James Edward Gray II

 

[Robert Klemme]

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.newobj, rev, :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

 

[Austin Ziegler]

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

irb(main):001:0> a = %w(The brown fox jumped the dog.)
=> ["The", "brown", "fox", "jumped", "the", "dog."]
irb(main):002:0> a[1, 0] = "quick"; a
=> ["The", "quick", "brown", "fox", "jumped", "the", "dog."]
irb(main):003:0> a[-1, 0] = "lazy"; a
=> ["The", "quick", "brown", "fox", "jumped", "the", "lazy", "dog."]
irb(main):007:0> a[a.index("jumped") + 1, 0] = "over"; a
=> ["The", "quick", "brown", "fox", "jumped", "over", "the", "lazy", "dog."]
irb(main):008:0>

You probably don't need a linked list for this; there are other things
where a linked list or a circular linked list would be useful and
necessary, but not this as such.

-austin

 

[Randy Kramer]

Ruby arrays are incredibly more flexible than C arrays. You can insert
an element into an array _between_ two other elements.

a = [1,2,3]
a[1,0] = 4 => [1,4,2,3]

You can delete an element from an array any number of ways. The
delete_at method works if you know the index of the element you want to
delete.

But (just asking), what about performance? Is an entire new array created, or
is the new stuff (only) put in a newly allocated piece of memory and a
pointer/reference/whatever inserted into (maybe a linked list which
implements) the array?

Randy Kramer

 

[Douglas Livingstone]

But (just asking), what about performance? Is an entire new array created, or
is the new stuff (only) put in a newly allocated piece of memory and a
pointer/reference/whatever inserted into (maybe a linked list which
implements) the array?

irb(main):001:0> a = [1,2,3]
=> [1, 2, 3]
irb(main):002:0> b = a
=> [1, 2, 3]
irb(main):003:0> b[2,0] = 4
=> 4
irb(main):004:0> a
=> [1, 2, 4, 3]
irb(main):005:0> b
=> [1, 2, 4, 3]
irb(main):006:0> a == b
=> true

[] is sugar for Array.new, they are objects like any other.

hth,
Douglas