Hierarchy & data structure in Java (or XML to Object conversion: best practices)

Question

The problem: Let's say there is an XML file that contains both the data and the hierarchy of certain elements of interest to the application:

  <root>
    <node title="lvl1Node">
     <node title="lvl2Node">
      <node title="lvl3Node"></node>
     </node>
    </node>
    <node title="lvl1Node2"></node>
    <node title="lvl1Node3">
     <node title="lvl2Node2">
      <node title="lvl3Node2">
       <node title="lvl4Node"></node>
      </node>
     </node>
    </node>
  </root>

Now let's say your application needs to provide an API to retrieve these nodes. You need to write a method that returns the nodes without losing information about their hierarchy.

My question is how would you go about it ? What kind of data type would you use. A tree data type is the obvious answer but it not provided in the standard Collections API and writing it yourself is always a last resort (programmers are lazy, reinventing the wheel etc).

I also thought of an ArrayList where each item is either an Object (for node without subnodes) or an Arraylist (for node with subnodes) but I like generics and this feels too much like a hack. Is there a cleverer way to do it ?

Answer 1

If each item has a title, then you can use a Map instead of an List. Makes accessing each item more intuitive (Using the name of the node instead of an index).

Answer 2

The last time I needed a Tree structure - I cheated and used the Tree Model. Its not pretty (involves pulling in Swing) but it works really well! Its a shame that they didn't put this in the Collections API

Answer 3

The first question you should be asking yourself is how do you need to access the data? Depth-first iterations? Search for specific values?

At first glance, this is a tree of nodes where each node can have zero or more children.

So it goes something like this:

class Node {
  Node parent;
  List<Node> children;
}

It's like a linked list, but each node can branch out into an arbitrary number of children. If you need to find items directly by id the best bet is to keep a seperate hashmap index.

Answer 4

Err. What exactly do you need that isn't covered by DOM?