PEP Request: Advanced Data Structures

[Chris Angelico]

On Sun, Jul 17, 2016 at 10:54 AM,  <cs at zip.com.au> wrote:
> Well, in a larger context you can keep a reference to an element deep in the
> list, and insert a new element in O(1) time at that point.
>

I'd like to know how many elements your list needs before that
actually becomes faster than CPython's heavily-optimized C-implemented
list structure. And if someone's proposing a new core data type, I
very much doubt that'll fly - and at the C level, wouldn't tracing the
links cost massively more than the occasional insertion too? I'm not
sure O(1) is of value at any size, if the costs of all your other
operations go up.

ChrisA