ExpandableArray.java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
import java.util.Arrays; public class ExpandableArray { private int[] arr; private int count; public ExpandableArray(int initialSize){ arr = new int[initialSize]; count = 0; } private void expandArray(){ // Create a new array, copy everything. int[] newArr = new int[arr.length * 2]; for (int i = 0; i < arr.length; i++){ newArr[i] = arr[i]; } arr = newArr; } public void add(int i){ if (count == arr.length) expandArray(); arr[count++] = i; //count++; } // Order preserving insert // Requires shifting items in the array // from idx onward. // We don't want "holes" in our array, so // we'll return false if idx is greater than // count. public boolean insert(int i, int idx){ if (idx > count || idx < 0) return false; if (idx == count){ add(i); return true; } if (count == arr.length) expandArray(); for (int j = count-1; j >= idx; j--){ arr[j+1] = arr[j]; } arr[idx] = i; count++; return true; } public int indexOf(int i){ for (int j = 0; j < count; j++) if (arr[j]==i) return j; return -1; } @Override public String toString(){ return String.join(", ", Arrays.stream(arr) .limit(count) .mapToObj(String::valueOf) .toArray(String[]::new)); } public static void main(String[] args){ ExpandableArray arr = new ExpandableArray(2); arr.add(1); arr.add(2); System.out.println(arr); System.out.println("Index of 1 " + arr.indexOf(1)); System.out.println("Index of 2 " + arr.indexOf(2)); System.out.println("Index of 3 " + arr.indexOf(3)); arr.insert(3, 0); System.out.println(arr); System.out.println("Index of 3 " + arr.indexOf(3)); arr.insert(5, -1); System.out.println(arr); } } |