Horje
Delete the Element in Array with Constant Time in Java

In Java, arrays are a basic data structure. Dynamic operations like Insertion and Deletion are costly due to their constant size. We can accomplish constant-time deletion operations by combining arrays and linked lists.

In this article, we will learn how to implement an Array with Constant-Time Deletion operations in Java.

Program to Implement Constant-Time Deletion Operations in an Array in Java

Let’s know this concept in detail with a simple example:

Java

// Java program to implement an array with
// Constant-Time Insertion and Deletion operation
import java.util.LinkedList;
  
// Driver Class
public class ConstantTimeArray {
    private static final int CHUNK_SIZE = 3;
    private LinkedList<Integer>[] chunks;
    private int size;
  
    public ConstantTimeArray() 
    {
        chunks = new LinkedList[1];
        chunks[0] = new LinkedList<>();
        size = 0;
    }
  
    public void insert(int element) 
    {
        if (size % CHUNK_SIZE == 0) 
        {
            addChunk();
        }
        int chunkIndex = size / CHUNK_SIZE;
        chunks[chunkIndex].add(element);
        size++;
    }
  
    public void delete(int index) 
    {
        if (index < 0 || index >= size) 
        {
            throw new IndexOutOfBoundsException("Index out of bounds");
        }
  
        int chunkIndex = index / CHUNK_SIZE;
        int elementIndex = index % CHUNK_SIZE;
        chunks[chunkIndex].remove(elementIndex);
        size--;
  
        // if the chunk becomes empty, remove it
        if (chunks[chunkIndex].isEmpty() && chunks.length > 1) 
        {
            removeChunk(chunkIndex);
        }
    }
  
    private void addChunk() 
    {
        LinkedList<Integer>[] newChunks = new LinkedList[chunks.length + 1];
        System.arraycopy(chunks, 0, newChunks, 0, chunks.length);
        newChunks[chunks.length] = new LinkedList<>();
        chunks = newChunks;
    }
  
    private void removeChunk(int index) 
    {
        LinkedList<Integer>[] newChunks = new LinkedList[chunks.length - 1];
        System.arraycopy(chunks, 0, newChunks, 0, index);
        System.arraycopy(chunks, index + 1, newChunks, index, chunks.length - index - 1);
        chunks = newChunks;
    }
  
    public void printArray() 
    {
        for (LinkedList<Integer> chunk : chunks) 
        {
            for (Integer element : chunk) 
            {
                System.out.print(element + " ");
            }
        }
        System.out.println();
    }
  
    public static void main(String[] args) 
    {
        ConstantTimeArray constantTimeArray = new ConstantTimeArray();
  
        // insert elements
        constantTimeArray.insert(1);
        constantTimeArray.insert(2);
        constantTimeArray.insert(3);
        constantTimeArray.insert(4);
         
  
        // print the array
        System.out.print("Array after insertion: ");
        constantTimeArray.printArray();
  
        // delete element at index 2
        constantTimeArray.delete(2);
  
        // print the array after deletion
        System.out.print("Array after deletion: ");
        constantTimeArray.printArray();
    }
}

Output

Array after insertion: 1 2 3 4 
Array after deletion: 1 2 4

Explanation of the above Program:

In the above program,

  • The addChunk() method adds an element in the LinkedList.
  • The removeChunk() method removes elements from the specified index.
  • After insertion and deletion, it will print the result in console.

Complexities of the above Method:

Time Complexity:

  • Insertion: O(1) amortized time complexity.
  • Deletion: O(1) average time complexity.

Space Complexity:

  • O(N), where N is the total number of elements.

 


Reffered: https://www.geeksforgeeks.org

Java

Related
How to Convert List of Lists to HashSet in Java Using Lambda Expression? How to Convert List of Lists to HashSet in Java Using Lambda Expression?
How to Convert a HashTable to Other Collections Types in Java? How to Convert a HashTable to Other Collections Types in Java?
Creating and Populating a TreeSet in Java Creating and Populating a TreeSet in Java
How to Update the Value of an Existing Key in a LinkedHashMap in Java? How to Update the Value of an Existing Key in a LinkedHashMap in Java?
How to Convert ISO 8601 Compliant String to java.util.Date? How to Convert ISO 8601 Compliant String to java.util.Date?

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 13



 

Horje