classification
Title: Suggest to add an LinkedList data structure to python
Type: enhancement Stage: resolved
Components: Interpreter Core Versions: Python 3.10
process
Status: closed Resolution: rejected
Dependencies: Superseder:
Assigned To: Nosy List: Dennis Sweeney, SamUnimelb, rhettinger, steven.daprano, terry.reedy
Priority: normal Keywords:

Created on 2020-12-05 06:35 by SamUnimelb, last changed 2020-12-12 02:04 by rhettinger. This issue is now closed.

Files
File name Uploaded Description Edit
LinkedList.py SamUnimelb, 2020-12-05 06:35 Implementation of a linked list data structure using python
Messages (5)
msg382557 - (view) Author: Sam Yan (SamUnimelb) * Date: 2020-12-05 06:35
There has been no LinkedList data structure for Python. Therefore suggest adding a LinkedList data structure.
msg382559 - (view) Author: Steven D'Aprano (steven.daprano) * (Python committer) Date: 2020-12-05 08:11
The class you have provided is awkward to use, random access is inefficient, it is not compatible with lists or offer a sequence API, it's not subscriptable or iterable, the API exposes an unnecessary "Proxy" class, and the API is more like what I would expect from Java code than Python code.

But even if every one of those problems was fixed, there is still the question, why would somebody choose this LinkedList instead of the fast, efficient built-in list? What advantages does this have?
msg382582 - (view) Author: Dennis Sweeney (Dennis Sweeney) * (Python triager) Date: 2020-12-05 19:58
I'll add that for 98% of the use cases of a linked list (where you just want fast access at the ends), you can use a `collections.deque` instead, and it will be faster (fewer dereferences) and more memory-efficient (fewer pointers to store).

In the remaining 2% where a linked list is genuinely better (say in CPython's internal garbage collector), you're in a situation where you are already holding a node and you want to delete it or insert around it in constant time. (If you need to do a linear scan before deleting things, list comprehensions will already do what you need). In such situations, the construction is highly specialized for the application, so it's difficult to generalize the construction to an abstract data structure -- in particular, the "data" may need to access the next/previous "data" directly. It's also not inaccessibly hard to re-do every time you need it.
msg382896 - (view) Author: Terry J. Reedy (terry.reedy) * (Python committer) Date: 2020-12-12 01:39
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.
msg382899 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2020-12-12 02:04
> So I think that this issue should be closed.

I agree with the respondents.  Marking this one as closed.
History
Date User Action Args
2020-12-12 02:04:16rhettingersetstatus: open -> closed

nosy: + rhettinger
messages: + msg382899

resolution: rejected
stage: resolved
2020-12-12 01:39:53terry.reedysetnosy: + terry.reedy
messages: + msg382896
components: + Interpreter Core, - C API
2020-12-05 19:58:24Dennis Sweeneysetnosy: + Dennis Sweeney
messages: + msg382582
2020-12-05 08:11:36steven.dapranosetnosy: + steven.daprano
messages: + msg382559
2020-12-05 06:35:39SamUnimelbcreate