Data structure for "linked list"


#1

Folks,

I’m trying to figure out the best approach to creating a linked list
conceptually in RoR. This is what I’m looking at doing and want to
know if there is a best practice approach to this already (my search
didn’t seem to indicate this) OR if I’m completely off base on the
naming convention I’m using:

category table
id
name

categories_categories table (not defined as a model; should it be?)
id
category_id
parent_category_id

Then I should be able to do things like this…

Fruit -> Berry -> Blueberry
Fruit -> Berry -> Raspberry
Fruit -> Apple -> Rome
Food -> Fruit
Food -> Beverage
etc.

where I create these by recursively(?) accessing the
categories_categories data joined to the category data. The start of a
category will be implied where parent_category_id is 0. And those
parent records could be a foreign key like so

categories_categories_object table
object_id
categories_categories_id

where object is the other model/table in the many-to-many
relationship.
Is this the appropriate way to do something like this? If not, could
someone point me to some documentation or an example of how I should
be handling this.

Thanks,
Jack


#2

I just found some info in the Agile Rails book and with a bit more
searching I discovered I could look into one of these:

acts_as_list
acts_as_tree
acts_as_nested

I don’t think the list feature works since I’m looking at a hierarchy
and want to be able to re-use the same term in different levels.

Can acts_as_tree allow for multiple trees? i.e. more than one NULL
parent_id?

This also seems to imply that I do want to make my
categories_categories table a full blown model, with a better name of
course.

Could someone confirm I’m on the right track?

Thanks,
Jack


#3

On Wed, Apr 1, 2009 at 1:03 PM, Jack removed_email_address@domain.invalid wrote:

I’m trying to figure out the best approach to creating a linked list
conceptually in RoR.

http://www.koders.com/ruby/fidCB5A463AB556F4FFD20E03139FF59563B118D108.aspx?s=socket


Greg D.
http://destiney.com/


#4

Jack wrote:

Folks,

I’m trying to figure out the best approach to creating a linked list
conceptually in RoR.
[…]

What you describe is a tree, not really a linked list. You could use
acts_as_tree for this, but you’ll probably get better results with
awesome_nested_set or something similar.

Best,

Marnen Laibow-Koser
removed_email_address@domain.invalid
http://www.marnen.org