Collection to implement linked structure traverse up and down

[ruds]

Hi,
I want to implement a tree or a linked structure where I can traverse
to the parent of a node also and the same node refers to another data
related to it too.
for example i have a set [0,1,2,3,...10], consider these as levels,
so ) will be at top i.e the root, 1 will be first level, and so on.
each of these levels will again have some branches and some data needs
to be referenced with this too for comparison with another similar
tree of this kind. Also, once I get the comparion of the branch X done
I need to traverse to its parent level and it higher level.
I think TreeMapClass and LinkedHashMapClass will be helpfull to me in
this regard.
This need not be a tree, it can be a linked list too.
Please tell me am i on the right path? Kindly, suggest the
implementation too.

 

[Arved Sandstrom]

Hi,
I want to implement a tree or a linked structure where I can traverse
to the parent of a node also and the same node refers to another data
related to it too.
for example i have a set [0,1,2,3,...10], consider these as levels,
so ) will be at top i.e the root, 1 will be first level, and so on.
each of these levels will again have some branches and some data needs
to be referenced with this too for comparison with another similar
tree of this kind. Also, once I get the comparion of the branch X done
I need to traverse to its parent level and it higher level.
I think TreeMapClass and LinkedHashMapClass will be helpfull to me in
this regard.
This need not be a tree, it can be a linked list too.
Please tell me am i on the right path? Kindly, suggest the
implementation too.

If I understand you correctly, one of your requirements is that each
node of the data structure has associated user data, which is distinct
from references to other nodes. This is common.

The distinguishing feature of a node for a singly linked list is that it
has a reference to a "next" sibling. Nodes for doubly linked lists have
two references, one to a "previous" sibling, one to a "next" sibling.
Nodes for a binary tree have zero, one or two references, where any
reference is to a "child". Any or all of these nodes can be implemented
with objects that have not only the required references but also
variable, user-defined data.

It's also helpful to distinguish between concept and implementation. At
this stage we're talking concepts, and the language is clearly that of
trees. In particular where you are talking about tree comparisons this
is all very standard stuff...although your determination of how two
trees compare will typically not start at the bottom.

I don't think TreeMap or LinkedHashMap will help you much. These are
both maps. You can distort them into trees but that's not their intended
purpose. If you're looking to locate a starting implementation you could
do worse than use javax.swing.tree.TreeModel (implementation class
javax.swing.tree.DefaultTreeModel) and javax.swing.tree.TreeNode
(MutableTreeNode, DefaultMutableTreeNode). These are general purpose and
don't have to be used with Swing at all.

AHS

 

[Roedy Green]

Please tell me am i on the right path?

There are two kinds of links:

1. links which define which objects are in the Set and how to find
them.

2. links that define interrelationships between the objects.

I would expect things to become clearer if you expected of your
Collection to handle type (1), and you handled type (2) yourself
independent of the Collection.

I might help to recall it is possible to have a HashMap an ArrayList
and a TreeSet simultaneously all on the same group of objects.

So in your case you can have a Map for finding things, and a
completely independent set of links defining your directed graph (to
use the mathematical name for such a generic structure).

If it is truly a tree, don't forget about JTree.

see http://mindprod.com/jgloss/treeset.html
http://mindprod.com/jgloss/treemap.html
http://mindprod.com/jgloss/jtree.html
http://mindprod.com/jgloss/tree.html

--
Roedy Green Canadian Mind Products
http://mindprod.com
For me, the appeal of computer programming is that
even though I am quite a klutz,
I can still produce something, in a sense
perfect, because the computer gives me as many
chances as I please to get it right.

 

[Martin Gregorie]

Hi,
I want to implement a tree or a linked structure where I can traverse to
the parent of a node also and the same node refers to another data
related to it too.
for example i have a set [0,1,2,3,...10], consider these as levels, so )
will be at top i.e the root, 1 will be first level, and so on. each of
these levels will again have some branches and some data needs to be
referenced with this too for comparison with another similar tree of
this kind. Also, once I get the comparion of the branch X done I need to
traverse to its parent level and it higher level.
I think TreeMapClass and LinkedHashMapClass will be helpfull to me in
this regard.
This need not be a tree, it can be a linked list too.
Please tell me am i on the right path? Kindly, suggest the
implementation too.

The main problem is that, unless I missed something, none of the standard
Tree* classes implement a getParent() method - if you need that operation
you'll probably need to implement a red-black tree or Btree yourself, but
once that's done there's no reason why each node shouldn't use some
Collection class to hold your data items.

 

[ruds]

Thanks all.
Roedy Green: Can you elaborate some more on "a HashMap an ArrayList
and a TreeSet simultaneously all on the same group of objects."

 

[Henk van Voorthuijsen]

If it is truly a tree, don't forget about JTree.

You mean TreeModel and its implementation(s), I hope?

Henk

 

[Lew]

Roedy Green: Can you elaborate some more on "a HashMap an ArrayList
and a TreeSet simultaneously all on the same group of objects."

Consider this fragment:

Map<Foo, Bar> bars = new HashMap<>();
List<Bar> barVals = new ArrayList<>();
Set<Foo> foos = new TreeSet<>();
....
Foo foo = new Foo();
Bar bar = new Bar();
bars.put(foo, bar);
barVals.add(bar);
foos.add(foo);
....

A pointer to the same 'foo' appears in 'bars' and in 'foos'. A pointer to the same 'bar' appears in 'bars' and in 'barVals'.

Do that again with a new 'foo' and a new 'bar' a few times and you have "a group of objects" in all three collections simultaneously.

 

[ruds]

Consider this fragment:

 Map<Foo, Bar> bars = new HashMap<>();
 List<Bar> barVals = new ArrayList<>();
 Set<Foo> foos = new TreeSet<>();
...
 Foo foo = new Foo();
 Bar bar = new Bar();
 bars.put(foo, bar);
 barVals.add(bar);
 foos.add(foo);
...

A pointer to the same 'foo' appears in 'bars' and in 'foos'.  A pointerto the same 'bar' appears in 'bars' and in 'barVals'.

Do that again with a new 'foo' and a new 'bar' a few times and you have "a group of objects" in all three collections simultaneously.

thanks will check this out.