On Wed, Apr 29, 2020 at 9:01 PM Ram Rachum wrote:

Is there a strategic decision to limit deque to certain operations of doubly-linked lists and not others? That would make sense. Is that decision written somewhere with the rationale behind it? That would be interesting to read.

"""Deques are a generalization of stacks and queues (the name is pronounced “deck” and is short for “double-ended queue”). Deques support thread-safe, memory efficient appends and pops from either side of the deque with approximately the same O(1) performance in either direction.""" I'm not seeing any evidence that this is a doubly-linked list. It might happen to be implemented using one in current versions of CPython, but that's not mandated anywhere. Is there a particular reason to mandate this for all Pythons for all time? As Paul says, you can always implement your own doubly linked list. ChrisA

Hello, On Wed, 29 Apr 2020 13:58:15 +0300 Ram Rachum wrote:

On Wed, Apr 29, 2020 at 1:54 PM Paul Sokolovsky wrote:

...

If you want a different data structure, [...] implement such a data structure

And if I wanted an answer like "it's the way that it is because it's the way that it is" I wouldn't be posting on python-ideas.

Is there a strategic decision to limit deque to certain operations of doubly-linked lists and not others?

Deque is not doubly-linked list, they are completely different data structures. Even if a particular Python implementation uses doubly-linked list as an internal implementation strategy. There're other Python implementations which realize deque in other ways, which guarantee performance only for operations defined for deque and not for any other data structure. (E.g., an obvious implementation is an array with head/tail pointers).

That would make sense. Is that decision written somewhere with the rationale behind it? That would be interesting to read.

-- Best regards, Paul mailto:pmiscml@gmail.com

On 29 Apr 2020, at 12:36, remi.lapeyre@henki.fr wrote:

Also, removing an element from a doubly-linked list is not a O(1) operation, it's O(n). It's O(1) once you have a pointer to the element but you have to iterate over the list to get it and that would take O(n) operations, so making deque a doubly-linked list would not be faster anyway.

In the cases where a DLL is the reasonable design choice remove is O(1) in my experience. The reason is that you have the element in your hand by other means then scanning the DLL. This was a heavily used pattern when I worked on DEC VMS device drivers. Async I/O requests could be cancelled and removed from the list of outstanding I/O for a device in O(1). Indeed the VAX had instructions to implement this pattern in hardware. Barry

Thanks everybody for your answers, and especially Ricky for finding this note. On Wed, Apr 29, 2020 at 2:20 PM Ricky Teachey wrote:

I was playing around with deque today, and there were a couple of

...

operations I wanted to do, that can't really be done efficiently with deque because of its implementation.

...

What do you think about adding [O(1) insert and remove] this to `deque`?

_collectionsmodule.c has this note, so it sounds like this is intended to be a possibility if there is enough interest:

/* insert(), remove(), and delitem() are implemented in terms of rotate()

...

for simplicity and reasonable performance near the end points. If for some reason these methods become popular, it is not hard to re-implement this using direct data movement (similar to the code used in list slice assignments) and achieve a performance boost (by moving each pointer only once instead of twice). */

https://github.com/python/cpython/blob/d16a1520c2b22c3cbde7547937ba283db3e88...

--- Ricky.

"I've never met a Kentucky man who wasn't either thinking about going home or actually going home." - Happy Chandler

On Apr 29, 2020, at 08:33, Christopher Barker wrote:

I've wondered about Linked Lists for a while, but while there are many versions on PyPi, I can't find one that seems to be mature and maintained. Which seems to indicate that there isn't much demand for them.

I think there’s lots of demand for them, but there are so many different variants that can’t substitute for each other (try taking any nontrivial sample code using Haskell’s single-linked, no-handle, immutable tail-sharing list and rewriting it with C++’s doubly-linked handled mutable list, or vice-versa), and most of the key operations fit so poorly with Python’s sequence/iterable API, and they’re all so easy to build, that people just build the one they need whenever they need it. I do have a few different linked lists in my toolbox that have come up often enough that I stashed them (an immutable cons, a handled double-linked list, a cffi wrapper for a common style of C internally-linked lists, probably others), but half the time I reach for one I have to modify it anyway, so I haven’t bothered to turn them into a package I just import and use. And, while I did add the whole (Mutable)Sequence API to each one (because it’s convenient for debugging and REPL exploration to be able to list(xs), or to get a repr that’s written in terms of a from_iter classmethod so I can eval it back, etc.), I usually don’t use that API for anything but debugging. When you’re dealing with linked lists, you usually need to deal with the nodes directly. For example, one big reason to use linked lists is constant-time splicing, but you can’t splice in constant time if all you have is the head/handle and/or an opaque iterator that only knows how to go forward; you need the node before the splice point (or, for doubly-linked, after is fine too). Another reason to use (Lisp/Haskell-style) linked lists is that they automatically release nodes as you iterate unless you keep a reference to the head, but that’s clumsy to do with Python-style APIs. And so on.

On Apr 29, 2020, at 12:03, Christopher Barker wrote:

Isn't much demand for a *generic* linked list. It would probably be a good recipe though -- so users could have a starting point for their custom version.

I think what would be really handy would be a HOWTO on linked lists that showed the different options and tradeoffs and how to implement and use at least a few different ones, and showed why they’re useful with examples. (And also showed why the Sequence/Iterable API can be helpful but also why it’s not sufficient.) Then the collections module (and the tutorial?) could both just have a sentence saying “Python doesn’t have a linked list type because there are so many useful kinds of linked lists and they’re all easy to build but very different—see the Linked Lists HOWTO for details.” But if I wrote it, it would probably be 4x as long as any novice would want to read. (I think I wrote some blog posts on linked lists in Python years ago, and ended up building a Haskell-style lazy list out of a trigger function and then showing how to do Fibonacci numbers by recursively zipping it, or something crazy like that.) In the old days we could probably just post three different simple recipes on ActiveState and link to them from the docs and let people build on the examples there, rather than try to write it all up-front and fit it into the Python docs style, but that doesn’t work so well anymore.

On Thu, Apr 30, 2020 at 5:56 AM Andrew Barnert via Python-ideas wrote:

On Apr 29, 2020, at 12:03, Christopher Barker wrote:

...

Isn't much demand for a *generic* linked list. It would probably be a good recipe though -- so users could have a starting point for their custom version.

I think what would be really handy would be a HOWTO on linked lists that showed the different options and tradeoffs and how to implement and use at least a few different ones, and showed why they’re useful with examples. (And also showed why the Sequence/Iterable API can be helpful but also why it’s not sufficient.)

Then the collections module (and the tutorial?) could both just have a sentence saying “Python doesn’t have a linked list type because there are so many useful kinds of linked lists and they’re all easy to build but very different—see the Linked Lists HOWTO for details.”

But if I wrote it, it would probably be 4x as long as any novice would want to read.

Summary, for novices: "Just use a built-in list and don't worry about it. Performance of built-in types is usually 'good enough' even if it isn't perfect." It's only the experts who need this sort of thing, so I'm not too bothered if novices can't implement LLs efficiently in Python. ChrisA

On 30/04/20 3:32 am, Christopher Barker wrote:

I've wondered about Linked Lists for a while, but while there are many versions on PyPi, I can't find one that seems to be mature and maintained. Which seems to indicate that there isn't much demand for them.

I think this is probably because a linked list is more of a design pattern than a concrete data structure. In situations where you want a linked list in particular, rather than just a container that supports certain operations, you really need the references implementing the links to be embedded in the objects being kept in the list. This makes it difficult to abstract, especially if your objects need to be part of more than one list at a time. -- Greg