5 ms·

The other day I was surprised to find that Python doesn’t come with linked lists and apparently there isn’t anything like an agreed upon `pip install linked-lis

The other day I was surprised to find that Python doesn’t come with linked lists and apparently there isn’t anything like an agreed upon `pip install linked-list` solution.

mazokum 4y ago
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#collections.deque https://docs.python.org/3/library/collections.html#collectio...
- maxbond 4y ago
  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.
  - wodenokoto 4y ago
    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.
    - maxbond 4y ago
      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.
- hddqsb 4y ago
  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/a4ac14faa5c2be433738dfbbed14b0eaa1a2399e/Modules/_collectionsmodule.c#L31 https://github.com/python/cpython/blob/a4ac14faa5c2be433738d...
pradn 4y ago
Linked lists are popular because they are useful in teaching basic data structures and complexity analysis. They can be compared to array lists. But in real life the extra cost of allocating a node is way higher than simply copying over a block of memory, for most realistic sized workloads, which are small.

The other day I was surprised to find that Python doesn’t come with linked lists and apparently there isn’t anything like an agreed upon `pip install linked-list` solution.

mazokum 4y ago

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#collections.deque https://docs.python.org/3/library/collections.html#collectio...

maxbond 4y ago
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.
- wodenokoto 4y ago
  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.
  - maxbond 4y ago
    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.
hddqsb 4y ago
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/a4ac14faa5c2be433738dfbbed14b0eaa1a2399e/Modules/_collectionsmodule.c#L31 https://github.com/python/cpython/blob/a4ac14faa5c2be433738d...

pradn 4y ago

Linked lists are popular because they are useful in teaching basic data structures and complexity analysis. They can be compared to array lists. But in real life the extra cost of allocating a node is way higher than simply copying over a block of memory, for most realistic sized workloads, which are small.