Hacker News Reader

Comment by thomasahle | Hacker News Reader

This is known as a Circular Buffer https://en.m.wikipedia.org/wiki/Circular_buffer

In Java it is ArrayDeque https://docs.oracle.com/javase/8/docs/api/java/util/ArrayDeq...

I don't think this is a circular buffer. The strategy here is to shift the data inside the buffer to the middle once either the front or back pointer are at the front/end of the buffer respectively, rather than to wrap around.

My intuition is that a circular buffer would be better though, because it would not have to do any large scale moves of memory until it came time to reallocate.

There are many ways one might implement a circular buffer, that's not really important. The point is that you should use the standard names, so people may easily compare your "Double-ended vector" to the state of the art.

Yes, there are, but in my opinion, for it to be a circular buffer, it should wrap the end of the data back round to the front when the end of the queue reaches the end of the buffer.

Inserting 4 into:

    [x, x, x, 1, 2, 3]

Produces:

    [4, x, x, 1, 2, 3]

In a circular buffer, and:

    [x, 1, 2, 3, 4, x]

In the proposed "double-ended vector". The technique is different, the amortized complexity is also different. I think therefore, it warrants a different name, to avoid confusion.

It really is a double ended queue. A circular buffer is a particular data structure that share some properties with the double ended queue.

One of the difference is that a circular buffer has a fixed capacity. The double ended queue has no capacity limit.

A circular buffer can contain a number of nodes and get bigger when it runs out of space by making a larger buffer and copying the old data or clustering as I described above. It doesn't have a "fixed capacity".

My circular queue works without moving any elements on insertion (with cluster method) or just moving the nodes each time the buffer size is exceeded. It seems this "double ended queue" isn't as useful because it has to copy nodes, find a middle etc.

Even in the "cluster" version of my circular queue, you can quickly calculate the actual location of any node directly using it's "virtual" index number, even though the head and tail can "float" anywhere along each cluster array of structs.

Well, from what I remember from my data structures class, a queue/dequeue has to have O(1) worst case insertion, but otherwise, yeah, it's pretty much the same.

But your part made me think, indeed there's no inherent reason for a circular buffer to have a fixed capacity. You could use pretty much the same logic but implement reallocation when it's 100% full, and get most of the benefit of both.

Reply on news.ycombinator.com