[issue42575] Suggest to add an LinkedList data structure to python

[Terry J. Reedy]

Terry J. Reedy <tjreedy at udel.edu> added the comment:

The opening claim (no linked list structures in Python) is flawed. Abstractly, a linked list is a binary tree with right items of nodes restricted to being a linked list or None.  If the left items are restricted to being non-lists values, then the linked list implements, in somewhat peculiar way, a sequence of non-list values.

Python's tuples and lists can make general trees with unrestricted numbers and types of items.  Add the linked-list restriction as to number and types and one has, in Python already, a frozen or mutable linked list.  Alternatively, one can make linked lists in Python with a class with two named attributes with whichever linked-list restrictions.  Finally, one can view a deque as a doubly-linked list, mutable at each end.  Internally, it is a doubly-linked list of blocks of values.  The block size is tuned to the cache size of modern processors.

Lisp's linked lists are a solution to incrementally building immutable structures that can be processed by function-call recursion.  The key idea is that a sequence can be inductively defined as the first item followed by the rest.  Python is not restricted to either immutable structures or recursion, but its iteration protocol implements that key idea.  it = iter(iterable) represents a non-iterator iterable by an iterator (and an iterator by itself).  next(it) splits the sequence represented by 'it' into first and rest, mutates 'it' to represent the rest, and returns the first.  (The proposed class is missing a ListIterator class and a .__iter__ method to return one.)
---

I am sure that adding linked lists has been proposed and rejected before.  I know that b-trees have been, and likely others specialized structures.  Guido decided long ago that such things should generally be left to what is now https://pypi.org. The major exceptional addition was deque, which filled the hole of being efficiently mutated at each end.  So I think that this issue should be closed.

Adding a new structure is too 'big' a change for a bpo issue.  Discussion on python-ideas list and a PEP would be needed.  But I think the chance of success is nil.

----------
components: +Interpreter Core -C API
nosy: +terry.reedy

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue42575>
_______________________________________