Menu
What is the difference between a Ring Buffer and a Circular Linked List?
What purpose does Ring Buffer serve that Circular Linked List cannot or vice versa?
792
A circular buffer is a popular way to implement a data stream because the code can be compact. A ring buffer is also known as a circular buffer, circular queue or cyclic buffer.
A Circular Queue is an extension of the Queue data structure such that the last element of the queue links to the first element. It is known as Ring Buffer, Circular Buffer or Cyclic Buffer.
Ring Buffer (or Circular Buffer) is a bounded circular data structure that is used for buffering data between two or more threads.
In computer science, a circular buffer, circular queue, cyclic buffer or ring buffer is a data structure that uses a single, fixed-size buffer as if it were connected end-to-end. This structure lends itself easily to buffering data streams. There were early circular buffer implementations in hardware.
A ring buffer is a single contiguous block of memory which contains your items and, when you reach the end, you cycle back to the start:
+----------------------+
| |
+-->| a | b | c | d |--+
=== increasing memory ===>
A circular linked list, due to the linked list nature, does not have to be contiguous at all, so all the elements can be scattered in memory. It simply obeys the property that the elements for a loop:
+---------| d |<-----------------+
| |
+-->| a |------------->| b |--+ |
| |
+-----------------+ |
| |
+-->| c |------------+
=== increasing memory ===>
The circular linked list has the same advantage over a ring buffer that a linked list has over a fixed array. It can vary in size and you can insert and delete items without shuffling.
The disadvantages are similar as well, no O(1) array access and increased work if you're expanding or contracting the list.
A ring buffer would tend to be used when you know the maximum allowed entries in it, or don't mind limiting it. For example, if you have a communications protocol that can throttle the sending side when the buffer becomes full, giving the receiving side time to catch up.
A circular linked list example would be a process list in an operating system where you need to be able to add or delete processes but you don't care about the head of the list, only the current item.
121
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
