Circular Buffer in Java

  2. HowTo
  3. Java Howtos
  4. Circular Buffer in Java
Sheeraz Gul Feb 15, 2024
Java Java Buffer
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

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