DEV Community

loading...

Discussion on: What are Linked Lists and How Do I Make One in Python?

erikhei profile image
Whiteboarding with Erik Author

I also was unaware how list is implemented in Python. So we both learned something :)

Thread Thread
codemouse92 profile image
Jason C. McDonald • Edited

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.

Thread Thread
erikhei profile image
Whiteboarding with Erik Author

I'm trying to imagine what this looks like implemented:

Thread Thread
codemouse92 profile image
Jason C. McDonald

Not far off. ;)