1D Array Implementation

Let's do the implementation and understand it in a deep-dive. We will go step-by-step and implement the most useful method.
Declare and Initialization Phase- O(1)
int[] nums;
int maxCapacity;
int size = 0;

public Array(int maxCapacity) {
    this.maxCapacity = maxCapacity;
    nums = new int[maxCapacity];
}
Add Element- O(1)
private void add(int value) {
    if (size < maxCapacity) {
        nums[size++] = value;
    } else
        throw new ArrayIndexOutOfBoundsException(size);
}
Add Element in a particular and shift all the elements to the right- O(n)
private void add(int index, int value) {
    if (size < maxCapacity && index > 0) {
        int tempIndex = size;
        while(tempIndex > index) {
            nums[tempIndex] = nums[--tempIndex];
        }
        nums[index] = value;
        size = (index > size) ? index + 1 : size+1;
    } else
        throw new ArrayIndexOutOfBoundsException();
}
Update the element value for a particular index- O(1)
private int set(int index, int value) {
    if (index < size) {
        int prevValue = nums[index];
        nums[index] = value;
        return prevValue;
    }
    throw new ArrayIndexOutOfBoundsException(index);
}
Fetch element for a particular index- O(1)
private int get(int index) {
    if (index < size) {
        return nums[index];
    }
    throw new ArrayIndexOutOfBoundsException(index);
}
Remove element for a particular index- O(n)
public int remove(int index) {
    if (index < size) {
        int removeValue = nums[index];
        fastRemoval(index);
        return removeValue;
    }
    throw new ArrayIndexOutOfBoundsException(index);
}

private void fastRemoval(int index) {
    while (index < size-1) {
        nums[index] = nums[++index];
    }
    nums[size-1] = 0;
    size--;
}
Search element from the start and return first found index- O(n)
private int indexOf(int val) {
    for (int i = 0; i < size; i++) {
        if (nums[i] == val)
            return i;
    }
    return -1;
}
Search element from the end and return first found index- O(n)
private int lastIndexOf(int val) {
    for (int i = size-1; i >= 0; i--) {
        if (nums[i] == val)
            return i;
    }
    return -1;
}
Check element is exists- O(n)
private boolean contains(int val) {
    for (int i = 0; i < size; i++) {
        if (nums[i] == val)
            return true;
    }
    return false;
}
Check is array empty- O(1)
public boolean isEmpty() {
    return size == 0;
}
Get the size- O(1)
public int size() {
    return size;
}

Comments

Popular posts from this blog

Recursion

Stack

Data Structure & Algorithm