We use static arrays in Java to encapsulate a dynamic array. The underlying core principle is similar to ArrayList in the Java Standard library.

1. Constructors and general functions

Define a static array data and a capacity size;

Define three constructors, one passing capacity, one with no arguments and a default capacity of 10, and one passing another array as an argument.

The swap function swaps the elements at the I and j indexes of the array.

public class Array<E> { private E[] data; private int size; Public Array(int capacity){data = (E[])new Object[capacity]; size = 0; Capacity =10 public Array(){this(10); } public Array(E[] arr){data = (E[])new Object[arr.length]; for(int i = 0 ; i < arr.length ; i ++) data[i] = arr[i]; size = arr.length; } public void swap(int I, int I, int j){ if(i < 0 || i >= size || j < 0 || j >= size) throw new IllegalArgumentException("Index is illegal."); E t = data[i]; data[i] = data[j]; data[j] = t; },,}Copy the code

Define three general functions, namely, get the capacity of the array, get the number of elements of the array, determine whether the array is empty;

Public int getCapacity(){return data.length; } public int getSize(){return size; Public Boolean isEmpty(){return size == 0; }Copy the code

2. Add elements

Define the function to add elements, insert new element e at index index; Note that when the array is full, it needs to be dynamically expanded. The resize function is shown below. To insert an element at the index of the array, we need to move all the elements after the index back one bit, so the time complexity is O(n);

Defining addLast and addFirst at the same time adds elements to the end and the header of the array;

E public void add(int index, E e){ if(index < 0 || index > size) throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size."); If (size == data.length) resize(2 * data.length); for(int i = size - 1; i >= index ; i --) data[i + 1] = data[i]; data[index] = e; size ++; } public void addLast(E E){add(size, E); } public void addFirst(E E){add(0, E); Private void resize(int newCapacity){E[] newData = (E[])new Object[newCapacity]; private void resize(int newCapacity){E[] newData = (E[])new Object[newCapacity]; for(int i = 0 ; i < size ; i ++) newData[i] = data[i]; data = newData; }Copy the code

3. Find and modify elements

Get and set functions are shown as follows, which can be directly indexed, and the time complexity is O(1).

/ / get the index index position of the element of public E get (int index) {if (index < 0 | | index > = size) throw new IllegalArgumentException (" get failed. Index is illegal."); return data[index]; } public void set(int index) public void set(int index) E e){ if(index < 0 || index >= size) throw new IllegalArgumentException("Set failed. Index is illegal."); data[index] = e; }Copy the code

Contains and find functions are shown as follows. At this time, we need to search through the number group, and the time complexity is O(n).

E public Boolean contains(e e){for(int I = 0; i < size ; i ++){ if(data[i].equals(e)) return true; } return false; Public int find(e e){for(int I = 0;} public int find(e e){for(int I = 0; i < size ; i ++){ if(data[i].equals(e)) return i; } return -1; }Copy the code

4. Delete elements

The remove function is shown as follows: to delete the element at index, the index index and the following elements need to be moved one bit forward, so the time complexity is O(n). At the same time, it should be noted that if the number of elements is only one quarter of the capacity after deleting the elements, we should reduce the capacity to half of the capacity.

The removeFirst and removeLast functions remove elements from the header and tail of an array.

RemoveElement removes element E. The index is searched by the element and then removed by the remove call.

// Remove the index element from the array, Return to delete elements public E remove (int index) {if (index < 0 | | index > = size) throw new IllegalArgumentException (" remove failed. Index is illegal."); E ret = data[index]; for(int i = index + 1 ; i < size ; i ++) data[i - 1] = data[i]; size --; data[size] = null; // loitering objects ! If (size == data.length / 4 && data.length / 2! = 0) resize(data.length / 2); return ret; } public E removeFirst(){return remove(0); } public E removeLast(){return remove(size-1); } public void removeElement(e e){int index = find(e); if(index ! = -1) remove(index); }Copy the code

Finally, the toString function prints the contents of a dynamic array for easy viewing.

@Override
public String toString(){

    StringBuilder res = new StringBuilder();
    res.append(String.format("Array: size = %d , capacity = %d\n", size, data.length));
    res.append('[');
    for(int i = 0 ; i < size ; i ++){
        res.append(data[i]);
        if(i != size - 1)
            res.append(", ");
    }
    res.append(']');
    return res.toString();
}
Copy the code

Here is the source code for the entire class:

public class Array<E> { private E[] data; private int size; Public Array(int capacity){data = (E[])new Object[capacity]; size = 0; Capacity =10 public Array(){this(10); } public int getCapacity(){return data.length; } public int getSize(){return size; Public Boolean isEmpty(){return size == 0; } public void add(int index, int index, int index) E e){ if(index < 0 || index > size) throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size."); If (size == data.length) resize(2 * data.length); for(int i = size - 1; i >= index ; i --) data[i + 1] = data[i]; data[index] = e; size ++; } public void addLast(E E){add(size, E); } public void addFirst(E E){add(0, E); } / / get the index index position of the element of public E get (int index) {if (index < 0 | | index > = size) throw new IllegalArgumentException (" get failed. Index is illegal."); return data[index]; } public void set(int index) public void set(int index) E e){ if(index < 0 || index >= size) throw new IllegalArgumentException("Set failed. Index is illegal."); data[index] = e; } public Boolean contains(e e){for(int I = 0; i < size ; i ++){ if(data[i].equals(e)) return true; } return false; Public int find(e e){for(int I = 0;} public int find(e e){for(int I = 0; i < size ; i ++){ if(data[i].equals(e)) return i; } return -1; } // Remove the index element from the array, Return to delete elements public E remove (int index) {if (index < 0 | | index > = size) throw new IllegalArgumentException (" remove failed. Index is illegal."); E ret = data[index]; for(int i = index + 1 ; i < size ; i ++) data[i - 1] = data[i]; size --; data[size] = null; // loitering objects ! = memory leak if(size == data.length / 4 && data.length / 2 ! = 0) resize(data.length / 2); return ret; } public E removeFirst(){return remove(0); } public E removeLast(){return remove(size-1); } public void removeElement(e e){int index = find(e); if(index ! = -1) remove(index); } @Override public String toString(){ StringBuilder res = new StringBuilder(); res.append(String.format("Array: size = %d , capacity = %d\n", size, data.length)); res.append('['); for(int i = 0 ; i < size ; i ++){ res.append(data[i]); if(i != size - 1) res.append(", "); } res.append(']'); return res.toString(); Private void resize(int newCapacity){E[] newData = (E[])new Object[newCapacity]; private void resize(int newCapacity){E[] newData = (E[])new Object[newCapacity]; for(int i = 0 ; i < size ; i ++) newData[i] = data[i]; data = newData; }}Copy the code