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.
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.
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
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.
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.
"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
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
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.
--
Austin Ziegler * halostatue@gmail.com
* Alternate: austin@halostatue.ca
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
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.
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
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.
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
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?
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.
PGP.sig (194 Bytes)
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?
--
Eric Hodel - drbrain@segment7.net - http://segment7.net
FEC2 57F1 D465 EB15 5D6E 7C11 332A 551C 796C 9F04
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.
Douglas,
Thanks! (I should have tried that myself.) And, I've now done so, throwing
in several a.id and b.ids. Looks like it's the same array (the same object)
before and after, so, I think that means the new value is linked in.
(Presumably, if the array had to be rewritten to be expanded, the object would
have a new id (i.e., address), iiuc.)
regards,
Randy Kramer
On Monday 04 April 2005 03:44 pm, Douglas Livingstone wrote:
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
=> trueis sugar for Array.new, they are objects like any other.
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?
No. Sometimes curiosity gets the best of me. 
regards,
Randy Kramer
On Monday 04 April 2005 04:29 pm, Tim Hunter wrote:
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.
It does add confidence in your code if you have an idea in your head
of how it will work
Douglas
On Apr 4, 2005 9:29 PM, Tim Hunter <sastph@sas.com> wrote:
Don't know. Don't care. Do you think your application's performance will
be dominated by array insertions and deletions?
I disagree. It doesn't add any confidence to my driving to know how every little component inside the car works. I just want it to work. Same with my code. Until something doesn't work the way it should, I don't care how it does it under the hood. I operate on the assumption that the language will take care of stuff (correctly) for me, otherwise I'd code in assembler.
On Apr 4, 2005, at 2:58 PM, Douglas Livingstone wrote:
On Apr 4, 2005 9:29 PM, Tim Hunter <sastph@sas.com> wrote:
Don't know. Don't care. Do you think your application's performance will
be dominated by array insertions and deletions?It does add confidence in your code if you have an idea in your head of how it will work
It does add confidence to know about Array.new, and it does add
confidence if you know your car stears with the front wheels or the
back wheels. I agree that you don't need to know how "every little
component works", that would be taking it too far. But even then, I
see no problem with someone asking about the details.
Douglas
On Apr 4, 2005 11:03 PM, Ryan Davis <ryand-ruby@zenspider.com> wrote:
I disagree. It doesn't add any confidence to my driving to know how
every little component inside the car works.
>
> I disagree. It doesn't add any confidence to my driving to know how
> every little component inside the car works.It does add confidence to know about Array.new, and it does add
confidence if you know your car stears with the front wheels or the
back wheels. I agree that you don't need to know how "every little
component works", that would be taking it too far. But even then, I
see no problem with someone asking about the details.
Indeed, Ignorance about implementations leads to code like the following
pixels =
width=100
height=100
height.times { |y|
pixels[y]=
width.times {|x|
pixels[y] = Pixel.new(100)
}
}
Ie 100000 objects being created just because its good OO practice.
On Apr 5, 2005 8:15 AM, Douglas Livingstone <rampant@gmail.com> wrote:
On Apr 4, 2005 11:03 PM, Ryan Davis <ryand-ruby@zenspider.com> wrote:
Douglas
--
Into RFID? www.rfidnewsupdate.com Simple, fast, news.