Adding a LinkedList type to the Standard Library

At this time I don't think linked lists belong in the Standard Library. They are almost always the wrong data structure to use in practice, so having them prominently available would probably be a bad idea. However, they do have two properties that I believe can make them very useful in niche use cases: index stability and "constant-time" insertions/removals. If some of these use cases turn out to be more important than I thought, then maybe I could change my mind, though!

By index stability, I expect that an index pointing to an element in a linked list will remain valid (pointing to the same item) until the item is removed, even if other items are added or removed from the list, before or after the indexed item.

In the cases I've come across so far, it was always the case that index stability could be substituted by content/id based lookups in a dictionary-like data structure. For example, keys in a Dictionary/OrderedDictionary behave somewhat like stable indices. But I can easily believe that it isn't always practical / convenient to do this.

Index stability comes easy* for linked lists, but it is tricky to implement in other kinds of data structures.

* (Nothing is ever really easy. The straightforward implementation of linked lists results in an unsatisfying, slow Comparable implementation; it's unclear to me if this can be fixed.)

The other major benefit of linked lists is "constant-time" insertions/removals at a particular index. This too can often be well enough approximated (e.g. by using a tree-based data structure), although this usually breaks index stability.

These two features can sometimes be important, so I wouldn't want to entirely dismiss the idea of implementing a linked list. But the use cases that require these features seem to be so rare that I don't expect we'd ever want to add a linked list type to the Standard Library -- and certainly not before adding some more practical data structures that can often replace them (such simple deques or a B-tree based list construct).


The best place to develop a linked list implementation is the same as with other data structures: in a package! Once the kinks have been hammered out, and folks have gained years of production experience using it, then it may be worth considering adopting it in the Standard Library -- it will certainly be easier to argue for the addition if we can be reasonably confident that the implementation is the right one.

(Generic data structure implementations usually need to be inlinable to achieve good performance. This (along with the stdlib's ABI stability requirements) usually makes it difficult to change/improve data structure implementations once they have shipped in a Swift release. We need to get them right the first time, because we usually won't be able to change the memory layout or overhaul the API later. This increases the stakes considerably -- there are few things sadder than finding out too late that we shipped something that is "obviously" suboptimal, but not being able to fix it.)

Therefore, unless something forces our hands*, I would strongly oppose adding a new general-purpose data structure to the Standard Library unless its implementation originates from a long standing, universally beloved package that has seen of years of widespread production use, and there is already clear consensus about the new type's (source and binary) interfaces.

* (Such as the new data structure being intimately tied to a high-profile language feature under development.)

For example, I think Swift Collections is a great place for developing new data structures that might end up in/near the Standard Library. (Landing a new data structure there still isn't easy, though -- it takes far less work than landing something in the stdlib, but the bar is still very, very high. For reference, we have several new data structures nearing completion, but the package is yet to release its first feature update.)

The quickest way to ship a data structure is to release your own package, like you already did. :+1:

(Tip: a general purpose linked list implementation needs to support an arbitrary number of items. E.g., destroying a long linked list must not overflow the stack.)

9 Likes