Hacker News Reader

Comment by mazokum | Hacker News Reader

I believe that collections.deque is implemented as a double linked list. I have used that data structure as a linked list a couple of times.

https://docs.python.org/3/library/collections.html#collectio...

View on HN

Curious why both of you need linked lists in Python? Are you doing a lot of list insertion operations or something & allocations are bringing it to a crawl?

I'm quite tickled by the idea that you need a linked list because your allocator is spending too much time - traversing a linked list.

I thought one of the advent of code challenges needed a linked list, but other than that, I have never needed one.

I was just surprised as I thought it was a basic structure, so it just seemed like there ought to be a `from collections import linkedlist` because python just feel like the kind of language where you just do that without even consulting the docs.

Yeah for sure. I think your intuition is almost right. Python does have a "batteries included" philosophy, but it's also not usually clear or documented what data structures something is using. Like I presume that Python's sets are syntactic sugar over dictionaries where the values are None, but when I skimmed the docs just now I didn't find any mention of the implementation details.

Python doesn't want you thinking in terms of data structures, just in terms of functionality. Which I think is unfortunate and limiting.

Correct (actually a linked list of blocks[1]). It supports insertion and removal from both ends in O(1), which is very useful. However, it does not support insertion and removal from the middle (via an iterator) in O(1), so it's not a complete replacement for doubly-linked lists.

[1]: https://github.com/python/cpython/blob/a4ac14faa5c2be433738d...

Reply on news.ycombinator.com