Circular Buffer in Java

Sheeraz Gul Sep 11, 2022
Circular Buffer in Java

This tutorial demonstrates using arrays and linked lists to generate a circular buffer in Java.

Circular Buffer in Java

The circular buffer is known as an array which is used as a queue. When we constantly move data from one process to another, we cannot store that data in permanent memory locations because they time to retrieve it.

So we need to store this type of data in temporary locations, known as buffers, for example, the RAM. The Circular buffer, also known as a ring buffer, is a queue that allows the use of memory in a contiguous way.

The circular buffer works in the first in, first out FIFO manner and can be implemented using either array or a linked list. So let’s start learning with arrays.

Use Array to Create Circular Buffer in Java

To create the circular buffer using an array, we need to initialize an empty array in the constructor where the type of elements added to the array will be unknown.

Two pointers, head and tail, are used for the insertion and deletion operation, where the head is the first element, and tail is the last, as shown in the picture:

circular buffer in java - array circular buffer.png

Now there are two main operations, in and out means insertion and deletion:

Demonstration of the Insert Operation

Insertion is an easy operation with a few essential points:

  1. At the start, the array size is 0, where the head position is 0 and the tail position is -1.

  2. Then, we use the following formula for the index at which we will insert the element:

    int index_position = (tail_pointer + 1) % buffer_capacity
    array[index_position] = element;
    
  3. The size of the array and the tail pointer will increment by 1 when we insert an element into the array.

  4. When the array size equals its capacity, we can add no more elements.

Demonstration of the Delete Operation

  1. When an element is retrieved at the head pointer, there will be an increment of 1 in the head pointer and the decrement of 1 in the buffer size.

  2. The following formula is used for the index at which we will delete the element.

    int index_position = head_pointer % buffer_capacity;
    Elem element = (Elem) array[index_position];
    

    Now, for example, the input array for the circular buffer is:

    [7, 2, 5, 3, 4]
    

    The elements will be printed in order using the circular buffer:

    7
    2
    5
    3
    4
    

Let’s try to implement the above method for circular buffer in Java:

package delftstack;

import java.io.*;
import java.lang.*;

class Circular_Buffer {

    //the initial capacity of the buffer
    private int buffer_capacity = 0;
    // the initial size of the buffer
    private int buffer_size = 0;
    // the head pointer
    private int head_pointer = 0;
    // the tail pointer
    private int tail_pointer = -1;
    // the array
    private Object[] demo_array;

    Circular_Buffer(int array_capacity) {
        // initialize the array capacity in the constructor
        this.buffer_capacity = array_capacity;

        // initialize the array
        demo_array = new Object[array_capacity];
    }

    // insertion
    public void Insert(Object array_element) throws Exception {

        // calculate the index to insert the element
        int index = (tail_pointer + 1) % buffer_capacity;

        // increment in the size of the array
        buffer_size++;

        if (buffer_size == buffer_capacity) {
            throw new Exception("Buffer is Overflowen");
        }

        // store the element in the array
        demo_array[index] = array_element;

        // increment the tail pointer
        tail_pointer++;
    }

    // deletion 
    public Object Delete() throws Exception {

        // check if the array is empty
        if (buffer_size == 0) {
            throw new Exception("Buffer is empty");
        }

        // calculate the index of the element which is going to be deleted
        int element_index = head_pointer % buffer_capacity;

        // get the element
        Object array_element = demo_array[element_index];

        // increment the head pointer
        head_pointer++;

        // decrement the size of the array
        buffer_size--;

        // return the first element
        return array_element;
    }

    // retrieve the first element
    public Object Retrieve() throws Exception {

        // check if the array is empty
        if (buffer_size == 0) {
            throw new Exception("Buffer is empty");
        }

        // calculate the index of the element to be deleted
        int element_index = head_pointer % buffer_capacity;

        Object array_element = demo_array[element_index];

        return array_element;
    }
    
    // helper methods
    public boolean isEmpty() { return buffer_size == 0; }
    public int size() { return buffer_size; }
}

public class Example {
    public static void main(String[] args) throws Exception {

        // create the Circular Buffer using an array
        Circular_Buffer Array_CircularBuffer = new Circular_Buffer(10);

        // insert elements into the circular buffer
        Array_CircularBuffer.Insert(7);
        Array_CircularBuffer.Insert(2);
        Array_CircularBuffer.Insert(5);
        Array_CircularBuffer.Insert(3);
        Array_CircularBuffer.Insert(4);

        // print the elements with the delete method
        System.out.println("The elements were inserted and "
                + "now printed in the order by deletion:-");
        System.out.println(Array_CircularBuffer.Delete());
        System.out.println(Array_CircularBuffer.Delete());
        System.out.println(Array_CircularBuffer.Delete());
        System.out.println(Array_CircularBuffer.Delete());
        System.out.println(Array_CircularBuffer.Delete());
    }
}

The code above contains two classes, one for the methods and the other for the main class to run the operations.

The first class includes the methods for the insertion, deletion, and retrieval of the elements; the code will print the element one by one by applying the circular buffer insertion and deletion operation; see the output:

The elements were inserted and now printed in the order by deletion:-
7
2
5
3
4

Use Linked List to Create Circular Buffer in Java

To create a circular buffer using a linked list in Java, we need to create a helper class which we will use to create the generic nodes. Similar to the array, we will maintain the head and tail for the insertion and deletion; the process is shown in the picture:

circular buffer in java - linked list circular buffer

Demonstration of the Insert Operation

The steps for insertion to create a circular buffer using a linked list are:

  1. At the start, the size is 0, and the head and tail are null.
  2. Then, the elements are added to the tail of the linked list.
  3. The reference of the tail is then changed to the head pointer.
  4. When the elements are added to the linked list, the buffer size also increases.
  5. When the array size equals its capacity, we can add no more elements.

Demonstration of the Delete Operation

The steps for deletion are:

  1. First, we will retrieve the element at the head pointer.

  2. Second, we will change the reference of the head pointer to the next element.

  3. The size of the buffer will have a decrement of 1.

    Now, for example, the input array for a circular buffer using a linked list is:

    [7, 2, 5, 3, 4]
    

    The elements will be printed in order using the circular buffer with a linked list:

    7
    2
    5
    3
    4
    

Let’s try to implement the Circular buffer using the linked list in Java code:

package delftstack;

class Node<Elem> {
    // the data which will be stored in the linked list
    Elem Node_Data;
    // pointer to the next node
    Node<Elem> next_pointer;

    // the constructor will initialize the data in each node
    Node(Elem Node_data) { this.Node_Data = Node_data; }
}

class LinkedList_CircularBuffer<Elem> {

    // the head node
    Node<Elem> head_element;

    // the tail node
    Node<Elem> tail_element;
    int list_size = 0;
    int list_capacity = 0;

    // the constructor for circular buffer class
    LinkedList_CircularBuffer(int list_capacity) {
        this.list_capacity = list_capacity;
    }

    // insertion
    public void Insert(Elem element) throws Exception {

        // increment in the size when elements
        // are added to the linked list
        list_size++;

        // check the buffer
        if (list_size == list_capacity) {
            throw new Exception("Buffer is Overflowen");
        }

        if (head_element == null) {
            head_element = new Node<>(element);
            tail_element = head_element;
            return;
        }

        // The node element which will be linked
        Node<Elem> temp_element = new Node<>(element);

        // reference the last element to the head node
        temp_element.next_pointer = head_element;

        // update the tail reference to the latest node.
        tail_element.next_pointer = temp_element;

        // update the tail to the latest node, which is added now
        tail_element = temp_element;
    }

    // deletion
    public Elem Delete() throws Exception {

        // check the buffer
        if (list_size == 0) {
            throw new Exception("The Buffer is empty");
        }
        // get the element
        Elem element = head_element.Node_Data;

        // update the head pointer
        head_element = head_element.next_pointer;

        // update the tail reference to the head pointer
        tail_element.next_pointer = head_element;

        // decrement in the size
        list_size--;
        if (list_size == 0) {
            // remove any references present when the buffer is null
            head_element = tail_element = null;
        }
        return element;
    }

    // retrieve the head element without deleting it
    public Elem Retrieve() throws Exception {

        // check the buffer
        if (list_size == 0) {
            throw new Exception("Empty Buffer");
        }
        // get the element
        Elem element = head_element.Node_Data;
        return element;
    }

    // helper methods
    public boolean isEmpty() { return list_size == 0; }
    public int size() { return list_size; }
}

public class Example {
    public static void main(String[] args) throws Exception {

        // create the Circular Buffer using Linked List
        LinkedList_CircularBuffer<Integer> LL_CircularBuffer = new
                                    LinkedList_CircularBuffer<>(10);

        // insert elements to the circular Buffer
        LL_CircularBuffer.Insert(7);
        LL_CircularBuffer.Insert(2);
        LL_CircularBuffer.Insert(5);
        LL_CircularBuffer.Insert(3);
        LL_CircularBuffer.Insert(4);

        // printing the elements with the method delete
        System.out.println("The elements were inserted and "
                       + "now printed in the order by deletion:-");
        System.out.println(LL_CircularBuffer.Delete());
        System.out.println(LL_CircularBuffer.Delete());
        System.out.println(LL_CircularBuffer.Delete());
        System.out.println(LL_CircularBuffer.Delete());
        System.out.println(LL_CircularBuffer.Delete());
    }
}

The code above creates a generic node class to perform linked list operations and creates methods to perform insertion, deletion, and retrieve operations.

The code will create a circular buffer using the linked list and print the input list elements one by one, see the output below:

The elements were inserted and now printed in the order by deletion:-
7
2
5
3
4
Author: Sheeraz Gul
Sheeraz Gul avatar Sheeraz Gul avatar

Sheeraz is a Doctorate fellow in Computer Science at Northwestern Polytechnical University, Xian, China. He has 7 years of Software Development experience in AI, Web, Database, and Desktop technologies. He writes tutorials in Java, PHP, Python, GoLang, R, etc., to help beginners learn the field of Computer Science.

LinkedIn Facebook

Related Article - Java Buffer