On Jan 12, 2007, at 13:00, [EMAIL PROTECTED] wrote:

<snip />
   Just a quick comment on this, given the above stats you might
consider having a single Object field and switch the type of object
from the actual child (when there is a single child) to a List of
children when there are multiple children:

Also an interesting suggestion, thanks!

I'm still wondering whether the use of separate lists could not be avoided altogether. Based on Jörgs statistics, I'd say that the number of children will most likely never reach the level where using direct index-based access (ArrayList) has its benefits over traversing a tree of references (LinkedList).

On top of that, all we really seem to need further in the code, is an iterator over that list, not the list itself...

I'm thinking, roughly all we need is something like:
class Node {
  Object parent;
  Object firstChild;
  Object[] siblings; //if there are siblings, always length=2
class ChildIterator
  Node currentNode;

  ChildIterator(Node n) {
    currentNode = n.firstChild;

  hasNext() {
    return (currentNode.siblings != null)
         && (currentNode.siblings[1] != null);

  next() {
    if (hasNext()) {
      return currentNode.siblings[1];
    } else {
      throw new NoSuchElementException();


The backing list would be defined by the pointers between the objects, and not exist as a separate object (list) itself.

I'm still not completely sure about my estimation, but in the picture painted earlier (instance count of ArrayList and Object[]), those extra reference(s) for the siblings could turn out to be well worth it, since they'd only slightly increase the instance size of already existing objects, but they do avoid the creation of so many new ArrayList instances.



Reply via email to