Asp Forum - doubly linked list in Ruby?

ed_davis2

4/4/2005 6:37:00 PM

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.

16 Answers

Tim Hunter

4/4/2005 6:54:00 PM

ed_davis2 wrote:
> 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

4/4/2005 6:56:00 PM

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 Gray

4/4/2005 7:01:00 PM

On Apr 4, 2005, at 1:39 PM, ed_davis2 wrote:

> 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

4/4/2005 7:05:00 PM

"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.rub...

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

Austin Ziegler

4/4/2005 7:17:00 PM

On Apr 4, 2005 2:39 PM, ed_davis2 <ed_davis2@yahoo.com> wrote:
> 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
--
Austin Ziegler * halostatue@gmail.com
* Alternate: austin@halostatue.ca

Randy Kramer

4/4/2005 7:39:00 PM

On Monday 04 April 2005 03:09 pm, Tim Hunter wrote:
> 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

4/4/2005 7:44:00 PM

On Apr 4, 2005 8:39 PM, Randy Kramer <rhkramer@gmail.com> wrote:
>
> 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

Aria Stewart

4/4/2005 7:47:00 PM

On Tue, 2005-04-05 at 03:39 +0900, ed_davis2 wrote:
> 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.

In Ruby, you have it easy: Variables themselves are pointers. If you
have a class like so:

class Node
attr_accessor :up, :down, :string
end

then you can just assign a Node to up, a Node to down, and a String to
string.

That class is the equivalent of a C structure like so:

struct node {
struct node *up;
struct node *down;
char **string;
}

Though in C, you could get away with just char * for string.

Ari

Eric Hodel

4/4/2005 7:54:00 PM

On 04 Apr 2005, at 12:39, Randy Kramer wrote:

> On Monday 04 April 2005 03:09 pm, Tim Hunter wrote:
>> 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?

Why do you care?

Until you've written the app and profiled it and found that Array
insertion is slow, there's no point in attempting to optimize it.

Premature optimization is the root of all evil.

--
Eric Hodel - drbrain@segment7.net - http://se...
FEC2 57F1 D465 EB15 5D6E 7C11 332A 551C 796C 9F04

Tim Hunter

4/4/2005 8:03:00 PM

Randy Kramer wrote:
> 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?

Don't know. Don't care. Do you think your application's performance will
be dominated by array insertions and deletions?

Not too mention, the standard Array methods are written in C. I have no
reason to think that manipulating a Ruby-based linked list with Ruby
code would be faster.

comp.lang.ruby

doubly linked list in Ruby?

ed_davis2

Tim Hunter

Adriano Ferreira

James Gray

Robert Klemme

Austin Ziegler

Randy Kramer

Douglas Livingstone

Aria Stewart

Eric Hodel

Tim Hunter

x Login to ForumsZone