实现一个自定义数组

  1/**
  2 * 实现一个数组，包含基本的元素操作方法
  3 *
  4 * @author wangy
  5 * @version 1.0
  6 * @date 2021/6/21 / 16:11
  7 */
  8public class CustomArray<E> {
  9
 10    private E[] data;
 11    /** 数组空间大小 */
 12    private int capacity;
 13    /** 数组当前元素个数 */
 14    private int count;
 15
 16    private static final int DEFAULT_SIZE = 10;
 17
 18    public CustomArray() {
 19        this(DEFAULT_SIZE);
 20    }
 21
 22    public CustomArray(int capacity) {
 23        data = (E[]) new Object[capacity];
 24        this.capacity = capacity;
 25        count = 0;
 26    }
 27
 28    public boolean isEmpty() {
 29        return count == 0;
 30    }
 31
 32    public boolean isFull() {
 33        return count == capacity;
 34    }
 35
 36    public int size() {
 37        return count;
 38    }
 39
 40    public void grow() {
 41        capacity = capacity + (capacity >> 1);
 42        E[] newData = (E[]) new Object[capacity];
 43        for (int i = 0; i < count; i++) {
 44            newData[i] = data[i];
 45        }
 46        data = newData;
 47    }
 48
 49    /*
 50     * 添加一个元素；
 51     * 删除一个元素；
 52     * 根据index获取元素；
 53     * 判断元素是否在数组中并返回下标；
 54     */
 55
 56    E add(E e) {
 57        if (count == capacity) {
 58            grow();
 59        }
 60        data[count++] = e;
 61        return e;
 62    }
 63
 64    E add(int index, E e) {
 65        if (count == capacity) {
 66            grow();
 67        }
 68        if (index > count) {
 69            throw new IndexOutOfBoundsException(
 70                    "index must between zero and count.");
 71        }
 72        if (index == count) {
 73            return add(e);
 74        }
 75        for (int i = count; i > index; i--) {
 76            data[i] = data[i - 1];
 77        }
 78        data[index] = e;
 79        ++count;
 80        return e;
 81    }
 82
 83    /**
 84     * 时间复杂度: O(n^2)
 85     *
 86     * @param e
 87     * @return
 88     */
 89    E remove(E e) {
 90        int index;
 91        if ((index = contains(e)) >= 0) {
 92            remove(index);
 93            // --count;
 94        }
 95        return e;
 96    }
 97
 98    /**
 99     * 移除index索引处的元素
100     * <p>
101     * 时间复杂度O(n)
102     *
103     * @param index
104     * @return
105     */
106    E remove(int index) {
107        if (index >= count) {
108            throw new IndexOutOfBoundsException(
109                    "index must between 0 and"
110                            + (count - 1) + ".");
111        }
112        E datum = data[index];
113        for (int i = index; i < count - 1; i++) {
114            data[i] = data[i + 1];
115        }
116        data[--count] = null;
117        return datum;
118    }
119
120    E get(int index) {
121        if (index >= count) {
122            throw new IndexOutOfBoundsException(
123                    "index must between 0 and "
124                            + (count - 1) + ".");
125        }
126        return data[index];
127    }
128
129    /**
130     * 判断元素E是否存在于数组中
131     * <p>
132     * 时间复杂度：O(n)
133     *
134     * @param e
135     * @return
136     */
137    int contains(E e) {
138        for (int i = 0; i < count; i++) {
139            if (data[i].equals(e)) {
140                return i;
141            }
142        }
143        return -1;
144    }
145
146    @Override
147    public String toString() {
148        return String.format(
149                "Array: %s, capacity: %d, count: %d",
150                Arrays.toString(data),
151                capacity,
152                count);
153    }
154
155    public static void main(String[] args) {
156        CustomArray<Integer> array = new CustomArray<>(2);
157        array.add(1);
158        array.add(2);
159        array.add(3);
160        array.add(4);
161
162        System.out.println("init==> " + array);
163        array.remove(Integer.valueOf(1));   // remove by value
164        System.out.println("remove==> " + array);
165        array.add(0, 9);
166        System.out.println("add==> " + array);
167        array.add(2, 8);
168        System.out.println("add==> " + array);
169        System.out.println("contains 6 ? " + (array.contains(6) != -1));
170        System.out.println("contains 3 ? " + (array.contains(3) != -1));
171        System.out.println("get by index 2: " + array.get(2));
172    }
173
174}
175
176/// :~
177// init==> Array:[1, 2, 3, 4], capacity:4, count:4
178// remove==> Array:[2, 3, 4, null], capacity:4, count:3
179// add==> Array:[9, 2, 3, 4], capacity:4, count:4
180// add==> Array:[9, 2, 8, 3, 4, null], capacity:6, count:5
181// contains 6 ? false
182// contains 3 ? true
183// get by index 2: 8