When data is constantly moved from one place to another or from one process to another or is frequently accessed, it cannot be stored in permanent memory locations such as hard drives as they take time to retrieve the data. This type of data needs to be accessed quickly and is stored in temporary memory locations such as RAM known as buffers.Â
Examples of Buffer:
- When any video is streamed online, the data (the audio and video)is buffered right before the video is played. During this buffering process, the data is downloaded and stored in the RAM and is accessed whenever needed.
- A Word document stores the content and the changes made by the user in a buffer before the document is saved.
What is a Circular Buffer?
Circular Buffer or Ring Buffer is a circular queue that allows the usage of memory in a contiguous manner. Circular Buffer follows the FIFO principle i.e First In First Out.Â
Circular Buffers can be implemented in two ways, using an array or a linked list.
Approach 1: Using an Array
An empty object array along with its capacity is initialized inside the constructor as the type of elements added is unknown. Two pointers namely head and tail are maintained for insertion and deletion of elements. The head points to the first element and the tail points to the last element.
Circular Buffer using an array
Insertion of elements
Initially, the head is 0, the tail is -1 and the size is 0.Â
The index at which the element needs to be inserted is calculated using the formula: –
int index = (tail + 1) % capacity array[index] = element;
The tail pointer and the size increment by one upon insertion of an element. When the size of the array becomes equal to its capacity, the buffer is full and no more elements can be accommodated.
Deletion of elements:
The element at the head pointer is retrieved and the head pointer is incremented by one and the size of the buffer if decremented by one.
int index = head % capacity; E element = (E) array[index];
Example:
Input : [5, 6, 7, 1 ,4]
Output : The elements are printed in the order :-
5
6
7
1
4
Below is the implementation of the above approach
Java
// Java program to implement a// Circular Buffer using an arrayÂ
import java.io.*;import java.lang.*;class CircularBuffer {Â
    // Initial Capacity of Buffer    private int capacity = 0;    // Initial Size of Buffer    private int size = 0;    // Head pointer    private int head = 0;    // Tail pointer    private int tail = -1;    private Object[] array;Â
    // Constructor    CircularBuffer(int capacity)    {        // Initializing the capacity of the array        this.capacity = capacity;Â
        // Initializing the array        array = new Object[capacity];    }Â
    // Addition of elements    public void add(Object element) throws Exception    {Â
        // Calculating the index to add the element        int index = (tail + 1) % capacity;Â
        // Size of the array increases as elements are added        size++;Â
        // Checking if the array is full        if (size == capacity) {            throw new Exception("Buffer Overflow");        }Â
        // Storing the element in the array        array[index] = element;Â
        // Incrementing the tail pointer to point        // to the element added currently        tail++;    }Â
    // Deletion of elements    public Object get() throws Exception    {Â
        // Checking if the array is empty        if (size == 0) {            throw new Exception("Empty Buffer");        }Â
        // Calculating the index of the element to be        // deleted        int index = head % capacity;Â
        // Getting the element        Object element = array[index];Â
        // Incrementing the head pointer to point        // to the next element        head++;Â
        // Decrementing the size of the array as the        // elements are deleted        size--;Â
        // Returning the first element        return element;    }Â
    // Retrieving the first element without deleting it    public Object peek() throws Exception    {Â
        // Checking if the array is empty        if (size == 0) {            throw new Exception("Empty Buffer");        }Â
        // Calculating the index of the        // element to be deleted        int index = head % capacity;Â
        // Getting the element        Object element = array[index];Â
        // Returning the element        return element;    }Â
    // Checking if the array is empty    public boolean isEmpty() { return size == 0; }Â
    // Size of the array    public int size() { return size; }}Â
class Main {    public static void main(String[] args) throws Exception    {Â
        // Creating the Circular Buffer        CircularBuffer cb = new CircularBuffer(10);Â
        // Adding elements to the circular Buffer        cb.add(5);        cb.add(6);        cb.add(7);        cb.add(1);        cb.add(4);Â
        // Printing the elements        System.out.println(            "The elements are printed in the order :-");        System.out.println(cb.get());        System.out.println(cb.get());        System.out.println(cb.get());        System.out.println(cb.get());        System.out.println(cb.get());    }} |
The elements are printed in the order :- 5 6 7 1 4
Time complexity: O(1), for both insertion and deletion.
Approach 2: Using a Linked List
A Generic Node class is created which acts as a helper class to create the Circular Buffer.
Two pointers namely head and tail are maintained for insertion and deletion of elements. The head points to the first element and the tail points to the last element.
Circular Buffer using Linked List
Insertion of elements:Â
- Initially the head and tail are null and the size is 0.
- Elements are added to the tail of the Linked List and the reference of the tail is changed to the head pointer.
- Size of the Buffer increases as elements are added into the Linked List.
- When the size of the array becomes equal to its capacity, the buffer is full and no more elements can be accommodated.
Deletion of elements:
The element at the head pointer is retrieved and the reference of the head pointer changes to the next element and the size of the buffer if decremented by one.
Example :Â
Input : [5, 6, 7, 1 ,4]
Output: The elements are printed in the order :
5
6
7
1
4
Below is the implementation of the above approach:Â
Java
// Java program to implement a Circular// Buffer using a Linked ListÂ
// A Generic Node class is used to create a Linked Listclass Node<E> {    // Data Stored in each Node of the Linked List    E data;    // Pointer to the next node in the Linked List    Node<E> next;Â
    // Node class constructor used to initializes    // the data in each Node    Node(E data) { this.data = data; }}Â
class CircularBufferLL<E> {Â
    // Head node    Node<E> head;Â
    // Tail Node    Node<E> tail;    int size = 0;    int capacity = 0;Â
    // Constructor    CircularBufferLL(int capacity)    {        this.capacity = capacity;    }Â
    // Addition of Elements    public void add(E element) throws Exception    {Â
        // Size of buffer increases as elements        // are added to the Linked List        size++;Â
        // Checking if the buffer is full        if (size == capacity) {            throw new Exception("Buffer Overflow");        }Â
        // Checking if the buffer is empty        if (head == null) {            head = new Node<>(element);            tail = head;            return;        }Â
        // Node element to be linked        Node<E> temp = new Node<>(element);Â
        // Referencing the last element to the head node        temp.next = head;Â
        // Updating the tail reference to the        // latest node added        tail.next = temp;Â
        // Updating the tail to the latest node added        tail = temp;    }Â
    // Retrieving the head element    public E get() throws Exception    {Â
        // Checking if the buffer is empty        if (size == 0) {            throw new Exception("Empty Buffer");        }        // Getting the element        E element = head.data;Â
        // Updating the head pointer        head = head.next;Â
        // Updating the tail reference to        // the new head pointer        tail.next = head;Â
        // Decrementing the size        size--;        if (size == 0) {            // Removing any references present            // when the buffer becomes empty            head = tail = null;        }        return element;    }Â
    // Retrieving the head element without deleting    public E peek() throws Exception    {Â
        // Checking if the buffer is empty        if (size == 0) {            throw new Exception("Empty Buffer");        }        // Getting the element        E element = head.data;        return element;    }Â
    // Checking if the buffer is empty    public boolean isEmpty() { return size == 0; }Â
    // Retrieving the size of the buffer    public int size() { return size; }}Â
class GFG {    public static void main(String[] args) throws Exception    {Â
        // Creating the Circular Buffer        CircularBufferLL<Integer> cb            = new CircularBufferLL<>(10);Â
        // Adding elements to the circular Buffer        cb.add(5);        cb.add(6);        cb.add(7);        cb.add(1);        cb.add(4);Â
        // Printing the elements        System.out.println(            "The elements are printed in the order :-");        System.out.println(cb.get());        System.out.println(cb.get());        System.out.println(cb.get());        System.out.println(cb.get());        System.out.println(cb.get());    }} |
The elements are printed in the order :- 5 6 7 1 4
Time complexity: O(1), for both insertion and deletion.
Â
