Implement custom Array List in Java
ArrayList also known as dynamic arrays because of its ability to resize itself automatically when an element is inserted or deleted.
Internally ArrayList elements are placed in contiguous storage (array) so that they can be accessed and traversed using iterators. Here are some properties of ArrayList
- By default ArrayList, data is inserted at the end.
- Inserting at the end takes differential time, because sometimes there may be a need of extending the array.
- Removing the last element takes only constant time because no resizing happens.
- Inserting and erasing at the beginning or in the middle is linear in time.
To have our own ArrayList class we need to implement below methods:
- void add(int data): This function takes one element and inserts it at the last. Amortized time complexity is O(1).
- void add(int data, int index): It inserts data at the specified index. Time complexity is O(1).
- int get(int index): It is used to get the element at the specified index. Time complexity is O(1).
- void pop(): It deletes the last element. Time complexity is O(1).
- int size(): It returns the size of the ArrayList. Time complexity is O(1). Advertisement
- int getCapacity(): It returns the capacity of the ArrayList. Time complexity is O(1).
- void print(): It is used to print array elements. Time complexity is O(N), where N is the size of the ArrayList.
import java.util.Arrays;
public class DynamicArray{
private int array[];
// holds the current size of array
private int size;
// holds the total capacity of array
private int capacity;
// default constructor to initialize the array and values
public DynamicArray(){
array = new int[2];
size=0;
capacity=2;
}
// to add an element at the end
public void add(int element){
// double the capacity if all the allocated space is utilized
if (size == capacity){
ensureCapacity(2);
}
array[size] = element;
size++;
}
// to add an element at a particular index
public void add(int index, int element){
// double the capacity if all the allocated space is utilized
if (size == capacity){
ensureCapacity(2);
}
// shift all elements from the given index to right
for(int i=size-1;i>=index;i--){
array[i+1] = array[i];
}
// insert the element at the specified index
array[index] = element;
size++;
}
// to get an element at an index
public int getElement(int index){
return array[index];
}
// to remove an element at a particular index
public void remove(int index){
if(index>=size || index<0){
System.out.println("No element at this index");
}else{
for(int i=index;i<size-1;i++){
array[i] = array[i+1];
}
array[size-1]=0;
size--;
}
}
/* method to increase the capacity, if necessary, to ensure it can hold at least the
* number of elements specified by minimum capacity arguement
*/
public void ensureCapacity(int minCapacity){
int temp[] = new int[capacity*minCapacity];
for (int i=0; i < capacity; i++){
temp[i] = array[i];
}
array = temp;
capacity = capacity * minCapacity;
}
/*
* Trim the capacity of dynamic array to the current size. i.e. remove unused space
*/
public void trimToSize(){
System.out.println("Trimming the array");
int temp[] = new int[size];
for (int i=0; i < size; i++){
temp[i] = array[i];
}
array = temp;
capacity = array.length;
}
// to get the current size
public int size(){
return size;
}
// to get the current capacity
public int capacity(){
return capacity;
}
// method to print elements in array
public void print(){
System.out.println("elements in array are :"+Arrays.toString(array));
}
}Advertisement