OrderedDict  was added with Python 3.1, and there's an equivalent (pure Python) class provided in the docs for backwards compatibility. Just in case the author reads this, it would make the code nicer to implement the appropriate "magic" method names that make it act like built-in containers .
The method and variable names here mostly reuse the names from the original skip lists paper, although in a real generic implementation, reusing the mapping protocol would be a nice touch. I posted this more due to the ridiculous simplicity of implementation: skip lists themselves are far more worthy of note than my horrid example code.
* The node pointer list is reused for the node structure to save memory, otherwise a minimum of 72 bytes is wasted per node on CPython, in addition to malloc slack for 2 allocations (the list object itself, and the array of pointers). As it stands, CPython burns about 100 bytes per record, so 'clean' code here would potentially double the memory requirements in addition to added runtime cost.
* Numeric, rather than symbolic indexing wins 5k lookups/second on CPython. It's debatable whether using speed hacks like "search(key, IDX_PREV=IDX_PREV, IDX_NEXT=IDX_NEXT)" is uglier than the bare numbers themselves. Using accessor functions to pretty the code also costs quite a lot.
I recently read through the concurrent skip list map implementation in Java that is lockless. That code is definitely quite tricky, and the comments refer to three PhD thesis's one should read to understand how it works.
You raise an interesting topic, I got into Python around the 2.2 era almost entirely due to the "cleanliness" factor, but features quickly began to appear that seemed redundant in some way, and the general popularity of the language meant its philosophy became increasingly dilute. Basically whatever "obviousness" the language had is eroded by varying degrees of pomp and ceremony, e.g. "idiomatic" use of crazy stuff like metaclasses, decorators everywhere, or nested list comprehensions containing perlish conditional expressions.
It seems healthier to look at Python less as some bastion of beauty and more a slightly prettier glue language, like a perl 2.0. From this angle it becomes an interesting macro language for combining chunks of C in interesting ways. You can write some awesomely fast, concise code with abuse of buffer(), itertools and functools.partial, but none of it looks particularly "Pythonic" or "beautiful". Nonetheless the resulting code is among the best in its class in terms of performance/size/maintainability compromise, yet the community at large would likely reject it as abhorrent.
I guess this code snippet is a good example of that.
The "public domain dedication" is the wrong way to make code available for anyone to do what they want with it. The problem is that under US copyright law, you and your heirs actually own that copyright, whether you want to or not. Declaring otherwise has no legal force. Which means that if you change your mind, or if your heirs feel differently than you do, people can potentially be sued for copyright violations on that code. Unlikely, but possible.
By contrast releasing your code under an extremely permissive license has legal force, and neither you nor your heirs can unrelease it. (Assuming, that is, that you own copyright to your own work. Sometimes people do not, and do not realize this...)
As Bernstein indicates, Lawrence Rosen argues the other side of this. There is binding precedent on the question in the 9th circuit. However that precedent is not necessarily binding on other courts, the statute does not provide for such a mechanism, and we've already seen statutes bring works back under copyright which had been out of copyright. The most famous example being It's a Wonderful Life. Therefore it is possible that other courts could decide differently, and it is possible that future copyright legislation or treaties could alter the legal status of works that have been abandoned to the public domain.
And this is just the situation in the USA. There are about 200 countries in the world, with different legal systems. Most have some type of copyright law, and that law roughly follows international treaties. I have confidence that in the countries with "reasonable" copyright legislation/jurisprudence, that copyright licenses have force. Given that even the US situation is not entirely settled, I have no confidence that a public domain declaration has force in other countries. Therefore caution would indicate that a simple permissive license is preferable to a public domain declaration.
Therefore yes, I would say that the chances of Damiel Bernstein being wrong on this are good enough that a simple permissive license is preferable to a public domain declaration.
See here, Article 18 is the only place that mentions public domain: http://www.wipo.int/treaties/en/ip/berne/trtdocs_wo001.html#...
Incidentally your Berne Convention argument is rather weak according to my reading of the actual text of the Berne Convention. (See http://www.wipo.int/treaties/en/ip/berne/trtdocs_wo001.html for the text.) Public domain is only referred to in article 18, and the only type of public domain referred to is due to expiration of the term for copyright. Section 7 indicates the minimum terms in question, and those terms are both long and do not contain anything indicating that they can be shortened by the author's wish.
Therefore the fact that public domain is mentioned in the Berne Convention does nothing to reassure me that countries which sign the Berne Convention will necessarily pay any attention to a public domain declaration.
They recognize that the public domain might not exist in all legal domains, so a licensed version is available, for a fee.
Others have decided to decline to use copyright protection. There's a list of such software at http://unlicense.org/ .
I wouldn't look to the Berne treaty for some statement of the international existence of copyright law. You need to look towards national laws instead. For example, the US recognizes the public domain, and a work of the United States government is automatically in the public domain in the US. (Though it might not be in the public domain elsewhere.)
So like any social movement, if enough people release software and disclaim copyright protection, then those jurisdictions which don't recognize the public domain might change. If no software ever takes the risk, then it will never change.
That doesn't mean the legal/IP system of Berne signatories has to allow putting things in the public domain before copyrights on it expire.
In fact, I know for certain that France does not allow it under any circumstance. And I believe (though without certainty) that this is the rule in all EU countries.
As long as there are people who the poster would like to see free to use the code who are American and subject to US Copyright Law, the issue has potential relevance.
Ditto for French users and French law since we've been informed that the declaration is useless in France.