I searched through Guido's Python History blog, because I was sure he'd written about this, but apparently that's not where he did so. So, this is based on a combination of reasoning (aka educated guessing) and memory (possibly faulty).
Let's start from the end: Without knowing why Guido didn't add linked lists in Python 0.x, do we at least know why the core devs haven't added them since then, even though they've added a bunch of other types from OrderedDict
to set
?
Yes, we do. The short version is: Nobody has asked for it, in over two decades. Almost of what's been added to builtins or the standard library over the years has been (a variation on) something that's proven to be useful and popular on PyPI or the ActiveState recipes. That's where OrderedDict
and defaultdict
came from, for example, and enum
and dataclass
(based on attrs
). There are popular libraries for a few other container types—various permutations of sorted dict/set, OrderedSet, trees and tries, etc., and both SortedContainers
and blist
have been proposed, but rejected, for inclusion in the stdlib.
But there are no popular linked list libraries, and that's why they're never going to be added.
So, that brings the question back a step: Why are there no popular linked list libraries?
First, "linked list" is not really one type, but a whole family of types—single vs. double-linked, node-as-list vs. handle-as-list, tail sharing or not, lazy (presumably via @property
-style triggers) or strict… as well as variations like circular lists. And each one of these is useful far less than the family as a whole, of course. And you can't share all that much between interfaces or implementations for them—an interface for dealing with Lisp-style cons
lists makes no sense at all for something like a C++ std::list
.
Second, all of the different variations are dead easy to build. The reason OrderedDict
made it into the language is that people were able to show that it's actually very tricky to get right. Sets are easy to get right, but impossible to space-optimize without borrowing behind-the-scenes implementation details out of dicts. Linked lists are easy to get right and to optimize. If you want one, any of the varieties, you build one in a few minutes, and you're done. (In fact, OrderedDict
uses one under the hood…)
Meanwhile, since Python 2.3, and especially since 3.0, the iterator protocol has become the central paradigm for everything. And there's a reason other languages are borrowing Python's generators—but in most of those languages, they don't provide the same benefits, because the whole language isn't built around them. Being able to forward-iterate any collection—including a "virtual" collection that doesn't even exist—already gives you most of the advantages of a lazy tail-sharing cons list without needing one. On the other hand, the main thing it's missing is convenient constant-time (mutating) splicing—but that one missing thing is actually pretty hard to fit into the iterator paradigm. (See itertools
for how you can do it—it's just tee
and chain
, after all—and for how clumsy it feels to do so.)
(Of course there are also advantages to a more complicated iteration protocol, like the one used by C++, or, even better, Swift. With bidirectional and mutable vs. immutable iteration, doubly-linked lists might be a lot more useful. But there's a tradeoff between power and simplicity there, and Python made its choice long ago.)
And, last, but definitely not least, linked lists, especially cons-style tail-sharing linked lists, are an inherently recursive data structure. The Python philosophy is to use recursion only when you have inherently recursive problems. And Guido believes there are very few of these, which is why Python doesn't do, e.g., tail recursion elimination. He didn't want map
and reduce
in his language, but once he figured out how to do them iteratively instead of recursively, he was willing to let them stay. And storing linear data is not an inherently recursive problem. Trees? Sure, they pretty much have to be recursive. But lists? No.