Python Big O: the time complexities of different data structures in Python (www.pythonmorsels.com)

submitted 4 weeks ago by norambna@programming.dev to c/python@programming.dev

8 comments fedilink hide all child comments

via https://mastodon.social/@treyhunner/113367936771761302

you are viewing a single comment's thread
view the rest of the comments

[-] FizzyOrange@programming.dev 2 points 3 weeks ago

Standard ring buffers or circular buffers are implemented as continuous vectors, with a read and write pointer.

Rust's VecDeque is a ring buffer: https://doc.rust-lang.org/std/collections/struct.VecDeque.html

[-] eager_eagle@lemmy.world 0 points 3 weeks ago

Since VecDeque is a ring buffer, its elements are not necessarily contiguous in memory.

[-] FizzyOrange@programming.dev 2 points 3 weeks ago

No that's a subtly different thing. The storage is a contiguous vector, but because it is a ring buffer there must be one pair of adjacent elements that are not contiguous in memory. That's what that comment is saying.

But because it is only one discontinuity it doesn't affect algorithmic complexity, so it is still O(1) to access elements, unlike a linked list which is O(N).

If you google "circular buffer" there will be loads of diagrams that make it really obvious how it works.