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.
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.
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.
