Eric White's Blog

One trick is to never, ever write queries or updates which retrieve or insert siblings before some particular element. In other words, avoid XNode.AddBeforeSelf(), XNode.ElementsBeforeSelf(), XNode.PreviousNode. This is because XNodes in an XContainer form a singly linked list, so only forward traversal is efficient, while backward requires restarting from the beginning of the container.

Because of this, IsBefore() and IsAfter() are not particularly efficient, either...

Interestingly enough, XPathDocument does not have this problem.

I understand the reasoning, but it's a real pity that MSDN docs don't say a word on this, and have outright deceiving samples (if you look the one for PreviousNode, it uses it in a while-loop to traverse nodes in reverse document order - that's O(n^2)!).

I've created a ticket for that at VS Connect:

https://connect.microsoft.com/VisualStudio/feedback/ViewFeedback.aspx?FeedbackID=355102

Eric White on Linq and Open XML. Eric White has been posting some great code samples lately, including

> Actually, I can't remember, but I vaguely recollect that the fact that nodes were forward only linked was an implementation detail that could in theory change in the future, so should not be put in the docs.

You might not want to put the exact algorithmic complexity in the docs, but I don't see how it would hurt to write something like "the complexity of this operation is not guaranteed to be O(1)" in Remarks section.

> But what I can tell you is that I wasn't focused on node traversal as a primary scenario.  Instead, I wanted to teach people about using queries, and the functional approach.  There are a couple of scenarios where a developer will want to do node traversal, but in those cases, the developer will be aware that nodes are forward linked.

XLINQ is indeed mostly about queries, but this particular example I linked to was certainly about node traversal.

> I'm not sure what a good example would be for previous node.  Suggestions?

Ironically enough, reverse traversal is perhaps the only thing it's actually useful for ... so no other ideas here, sorry.

In reality, as it stands, any use of PreviousNode in a loop (even an implicit one, such as a LINQ query) is suspect.

Great to hear; I'm looking forward to seeing that ticket closed as "Fixed" at Connect ;)

By the way, I sort of missed this:

> Well, that would be my fault, since I wrote the LINQ to XML documentation.

And just wanted to say that, on the whole, you did a great job there. It is one of the more interesting section of the Framework docs, with all the examples on how to do things (and how they can break if done wrong).

And of course the topics on pure/functional vs mutable/imperative approaches - "Functional Programming vs. Imperative Programming", "Refactoring Into Pure Functions", and "Introduction to Pure Functional Transformations" - I can only hope more people would read those. Though what makes me wonder is why the first two of those are under LINQ to XML, as they are really just as applicable to LINQ and C# in general; IMO, they should have been right there in the "Introduction to C#" sections (and thus our mission of world domination shall be complete, my brethren in lambda calculus... muhahhahaa!) ;)