diff --git a/src/org/apache/xerces/dom/AttrImpl.java b/src/org/apache/xerces/dom/AttrImpl.java
index 1db5f1e..15bbbf9 100644
--- a/src/org/apache/xerces/dom/AttrImpl.java
+++ b/src/org/apache/xerces/dom/AttrImpl.java
@@ -237,19 +237,19 @@
             if (needsSyncChildren()) {
                 synchronizeChildren();
             }
-            while(firstChild!=null)
-                internalRemoveChild(firstChild,MUTATION_LOCAL);
+            while (length != 0)
+                internalRemoveChild(children[0], MUTATION_LOCAL);
         }
         else
         {
             // simply discard children
-            if (firstChild != null) {
-                // remove ref from first child to last child
-                firstChild.previousSibling = null;
-                firstChild.isFirstChild(false);
-                // then remove ref to first child
-                firstChild   = null;
+            for (int i = 0; i < length; i++) {
+                // remove ref from every child to this node
+                children[i].ownerNode = ownerDocument;
+                children[i].isOwned(false);
+                children[i].parentIndex = -1;
             }
+            length = 0;
             needsSyncChildren(false);
         }
 
@@ -283,17 +283,15 @@
         if (needsSyncChildren()) {
             synchronizeChildren();
         }
-        if (firstChild == null) {
+        if (length == 0) {
             return "";
         }
-        ChildNode node = firstChild.nextSibling;
-        if (node == null) {
-            return firstChild.getNodeValue();
+        if (length == 1) {
+            return children[0].getNodeValue();
         }
-    	StringBuffer value = new StringBuffer(firstChild.getNodeValue());
-    	while (node != null) {
-            value.append(node.getNodeValue());
-            node = node.nextSibling;
+    	StringBuffer value = new StringBuffer(children[0].getNodeValue());
+    	for (int i = 1; i < length; i++) {
+            value.append(children[i].getNodeValue());
     	}
     	return value.toString();
 
@@ -353,20 +351,15 @@
     public void normalize() {
 
     	Node kid, next;
-    	for (kid = firstChild; kid != null; kid = next) {
-    		next = kid.getNextSibling();
-
-    		// If kid and next are both Text nodes (but _not_ CDATASection,
-    		// which is a subclass of Text), they can be merged.
-    		if (next != null
-			 && kid.getNodeType() == Node.TEXT_NODE
-			 && next.getNodeType() == Node.TEXT_NODE)
-    	    {
-    			((Text)kid).appendData(next.getNodeValue());
-    			removeChild(next);
-    			next = kid; // Don't advance; there might be another.
-    		}
-
+    	for (int i = 0; i < length; i++) {
+            // If kid and next are both Text nodes (but _not_ CDATASection,
+            // which is a subclass of Text), they can be merged.
+            if (i + 1 < length
+                && children[i].getNodeType() == Node.TEXT_NODE
+                && children[i + 1].getNodeType() == Node.TEXT_NODE) {
+                ((Text)children[i]).appendData(children[i + 1].getNodeValue());
+                removeChild(children[i + 1]);
+            }
         }
 
     } // normalize()
diff --git a/src/org/apache/xerces/dom/ChildAndParentNode.java b/src/org/apache/xerces/dom/ChildAndParentNode.java
index e5fd5c4..306a2ae 100644
--- a/src/org/apache/xerces/dom/ChildAndParentNode.java
+++ b/src/org/apache/xerces/dom/ChildAndParentNode.java
@@ -80,19 +80,8 @@
     /** Owner document. */
     protected DocumentImpl ownerDocument;
 
-    /** First child. */
-    protected ChildNode firstChild = null;
-
-    // transients
-
-    /** Cached node list length. */
-    protected transient int nodeListLength = -1;
-
-    /** Last requested node. */
-    protected transient ChildNode nodeListNode;
-
-    /** Last requested node index. */
-    protected transient int nodeListIndex = -1;
+    protected ChildNode		children [];
+    protected int		length;
 
     //
     // Constructors
@@ -110,6 +99,53 @@
     /** Constructor for serialization. */
     public ChildAndParentNode() {}
 
+    /**
+     * Called to minimize space utilization.  Affects only
+     * this node; children must be individually trimmed.
+     */
+    public void trimToSize ()
+    {
+	if (length == 0)
+	    children = null;
+        else if (children.length != length) {
+	    ChildNode	temp [] = new ChildNode [length];
+
+            System.arraycopy (children, 0, temp, 0, length);
+	    children = temp;
+	}
+    }
+
+    public void reduceWaste ()
+    {
+	if (children == null)
+	    return;
+
+	//
+	// Arbitrary -- rather than paying trimToSize() costs
+	// on most elements, we routinely accept some waste but
+	// do try to reduce egregious waste.  Interacts with
+	// the array allocation done in appendChild.
+	//
+	if ((children.length - length) > 6)
+            trimToSize ();
+    }
+
+    /**
+     * Returns the index of the node in the list of children, such
+     * that <em>item()</em> will return that child.
+     *
+     * @param maybeChild the node which may be a child of this one
+     * @return the index of the node in the set of children, or
+     *	else -1 if that node is not a child
+     */
+    final protected int getIndexOf(Node maybeChild)
+    {
+	for (int i = 0; i < length; i++)
+	    if (children[i] == maybeChild)
+		return i;
+	return -1;
+    }
+
     //
     // NodeList methods
     //
@@ -145,18 +181,13 @@
         }
 
     	// Need to break the association w/ original kids
-    	newnode.firstChild      = null;
-
-        // invalidate cache for children NodeList
-        newnode.nodeListIndex = -1;
-        newnode.nodeListLength = -1;
+        newnode.children = null;
+        newnode.length = 0;
 
         // Then, if deep, clone the kids too.
     	if (deep) {
-            for (Node child = firstChild;
-                 child != null;
-                 child = child.getNextSibling()) {
-                newnode.appendChild(child.cloneNode(true));
+            for (int i = 0; i < length; i++) {
+                newnode.appendChild(children[i].cloneNode(true));
             }
         }
 
@@ -189,9 +220,9 @@
         if (needsSyncChildren()) {
             synchronizeChildren();
         }
-	for (Node child = firstChild;
-	     child != null; child = child.getNextSibling()) {
-	    ((NodeImpl) child).setOwnerDocument(doc);
+        ownerDocument = doc;
+	for (int i = 0; i < length; i++) {
+	    children[i].setOwnerDocument(doc);
 	}
         ownerDocument = doc;
     }
@@ -204,7 +235,7 @@
         if (needsSyncChildren()) {
             synchronizeChildren();
         }
-        return firstChild != null;
+        return length > 0;
     }
 
     /**
@@ -236,7 +267,9 @@
         if (needsSyncChildren()) {
             synchronizeChildren();
         }
-    	return firstChild;
+        if (length == 0)
+            return null;
+    	return children[0];
 
     }   // getFirstChild():Node
 
@@ -246,20 +279,16 @@
         if (needsSyncChildren()) {
             synchronizeChildren();
         }
-        return lastChild();
+	if (length == 0)
+	    return null;
+	return children[length - 1];
 
     } // getLastChild():Node
 
     final ChildNode lastChild() {
-        // last child is stored as the previous sibling of first child
-        return firstChild != null ? firstChild.previousSibling : null;
-    }
-
-    final void lastChild(ChildNode node) {
-        // store lastChild as previous sibling of first child
-        if (firstChild != null) {
-            firstChild.previousSibling = node;
-        }
+	if (length == 0)
+	    return null;
+	return children[length - 1];
     }
 
     /**
@@ -357,11 +386,9 @@
 
             // No need to check kids for right-document; if they weren't,
             // they wouldn't be kids of that DocFrag.
-            for (Node kid = newChild.getFirstChild(); // Prescan
-                 kid != null;
-                 kid = kid.getNextSibling()) {
-
-                if (errorChecking && !ownerDocument.isKidOK(this, kid)) {
+            for (int i = 0; i < length; i++) { // Prescan
+                if (errorChecking &&
+                    !ownerDocument.isKidOK(this, children[i])) {
                     throw new DOMExceptionImpl(
                                            DOMException.HIERARCHY_REQUEST_ERR, 
                                            "DOM006 Hierarchy request error");
@@ -403,66 +430,53 @@
                 oldparent.removeChild(newInternal);
             }
 
-            // Convert to internal type, to avoid repeated casting
-            ChildNode refInternal = (ChildNode)refChild;
+            if (refChild == null) { // append
 
-            // Attach up
-            newInternal.ownerNode = this;
-            newInternal.isOwned(true);
+                // this is the only place this vector needs allocating,
+                // though it may also need to be grown in insertBefore.
+                // most elements have very few children
+                if (children == null)
+                    children = new ChildNode [3];
+                else if (children.length == length) {
+                    ChildNode temp [] = new ChildNode [length * 2];
+                    System.arraycopy(children, 0, temp, 0, length);
+                    children = temp;
+                }
 
-            // Attach before and after
-            // Note: firstChild.previousSibling == lastChild!!
-            if (firstChild == null) {
-                // this our first and only child
-                firstChild = newInternal;
-                newInternal.isFirstChild(true);
-                newInternal.previousSibling = newInternal;
+                // set parent
+                newInternal.ownerNode = this;
+                newInternal.isOwned(true);
+                newInternal.parentIndex = length;
+
+                children [length++] = newInternal;
+
             } else {
-                if (refInternal == null) {
-                    // this is an append
-                    ChildNode lastChild = firstChild.previousSibling;
-                    lastChild.nextSibling = newInternal;
-                    newInternal.previousSibling = lastChild;
-                    firstChild.previousSibling = newInternal;
-                } else {
-                    // this is an insert
-                    if (refChild == firstChild) {
-                        // at the head of the list
-                        firstChild.isFirstChild(false);
-                        newInternal.nextSibling = firstChild;
-                        newInternal.previousSibling =
-                            firstChild.previousSibling;
-                        firstChild.previousSibling = newInternal;
-                        firstChild = newInternal;
-                        newInternal.isFirstChild(true);
-                    } else {
-                        // somewhere in the middle
-                        ChildNode prev = refInternal.previousSibling;
-                        newInternal.nextSibling = refInternal;
-                        prev.nextSibling = newInternal;
-                        refInternal.previousSibling = newInternal;
-                        newInternal.previousSibling = prev;
-                    }
+
+                // grow array if needed
+                if (children.length == length) {
+                    ChildNode temp [] = new ChildNode [length * 2];
+                    System.arraycopy(children, 0, temp, 0, length);
+                    children = temp;
+                }
+
+                for (int i = 0; i < length; i++) {
+                    if (children [i] != refChild)
+                        continue;
+
+                    // set parent
+                    newInternal.ownerNode = this;
+                    newInternal.isOwned(true);
+                    newInternal.parentIndex = i;
+
+                    System.arraycopy(children, i, children, i + 1, length - i);
+                    children [i] = newInternal;
+                    length++;
+                    break;
                 }
             }
 
             changed();
 
-            // update cached length if we have any
-            if (nodeListLength != -1) {
-                nodeListLength++;
-            }
-            if (nodeListIndex != -1) {
-                // if we happen to insert just before the cached node, update
-                // the cache to the new node to match the cached index
-                if (nodeListNode == refInternal) {
-                    nodeListNode = newInternal;
-                } else {
-                    // otherwise just invalidate the cache
-                    nodeListIndex = -1;
-                }
-            }
-
             if(MUTATIONEVENTS && ownerDocument.mutationEvents)
             {
                 // MUTATION POST-EVENTS:
@@ -632,50 +646,24 @@
             }
         } // End mutation preprocessing
 
-        // update cached length if we have any
-        if (nodeListLength != -1) {
-            nodeListLength--;
-        }
-        if (nodeListIndex != -1) {
-            // if the removed node is the cached node
-            // move the cache to its (soon former) previous sibling
-            if (nodeListNode == oldInternal) {
-                nodeListIndex--;
-                nodeListNode = oldInternal.previousSibling();
-            } else {
-                // otherwise just invalidate the cache
-                nodeListIndex = -1;
+        // Patch tree past oldChild
+	for (int i = 0; i < length; i++) {
+	    if (children [i] != oldInternal)
+		continue;
+	    if ((i + 1) != length) {
+		System.arraycopy (children, i + 1, children, i,
+		    (length - 1) - i);
             }
-        }
+	    length--;
+	    children[length] = null;
 
-        // Patch linked list around oldChild
-        // Note: lastChild == firstChild.previousSibling
-        if (oldInternal == firstChild) {
-            // removing first child
-            oldInternal.isFirstChild(false);
-            firstChild = oldInternal.nextSibling;
-            if (firstChild != null) {
-                firstChild.isFirstChild(true);
-                firstChild.previousSibling = oldInternal.previousSibling;
-            }
-        } else {
-            ChildNode prev = oldInternal.previousSibling;
-            ChildNode next = oldInternal.nextSibling;
-            prev.nextSibling = next;
-            if (next == null) {
-                // removing last child
-                firstChild.previousSibling = prev;
-            } else {
-                // removing some other child in the middle
-                next.previousSibling = prev;
-            }
-        }
+            break;
+	}
 
         // Remove oldInternal's references to tree
         oldInternal.ownerNode       = ownerDocument;
         oldInternal.isOwned(false);
-        oldInternal.nextSibling     = null;
-        oldInternal.previousSibling = null;
+        oldInternal.parentIndex = -1;
 
         changed();
 
@@ -755,24 +743,7 @@
      * @return int
      */
     public int getLength() {
-
-        if (nodeListLength == -1) { // is the cached length invalid ?
-            ChildNode node;
-            // start from the cached node if we have one
-            if (nodeListIndex != -1 && nodeListNode != null) {
-                nodeListLength = nodeListIndex;
-                node = nodeListNode;
-            } else {
-                node = firstChild;
-                nodeListLength = 0;
-            }
-            for (; node != null; node = node.nextSibling) {
-                nodeListLength++;
-            }
-        }
-
-        return nodeListLength;
-
+        return length;
     } // getLength():int
 
     /**
@@ -782,32 +753,13 @@
      * @param Index int
      */
     public Node item(int index) {
-        // short way
-        if (nodeListIndex != -1 && nodeListNode != null) {
-            if (nodeListIndex < index) {
-                while (nodeListIndex < index && nodeListNode != null) {
-                    nodeListIndex++;
-                    nodeListNode = nodeListNode.nextSibling;
-                }
-            }
-            else if (nodeListIndex > index) {
-                while (nodeListIndex > index && nodeListNode != null) {
-                    nodeListIndex--;
-                    nodeListNode = nodeListNode.previousSibling();
-                }
-            }
-            return nodeListNode;
-        }
-
-        // long way
-        nodeListNode = firstChild;
-        for (nodeListIndex = 0; 
-             nodeListIndex < index && nodeListNode != null; 
-             nodeListIndex++) {
-            nodeListNode = nodeListNode.nextSibling;
-        }
-        return nodeListNode;
-
+	if (length == 0 || index >= length)
+	    return null;
+	try {
+	    return children[index];
+	} catch (ArrayIndexOutOfBoundsException e) {
+	    return null;
+	}
     } // item(int):Node
 
     //
@@ -822,8 +774,8 @@
     public void normalize() {
 
         Node kid;
-        for (kid = firstChild; kid != null; kid = kid.getNextSibling()) {
-            kid.normalize();
+        for (int i = 0; i < length; i++) {
+            children[i].normalize();
         }
     }
 
@@ -850,11 +802,9 @@
             }
 
             // Recursively set kids
-            for (ChildNode mykid = firstChild;
-                 mykid != null;
-                 mykid = mykid.nextSibling) {
-                if(!(mykid instanceof EntityReference)) {
-                    mykid.setReadOnly(readOnly,true);
+            for (int i = 0; i < length; i++) {
+                if(!(children[i] instanceof EntityReference)) {
+                    children[i].setReadOnly(readOnly,true);
                 }
             }
         }
@@ -893,28 +843,29 @@
         // create children and link them as siblings
         DeferredDocumentImpl ownerDocument =
             (DeferredDocumentImpl)this.ownerDocument;
-        ChildNode first = null;
-        ChildNode last = null;
-        for (int index = ownerDocument.getLastChild(nodeIndex);
-             index != -1;
-             index = ownerDocument.getPrevSibling(index)) {
 
-            ChildNode node = (ChildNode)ownerDocument.getNodeObject(index);
-            if (last == null) {
-                last = node;
-            }
-            else {
-                first.previousSibling = node;
-            }
-            node.ownerNode = this;
-            node.isOwned(true);
-            node.nextSibling = first;
-            first = node;
+        // first count them
+        for (int index = ownerDocument.getLastChild(nodeIndex, false);
+             index != -1;
+             index = ownerDocument.getPrevSibling(index, false)) {
+            length++;
         }
-        if (last != null) {
-            firstChild = first;
-            first.isFirstChild(true);
-            lastChild(last);
+
+        // then fluff them up
+        if (length > 0) {
+            children = new ChildNode [length];
+
+            int count = length;
+            for (int index = ownerDocument.getLastChild(nodeIndex);
+                 index != -1;
+                 index = ownerDocument.getPrevSibling(index)) {
+
+                ChildNode node = (ChildNode)ownerDocument.getNodeObject(index);
+                node.ownerNode = this;
+                node.isOwned(true);
+                node.parentIndex = --count;
+                children[count] = node;
+            }
         }
 
         // set mutation events flag back to its original value
@@ -950,10 +901,6 @@
 
         needsSyncChildren(false);
 
-        // initialize transients
-        nodeListLength = -1;
-        nodeListIndex = -1;
-
     } // readObject(ObjectInputStream)
 
 } // class ChildAndParentNode
diff --git a/src/org/apache/xerces/dom/ChildNode.java b/src/org/apache/xerces/dom/ChildNode.java
index 6378d2f..f1857fe 100644
--- a/src/org/apache/xerces/dom/ChildNode.java
+++ b/src/org/apache/xerces/dom/ChildNode.java
@@ -83,11 +83,7 @@
     // Data
     //
 
-    /** Previous sibling. */
-    protected ChildNode previousSibling;
-
-    /** Next sibling. */
-    protected ChildNode nextSibling;
+    int parentIndex = -1;	// cache
 
     //
     // Constructors
@@ -137,10 +133,8 @@
 
     	ChildNode newnode = (ChildNode) super.cloneNode(deep);
     	
-        // Need to break the association w/ original kids
-    	newnode.previousSibling = null;
-        newnode.nextSibling     = null;
-        newnode.isFirstChild(false);
+        // invalidate cache
+    	newnode.parentIndex = -1;
 
     	return newnode;
 
@@ -166,23 +160,47 @@
 
     /** The next child of this node's parent, or null if none */
     public Node getNextSibling() {
-        return nextSibling;
+        NodeImpl parent = parentNode();
+        if (parent == null)
+            return null;
+	if (parentIndex < 0 || parent.item(parentIndex) != this)
+	    parentIndex = parent.getIndexOf(this);
+	return parent.item(parentIndex + 1);
     }
 
     /** The previous child of this node's parent, or null if none */
     public Node getPreviousSibling() {
-        // if we are the firstChild, previousSibling actually refers to our
-        // parent's lastChild, but we hide that
-        return isFirstChild() ? null : previousSibling;
+        NodeImpl parent = parentNode();
+        if (parent == null)
+            return null;
+	if (parentIndex < 0 || parent.item(parentIndex) != this)
+	    parentIndex = parent.getIndexOf(this);
+	return parent.item(parentIndex - 1);
     }
 
     /*
      * same as above but returns internal type
      */
     final ChildNode previousSibling() {
-        // if we are the firstChild, previousSibling actually refers to our
-        // parent's lastChild, but we hide that
-        return isFirstChild() ? null : previousSibling;
+        NodeImpl parent = parentNode();
+        if (parent == null)
+            return null;
+	if (parentIndex < 0 || parent.item(parentIndex) != this)
+	    parentIndex = parent.getIndexOf(this);
+	return (ChildNode) parent.item(parentIndex - 1);
+    }
+
+    //
+    // Protected methods
+    //
+
+    /** Denotes that this node has changed. */
+    protected void changed() {
+        // ++changes; we just let the parent know
+        NodeImpl parentNode = parentNode();
+    	if (parentNode != null) {
+            parentNode.changed();
+        }
     }
 
 } // class ChildNode
diff --git a/src/org/apache/xerces/dom/DeferredDocumentImpl.java b/src/org/apache/xerces/dom/DeferredDocumentImpl.java
index 4a6f950..b617191 100644
--- a/src/org/apache/xerces/dom/DeferredDocumentImpl.java
+++ b/src/org/apache/xerces/dom/DeferredDocumentImpl.java
@@ -1385,24 +1385,26 @@
 
         getNodeType(0);
 
-        // create children and link them as siblings
-        ChildNode first = null;
-        ChildNode last = null;
+        // first count children
+        for (int index = getLastChild(0, false);
+             index != -1;
+             index = getPrevSibling(index, false)) {
+            length++;
+        }
+
+        // then fluff them up
+        children = new ChildNode [length];
+
+        int count = length;
         for (int index = getLastChild(0);
              index != -1;
              index = getPrevSibling(index)) {
 
             ChildNode node = (ChildNode)getNodeObject(index);
-            if (last == null) {
-                last = node;
-            }
-            else {
-                first.previousSibling = node;
-            }
             node.ownerNode = this;
             node.isOwned(true);
-            node.nextSibling = first;
-            first = node;
+            node.parentIndex = --count;
+            children[count] = node;
 
             // save doctype and document type
             int type = node.getNodeType();
@@ -1414,12 +1416,6 @@
             }
         }
 
-        if (first != null) {
-            firstChild = first;
-            first.isFirstChild(true);
-            lastChild(last);
-        }
-
         // set mutation events flag back to its original value
         mutationEvents = orig;
 
diff --git a/src/org/apache/xerces/dom/DocumentImpl.java b/src/org/apache/xerces/dom/DocumentImpl.java
index df52762..7a87423 100644
--- a/src/org/apache/xerces/dom/DocumentImpl.java
+++ b/src/org/apache/xerces/dom/DocumentImpl.java
@@ -294,8 +294,8 @@
              }
 
         if (deep) {
-            for (ChildNode n = firstChild; n != null; n = n.nextSibling) {
-                newdoc.appendChild(newdoc.importNode(n, true));
+            for (int i = 0; i < length; i++) {
+                newdoc.appendChild(newdoc.importNode(children[i], true));
             }
         }
 
diff --git a/src/org/apache/xerces/dom/EntityReferenceImpl.java b/src/org/apache/xerces/dom/EntityReferenceImpl.java
index 2279eae..f4e5597 100644
--- a/src/org/apache/xerces/dom/EntityReferenceImpl.java
+++ b/src/org/apache/xerces/dom/EntityReferenceImpl.java
@@ -233,7 +233,7 @@
      * This doesn't really support editing the Entity though.
      */
     protected void synchronize() {
-        if (firstChild != null) {
+        if (length != 0) {
             return;
         }
     	DocumentType doctype;
diff --git a/src/org/apache/xerces/dom/NodeImpl.java b/src/org/apache/xerces/dom/NodeImpl.java
index 539c7b7..b4c25ff 100644
--- a/src/org/apache/xerces/dom/NodeImpl.java
+++ b/src/org/apache/xerces/dom/NodeImpl.java
@@ -338,6 +338,13 @@
         return null;            // default behavior, overriden in ChildNode
     }
 
+    // overriden in subclasses ParentNode and ChildAndParentNode
+    public void reduceWaste () {}
+
+    protected int getIndexOf (Node maybeChild) {
+        return -1;              // overridden by ParentNode
+    }
+
     /**
      * Return the collection of attributes associated with this node,
      * or null if none. At this writing, Element is the only type of node
diff --git a/src/org/apache/xerces/dom/ParentNode.java b/src/org/apache/xerces/dom/ParentNode.java
index 3feb284..fae4e46 100644
--- a/src/org/apache/xerces/dom/ParentNode.java
+++ b/src/org/apache/xerces/dom/ParentNode.java
@@ -90,19 +90,8 @@
     /** Owner document. */
     protected DocumentImpl ownerDocument;
 
-    /** First child. */
-    protected ChildNode firstChild = null;
-
-    // transients
-
-    /** Cached node list length. */
-    protected transient int nodeListLength = -1;
-
-    /** Last requested node. */
-    protected transient ChildNode nodeListNode;
-
-    /** Last requested node index. */
-    protected transient int nodeListIndex = -1;
+    protected ChildNode		children [];
+    protected int		length;
 
     //
     // Constructors
@@ -120,6 +109,53 @@
     /** Constructor for serialization. */
     public ParentNode() {}
 
+    /**
+     * Called to minimize space utilization.  Affects only
+     * this node; children must be individually trimmed.
+     */
+    public void trimToSize ()
+    {
+	if (length == 0)
+	    children = null;
+        else if (children.length != length) {
+	    ChildNode	temp [] = new ChildNode [length];
+
+            System.arraycopy (children, 0, temp, 0, length);
+	    children = temp;
+	}
+    }
+
+    public void reduceWaste ()
+    {
+	if (children == null)
+	    return;
+
+	//
+	// Arbitrary -- rather than paying trimToSize() costs
+	// on most elements, we routinely accept some waste but
+	// do try to reduce egregious waste.  Interacts with
+	// the array allocation done in appendChild.
+	//
+	if ((children.length - length) > 6)
+            trimToSize ();
+    }
+
+    /**
+     * Returns the index of the node in the list of children, such
+     * that <em>item()</em> will return that child.
+     *
+     * @param maybeChild the node which may be a child of this one
+     * @return the index of the node in the set of children, or
+     *	else -1 if that node is not a child
+     */
+    final protected int getIndexOf(Node maybeChild)
+    {
+	for (int i = 0; i < length; i++)
+	    if (children[i] == maybeChild)
+		return i;
+	return -1;
+    }
+
     //
     // NodeList methods
     //
@@ -155,18 +191,13 @@
         }
 
     	// Need to break the association w/ original kids
-    	newnode.firstChild      = null;
-
-        // invalidate cache for children NodeList
-        newnode.nodeListIndex = -1;
-        newnode.nodeListLength = -1;
+        newnode.children = null;
+        newnode.length = 0;
 
         // Then, if deep, clone the kids too.
     	if (deep) {
-            for (Node child = firstChild;
-                 child != null;
-                 child = child.getNextSibling()) {
-                newnode.appendChild(child.cloneNode(true));
+            for (int i = 0; i < length; i++) {
+                newnode.appendChild(children[i].cloneNode(true));
             }
         }
 
@@ -199,9 +230,9 @@
         if (needsSyncChildren()) {
             synchronizeChildren();
         }
-	for (Node child = firstChild;
-	     child != null; child = child.getNextSibling()) {
-	    ((NodeImpl) child).setOwnerDocument(doc);
+        ownerDocument = doc;
+	for (int i = 0; i < length; i++) {
+	    children[i].setOwnerDocument(doc);
 	}
         ownerDocument = doc;
     }
@@ -214,7 +245,7 @@
         if (needsSyncChildren()) {
             synchronizeChildren();
         }
-        return firstChild != null;
+        return length > 0;
     }
 
     /**
@@ -246,7 +277,9 @@
         if (needsSyncChildren()) {
             synchronizeChildren();
         }
-    	return firstChild;
+        if (length == 0)
+            return null;
+    	return children[0];
 
     }   // getFirstChild():Node
 
@@ -256,20 +289,16 @@
         if (needsSyncChildren()) {
             synchronizeChildren();
         }
-        return lastChild();
+	if (length == 0)
+	    return null;
+	return children[length - 1];
 
     } // getLastChild():Node
 
     final ChildNode lastChild() {
-        // last child is stored as the previous sibling of first child
-        return firstChild != null ? firstChild.previousSibling : null;
-    }
-
-    final void lastChild(ChildNode node) {
-        // store lastChild as previous sibling of first child
-        if (firstChild != null) {
-            firstChild.previousSibling = node;
-        }
+	if (length == 0)
+	    return null;
+	return children[length - 1];
     }
 
     /**
@@ -367,11 +396,9 @@
 
             // No need to check kids for right-document; if they weren't,
             // they wouldn't be kids of that DocFrag.
-            for (Node kid = newChild.getFirstChild(); // Prescan
-                 kid != null;
-                 kid = kid.getNextSibling()) {
-
-                if (errorChecking && !ownerDocument.isKidOK(this, kid)) {
+            for (int i = 0; i < length; i++) { // Prescan
+                if (errorChecking &&
+                    !ownerDocument.isKidOK(this, children[i])) {
                     throw new DOMExceptionImpl(
                                            DOMException.HIERARCHY_REQUEST_ERR, 
                                            "DOM006 Hierarchy request error");
@@ -413,66 +440,53 @@
                 oldparent.removeChild(newInternal);
             }
 
-            // Convert to internal type, to avoid repeated casting
-            ChildNode refInternal = (ChildNode)refChild;
+            if (refChild == null) { // append
 
-            // Attach up
-            newInternal.ownerNode = this;
-            newInternal.isOwned(true);
+                // this is the only place this vector needs allocating,
+                // though it may also need to be grown in insertBefore.
+                // most elements have very few children
+                if (children == null)
+                    children = new ChildNode [3];
+                else if (children.length == length) {
+                    ChildNode temp [] = new ChildNode [length * 2];
+                    System.arraycopy(children, 0, temp, 0, length);
+                    children = temp;
+                }
 
-            // Attach before and after
-            // Note: firstChild.previousSibling == lastChild!!
-            if (firstChild == null) {
-                // this our first and only child
-                firstChild = newInternal;
-                newInternal.isFirstChild(true);
-                newInternal.previousSibling = newInternal;
+                // set parent
+                newInternal.ownerNode = this;
+                newInternal.isOwned(true);
+                newInternal.parentIndex = length;
+
+                children [length++] = newInternal;
+
             } else {
-                if (refInternal == null) {
-                    // this is an append
-                    ChildNode lastChild = firstChild.previousSibling;
-                    lastChild.nextSibling = newInternal;
-                    newInternal.previousSibling = lastChild;
-                    firstChild.previousSibling = newInternal;
-                } else {
-                    // this is an insert
-                    if (refChild == firstChild) {
-                        // at the head of the list
-                        firstChild.isFirstChild(false);
-                        newInternal.nextSibling = firstChild;
-                        newInternal.previousSibling =
-                            firstChild.previousSibling;
-                        firstChild.previousSibling = newInternal;
-                        firstChild = newInternal;
-                        newInternal.isFirstChild(true);
-                    } else {
-                        // somewhere in the middle
-                        ChildNode prev = refInternal.previousSibling;
-                        newInternal.nextSibling = refInternal;
-                        prev.nextSibling = newInternal;
-                        refInternal.previousSibling = newInternal;
-                        newInternal.previousSibling = prev;
-                    }
+
+                // grow array if needed
+                if (children.length == length) {
+                    ChildNode temp [] = new ChildNode [length * 2];
+                    System.arraycopy(children, 0, temp, 0, length);
+                    children = temp;
+                }
+
+                for (int i = 0; i < length; i++) {
+                    if (children [i] != refChild)
+                        continue;
+
+                    // set parent
+                    newInternal.ownerNode = this;
+                    newInternal.isOwned(true);
+                    newInternal.parentIndex = i;
+
+                    System.arraycopy(children, i, children, i + 1, length - i);
+                    children [i] = newInternal;
+                    length++;
+                    break;
                 }
             }
 
             changed();
 
-            // update cached length if we have any
-            if (nodeListLength != -1) {
-                nodeListLength++;
-            }
-            if (nodeListIndex != -1) {
-                // if we happen to insert just before the cached node, update
-                // the cache to the new node to match the cached index
-                if (nodeListNode == refInternal) {
-                    nodeListNode = newInternal;
-                } else {
-                    // otherwise just invalidate the cache
-                    nodeListIndex = -1;
-                }
-            }
-
             if(MUTATIONEVENTS && ownerDocument.mutationEvents)
             {
                 // MUTATION POST-EVENTS:
@@ -642,50 +656,24 @@
             }
         } // End mutation preprocessing
 
-        // update cached length if we have any
-        if (nodeListLength != -1) {
-            nodeListLength--;
-        }
-        if (nodeListIndex != -1) {
-            // if the removed node is the cached node
-            // move the cache to its (soon former) previous sibling
-            if (nodeListNode == oldInternal) {
-                nodeListIndex--;
-                nodeListNode = oldInternal.previousSibling();
-            } else {
-                // otherwise just invalidate the cache
-                nodeListIndex = -1;
+        // Patch tree past oldChild
+	for (int i = 0; i < length; i++) {
+	    if (children [i] != oldInternal)
+		continue;
+	    if ((i + 1) != length) {
+		System.arraycopy (children, i + 1, children, i,
+                                  (length - 1) - i);
             }
-        }
+	    length--;
+	    children[length] = null;
 
-        // Patch linked list around oldChild
-        // Note: lastChild == firstChild.previousSibling
-        if (oldInternal == firstChild) {
-            // removing first child
-            oldInternal.isFirstChild(false);
-            firstChild = oldInternal.nextSibling;
-            if (firstChild != null) {
-                firstChild.isFirstChild(true);
-                firstChild.previousSibling = oldInternal.previousSibling;
-            }
-        } else {
-            ChildNode prev = oldInternal.previousSibling;
-            ChildNode next = oldInternal.nextSibling;
-            prev.nextSibling = next;
-            if (next == null) {
-                // removing last child
-                firstChild.previousSibling = prev;
-            } else {
-                // removing some other child in the middle
-                next.previousSibling = prev;
-            }
-        }
+            break;
+	}
 
         // Remove oldInternal's references to tree
         oldInternal.ownerNode       = ownerDocument;
         oldInternal.isOwned(false);
-        oldInternal.nextSibling     = null;
-        oldInternal.previousSibling = null;
+        oldInternal.parentIndex = -1;
 
         changed();
 
@@ -765,24 +753,7 @@
      * @return int
      */
     public int getLength() {
-
-        if (nodeListLength == -1) { // is the cached length invalid ?
-            ChildNode node;
-            // start from the cached node if we have one
-            if (nodeListIndex != -1 && nodeListNode != null) {
-                nodeListLength = nodeListIndex;
-                node = nodeListNode;
-            } else {
-                node = firstChild;
-                nodeListLength = 0;
-            }
-            for (; node != null; node = node.nextSibling) {
-                nodeListLength++;
-            }
-        }
-
-        return nodeListLength;
-
+        return length;
     } // getLength():int
 
     /**
@@ -792,32 +763,13 @@
      * @param Index int
      */
     public Node item(int index) {
-        // short way
-        if (nodeListIndex != -1 && nodeListNode != null) {
-            if (nodeListIndex < index) {
-                while (nodeListIndex < index && nodeListNode != null) {
-                    nodeListIndex++;
-                    nodeListNode = nodeListNode.nextSibling;
-                }
-            }
-            else if (nodeListIndex > index) {
-                while (nodeListIndex > index && nodeListNode != null) {
-                    nodeListIndex--;
-                    nodeListNode = nodeListNode.previousSibling();
-                }
-            }
-            return nodeListNode;
-        }
-
-        // long way
-        nodeListNode = firstChild;
-        for (nodeListIndex = 0; 
-             nodeListIndex < index && nodeListNode != null; 
-             nodeListIndex++) {
-            nodeListNode = nodeListNode.nextSibling;
-        }
-        return nodeListNode;
-
+	if (length == 0 || index >= length)
+	    return null;
+	try {
+	    return children[index];
+	} catch (ArrayIndexOutOfBoundsException e) {
+	    return null;
+	}
     } // item(int):Node
 
     //
@@ -832,8 +784,8 @@
     public void normalize() {
 
         Node kid;
-        for (kid = firstChild; kid != null; kid = kid.getNextSibling()) {
-            kid.normalize();
+        for (int i = 0; i < length; i++) {
+            children[i].normalize();
         }
     }
 
@@ -860,11 +812,9 @@
             }
 
             // Recursively set kids
-            for (ChildNode mykid = firstChild;
-                 mykid != null;
-                 mykid = mykid.nextSibling) {
-                if(!(mykid instanceof EntityReference)) {
-                    mykid.setReadOnly(readOnly,true);
+            for (int i = 0; i < length; i++) {
+                if(!(children[i] instanceof EntityReference)) {
+                    children[i].setReadOnly(readOnly,true);
                 }
             }
         }
@@ -903,28 +853,29 @@
         // create children and link them as siblings
         DeferredDocumentImpl ownerDocument =
             (DeferredDocumentImpl)this.ownerDocument;
-        ChildNode first = null;
-        ChildNode last = null;
-        for (int index = ownerDocument.getLastChild(nodeIndex);
-             index != -1;
-             index = ownerDocument.getPrevSibling(index)) {
 
-            ChildNode node = (ChildNode)ownerDocument.getNodeObject(index);
-            if (last == null) {
-                last = node;
-            }
-            else {
-                first.previousSibling = node;
-            }
-            node.ownerNode = this;
-            node.isOwned(true);
-            node.nextSibling = first;
-            first = node;
+        // first count them
+        for (int index = ownerDocument.getLastChild(nodeIndex, false);
+             index != -1;
+             index = ownerDocument.getPrevSibling(index, false)) {
+            length++;
         }
-        if (last != null) {
-            firstChild = first;
-            first.isFirstChild(true);
-            lastChild(last);
+
+        // then fluff them up
+        if (length > 0) {
+            children = new ChildNode [length];
+
+            int count = length;
+            for (int index = ownerDocument.getLastChild(nodeIndex);
+                 index != -1;
+                 index = ownerDocument.getPrevSibling(index)) {
+
+                ChildNode node = (ChildNode)ownerDocument.getNodeObject(index);
+                node.ownerNode = this;
+                node.isOwned(true);
+                node.parentIndex = --count;
+                children[count] = node;
+            }
         }
 
         // set mutation events flag back to its original value
@@ -960,10 +911,6 @@
 
         needsSyncChildren(false);
 
-        // initialize transients
-        nodeListLength = -1;
-        nodeListIndex = -1;
-
     } // readObject(ObjectInputStream)
 
 } // class ParentNode
diff --git a/src/org/apache/xerces/dom/TextImpl.java b/src/org/apache/xerces/dom/TextImpl.java
index 82e803a..be31eaa 100644
--- a/src/org/apache/xerces/dom/TextImpl.java
+++ b/src/org/apache/xerces/dom/TextImpl.java
@@ -182,7 +182,7 @@
         // insert new text node
         Node parentNode = getParentNode();
     	if (parentNode != null) {
-    		parentNode.insertBefore(newText, nextSibling);
+            parentNode.insertBefore(newText, getNextSibling());
         }
 
     	return newText;
diff --git a/src/org/apache/xerces/parsers/DOMParser.java b/src/org/apache/xerces/parsers/DOMParser.java
index 3be40f6..d4f5c70 100644
--- a/src/org/apache/xerces/parsers/DOMParser.java
+++ b/src/org/apache/xerces/parsers/DOMParser.java
@@ -1142,6 +1142,9 @@
         else {
             fCurrentElementNode = fCurrentElementNode.getParentNode();
             fWithinElement = false;
+            if (fDocumentImpl != null) {
+                ((NodeImpl)fCurrentElementNode).reduceWaste();
+            }
         }
 
     } // endElement(QName)