Search code examples
pythonalgorithmdata-structuresbufferdeque

What's the difference between a deque and circular buffer?


I apologize in advance for my lack of data-structure education.

From my understanding:

  • a fixed sized deque that serves as a memory can have its oldest value replaced (although we an remove new values)

  • a circular buffer that serves as memory can also have its oldest values replaced

What is the difference between the two concepts? Are they the same thing? Is one a subset of another?


Solution

  • A good related question would be this one: what's the difference between a queue and a linked list with a tail pointer? A queue adds to the end and removes from the front, which is the same thing you can do with a linked list with a tail pointer.

    The difference is that one of these is an abstraction and one of these is a concrete way of implementing that abstraction. There are several ways to implement a queue, including a linked list with a tail pointer, a circular buffer, or even a splay tree. Similarly, there are things you can do to a linked list with a tail pointer that you wouldn't do to a deque, such as splicing large sections into or out of the list.

    In your case, "deque" is the abstraction. You can think of a deque as "something where you can add and remove from both ends," and it could be implemented with a circular buffer, or a linked list, or a splay tree, etc. A circular buffer is one of many ways you can implement a deque, and there are other things you can do with a circular buffer beyond just implementing a deque.

    Hope this helps!