A static array
The most basic array in Java is familiar:
int[] array = new int[6];
for (int i = 0; i < array.length; i++){
array[i] = 2 * i + 1;
}
Copy the codeLoops the element into the specified location like this:
This is a static array because we fixed its length at the first initialization step and cannot change it later. So, because of this limitation, static arrays are not suitable for scenarios where you are unsure how much data to store. But if the array is full, can I create a new one, a longer one, and transfer the elements into the new array? This way, the array can continue to be used. With this in mind, we can create dynamic arrays based on static arrays.
The implementation principle of dynamic array
“Dynamic” is mainly reflected in the following aspects:
1. Add elements
Instead of being limited to the end of the array, you can choose the index location at will (as long as it does not exceed the array length). For example, add element 4 at index 1:
As you can see, you need to move the elements at index and to the right one unit to the right (starting with the last element), and finally overwrite the element at index with the new element.
2. Delete elements
As with adding elements, you can also select by index. For example, drop element 3 at index 0:
Removing an element Moves an element in the opposite direction of adding an element, starting at index, overwriting the previous element with the next element, and finally setting the last element to NULL.
3. Expand array capacity
Once the array is full of elements, array expansion can be triggered, that is, to create a longer array, transfer the elements of the original array to the new array, and reference to the new array, complete the array change.
4. Array reduction
If the array elements are too small relative to the total size (for example, the number of elements in the array is less than a quarter of the array’s size), array reduction is triggered, that is, a new, shorter array is created and elements are transferred to the new array.
Code implementation
Create a new Array class to implement these important functions in turn:
public class Array<E> { private E[] data; Private int size; Public Array(int capacity) {this.data = (E[]) new Object[capacity]; this.size = 0; } public Array() { this(10); Public void resize(int newCapacity) {// The length of the new array must be greater than 0 if (newCapacity < 0) throw new IllegalArgumentException("capacity must > 0!" ); // Create a new array E[] newData = (E[]) new Object[newCapacity]; For (int I = 0; i < size; i++) { newData[i] = data[i]; } // point a reference to a new array data = newData; } public void add(int index, @param element, @param element, @param element, @param element) E element) { if (index < 0 || index > size) throw new IllegalArgumentException("Illegal index, index must > 0 and <= size!" ); If (size == data.length) {resize(2 * data.length); } // Start at the end and move the element to the right until index for (int I = size-1; i >= index; i--) { data[i + 1] = data[i]; } // Add element data[index] = element; size++; } public void addFirst(E element) {add(0, element); Public void addLast(E element) {add(size, element); } /** * overwrites the element at the specified position by moving it one bit to the left, Remove elements (data [size - 1] = null) * @ param index index * / public E remove (int index) {if (index < 0 | | index > size) throw new IllegalArgumentException("Illegal index, index must > 0 and < size!" ); If (size == 0) throw new IllegalArgumentException("Empty array!") ); E removedElement = data[index]; For (int I = index; i < size - 1; i++) { data[i] = data[i + 1]; Data [size-1] = null; data[size-1] = null; size--; If (size == data.length / 4 && data.length / 2! = 0) resize(data.length / 2); return removedElement; } public E removeFirst() {return remove(0); } public E removeLast() {return remove(size-1); @override public String toString() {StringBuilder STR = new StringBuilder(); Str.append (string. format("Array: size = %d, capacity = %d\n[", size, // Loop to STR for (int I = 0; I < size; I ++) {str.append(data[I]); if (I < size - 1) str.append(", "); } str.append("]"); return str.toString(); }}Copy the codeLet’s test the use of this array:
Public static void main(String[] args) {Array<Integer> arr = new Array<>(); for (int i = 0; i < 10; i++) arr.add(i, i); System.out.println(arr); Arr. Add (arr. Size, 7); System.out.println(arr); For (int I = 0; i < 6; I++) {system.out.println (" element "+ arr.removefirst () +" removed!" ); } System.out.println(arr); } /* Array: size = 10, capacity = 10 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] Array: Size = 11, capacity = 20 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 7] Element 1 has been removed! Element 2 has been removed! Element 3 has been removed! Element 4 has been removed! Element 5 has been removed! Array: size = 5, capacity = 10 [6, 7, 8, 9, 7] */Copy the codeAs you can see, when the array is full, adding more elements can trigger the array expansion successfully. Reduction is also triggered when the array has too few elements. Implement a few more common methods to improve our dynamic array class:
Public int getSize() {return size; } public int getCapacity() {return data.length; Public Boolean isEmpty() {return getSize() == 0; Public int search(E element) {for (int I = 0; i < getSize(); i++) { if (data[i].equals(element)) { return i; }} // -1 indicates that return-1 is not found; } public Boolean contains(E element) {return search(element)! = 1; } / / according to the index search element value public E get (int index) {if (index < 0 | | index > size) throw new IllegalArgumentException (" Illegal index, index must > 0 and < size!" ); return data[index]; } public E getFirst() {return get(0); Public E getLast() {return get(getSize() -1); } public void set(int index, int index) E element) { if (index < 0 || index > size) throw new IllegalArgumentException("Illegal index, index must > 0 and < size!" ); data[index] = element; } public Boolean removeElement(E element) {int index = ();} public Boolean removeElement(E element) {int index = () search(element); if (index ! = -1) { remove(index); return true; } return false; } @param element specifies the element value */ public Boolean removeElementAll(E element) {Boolean isRemoved = false; int i = getSize() - 1; while (i >= 0) { if (data[i].equals(element)) { remove(i); isRemoved = true; } i--; } return isRemoved; }Copy the codeFrom the external caller’s point of view, the array change operation is not perceptible and feels like a dynamic array, butThe expansion and reduction operations require the creation of new arrays and traversal of the original arrays, resulting in excessive overhead, so it is not a good solution in terms of performance. We’ll look at more efficient data structures later.The Book of Algorithms 