Ah, okay, I was merely under the impression that List had been implemented as a linked list. (I already know the difference between fixed-length array, dynamic-length array, and linked list, but your explanation will be helpful to anyone who isn't.)
On nerd-level discussion of data structures (language agnostic now), another good option for a dynamic contiguous collection is a circular buffer, which is designed such that the head and tail "float". It's a bit hard to explain — basically, you don't require head to be at element 0, but implement logic for "wrapping around" from the last element to the first, as long as you haven't yet reached tail.
It makes for a time complexity of O(n/2) on insertion/deletion without reallocation, instead of the O(n) of a typical contiguous collection. Even better, head and tail operations are always Θ(1). While this is still a bit higher than the consistent O(1) of a linked list, you don't have the cache misses. It's also better-suited for random access.
No idea how you'd effectively implement this in Python, however. I always use pointer arithmetic to pull it off.
Ah, okay, I was merely under the impression that
Listhad been implemented as a linked list. (I already know the difference between fixed-length array, dynamic-length array, and linked list, but your explanation will be helpful to anyone who isn't.)I also was unaware how
listis implemented in Python. So we both learned something :)On nerd-level discussion of data structures (language agnostic now), another good option for a dynamic contiguous collection is a circular buffer, which is designed such that the head and tail "float". It's a bit hard to explain — basically, you don't require head to be at element 0, but implement logic for "wrapping around" from the last element to the first, as long as you haven't yet reached tail.
It makes for a time complexity of O(n/2) on insertion/deletion without reallocation, instead of the O(n) of a typical contiguous collection. Even better, head and tail operations are always Θ(1). While this is still a bit higher than the consistent O(1) of a linked list, you don't have the cache misses. It's also better-suited for random access.
No idea how you'd effectively implement this in Python, however. I always use pointer arithmetic to pull it off.
I'm trying to imagine what this looks like implemented:
Not far off. ;)