DOM Impl: Array or Linked List?

[Don Park]

Docuverse DOM SDK is implemented using the array approach with the last
accessed index cached to improve next/prevSibling performance.  Resulting
implementation is fast for index-based access to child nodes and slightly
slower for sibling-based access (only 10% slower than linked-list version).
Modification to the tree is fast when appending nodes (i.e. building new
tree) but is somewhat slow when inserting new nodes since array contents
have to be shifted around.  If your XML document has gazillion child nodes
per element, performance will suffer quite a bit.

You can get around the update problem by applying the Strategy pattern to
child array implementation.  On insert, check to see if the array is big
enough to justify using different type of array implementation (i.e. sparse
array).  One caveat is that this tends to increase the number of child list
array (smart NodeLists and NodeList implementation strategies).  There are
ways to minimize this problem though.

So the bottom line is, you are on the right track.

Don Park
Docuverse

-----Original Message-----
From: Clark Evans <clark.evans at manhattanproject.com>
To: xml-dev at ic.ac.uk <xml-dev at ic.ac.uk>
Date: Wednesday, March 10, 1999 4:15 PM
Subject: DOM Impl: Array or Linked List?


>I've been struggling with this slightly, and would
>like your feedback.  I'm building a DOM tree.  For
>the internal representation, I see two options:
>
>A) A linked list for children
>
>* Easy inserts in middle of list
>* Slower non-sequential reads
>
>B) An array for children
>
>* Harder inserts in middle of list
>* Faster non-sequential reads
>
>Anyway, I was thinking of implementing
>a compromise, a sparse array with
>configurable spacing, depending upon
>the document.
>
>Thoughts?
>
>Thank you.
>
>Clark
>
>xml-dev: A list for W3C XML Developers. To post, mailto:xml-dev at ic.ac.uk
>Archived as: http://www.lists.ic.ac.uk/hypermail/xml-dev/ and on
CD-ROM/ISBN 981-02-3594-1
>To (un)subscribe, mailto:majordomo at ic.ac.uk the following message;
>(un)subscribe xml-dev
>To subscribe to the digests, mailto:majordomo at ic.ac.uk the following
message;
>subscribe xml-dev-digest
>List coordinator, Henry Rzepa (mailto:rzepa at ic.ac.uk)
>
>


xml-dev: A list for W3C XML Developers. To post, mailto:xml-dev at ic.ac.uk
Archived as: http://www.lists.ic.ac.uk/hypermail/xml-dev/ and on CD-ROM/ISBN 981-02-3594-1
To (un)subscribe, mailto:majordomo at ic.ac.uk the following message;
(un)subscribe xml-dev
To subscribe to the digests, mailto:majordomo at ic.ac.uk the following message;
subscribe xml-dev-digest
List coordinator, Henry Rzepa (mailto:rzepa at ic.ac.uk)