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)
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
Post a Comment