Don't talk too much nonsense

1. Start with the class name (I'm so considerate, like it)

public class Array<E>

First of all, array classes need to have generics, which is not much to say. It should be noted that in java, arrays can only be of the same type.

2. Member variable

private int size; //Number of elements in the array
private E[] data; //Array declaration

Add a digression:
About size and index, I was very sad when I first learned array. First, the index of array starts from 0, and size refers to the element of array.
If there are three elements in the array, then size=3, and the index is 0,1,2. They're a bit different. This magical design makes me write the boundary conditions of the cycle every time.
There's always a conversion.
For example, traverse all elements of an array

for (int i = 0; i < size; i++) { }

My mental journey is as follows:
First of all, the first step is to think that from 0 to the end of the index position of the last bit element, then the index of the last bit element should come in for loop, then i should
It is smaller than the next bit of the index of the last bit element, so who is the next bit of the index of the last bit element? Yes, the index of size peso is one bit larger, so it should be size.
So I < size;
If you think about it every time you write the limits of the for loop, you're wasting your brain. Am I the only one who is so stupid?
In the end, my way is to turn it into a picture to remember in my mind. Every time I use it, I think of it directly.

 

3. Construction method
A user specified initial array capacity
A user does not specify the initial array capacity

public Array (int capacity) {
data = (E[])new Object[capacity];
size = 0;
}

public Array () {
this(10); //Call another constructor with a default initial capacity of 10
}

4. Basic methods necessary for home use

//Get the number of array elements
public int getSize () {
return size;
}
//Get array length
public int getCapacity () {
return data.length;
}
//Get whether the array is empty
public boolean isEmpty () {
return size == 0;
}

 

5. Adding method

//Add elements to the array at the specified location. index For the specified index location, e Value added for
public void add (int index, E e) {
//The index position cannot allow it to be inserted blindly. The index is a negative number, or skip lattice insertion. It is not allowed.
if (index < 0 || index > size) {
throw new IllegalArgumentException("add is fail, require index < 0 || index > size");
}
//When the array capacity is full, call the expansion method. Here, expand it by twice the current array length.
if (data.length == size) {
this.resize(data.length * 2);
}
//The essence of array addition is: from the back to the specified index position, each element moves backward one cell to make room for the new one.
Key point: from back to front
for (int i = size - 1; i >= index; i--) {
data[i+1] = data[i];
}
//New entrant
data[index] = e;
//Maintain size
size ++;

}

 

//Add an element to the first bit of an array
public void addFirst (E e) {
//Reuse the previous one directly add Method
this.add(0, e);
}
//Add an element to the last bit of the array
public void addLast (E e) {
//Empathy
this.add(size, e);
}

 

6. Deletion method (I have two methods, one is based on index and the other is based on value)

Nature of deletion: in contrast to addition, it starts from the next bit of the index position to be deleted and ends at the index position of the last bit element, occupying a pit in turn.
Important: traverse from front to back

//Delete an element according to the index return the deleted element
public E remove (int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("remove is fail,require index < 0 || index >= size");
}
//Save the elements to be deleted first, or they will be overwritten later.
E value = data[index];
for (int i = index + 1; i < size; i++) {
data[i-1] = data[i];
}
//Maintain size
size --;
//Why is this set to null Because of generics, class objects are passed in, and reference addresses are stored in the array. If the references are kept open, the garbage collector cannot recycle them.
data[size] = null;
//Shrink here. When the number of array elements is equal to one quarter of the length of the array, shrinkif (size == data.length/4 && data.length / 2 != 0) {
//General reduction to array length
this.resize(data.length /2);
}
return value;
}

The question is, why not shrink in half? But a quarter?

This involves the problem of complexity oscillation. In an extreme case:
For example, an array with a capacity of 10.
At this time, the array is full. At this time, an element will come in, and then the array will be expanded. After the element is added, the capacity of the array is 20.
There are 11 elements inside.
At this time, I will delete one element of the array. After deletion, the number of array elements becomes 10, which is exactly one half of the array length.
Then automatically shrink, and so on. Repeat the operation. The time complexity of each expansion and shrink is O(n), so the solution of lazy is applied here.
When the number of array elements is one quarter of the length of the array, you can reduce the size to avoid this problem.

 

//Delete an element by value
public void removeByValue (E e) {
//Reuse the method to find the element based on the value, and return the index (this method is below)
int index = this.getByElement(e);
if (index != -1) {
//Reuse method of deleting according to index
this.remove(index);
}
}
//Delete first element
public E removeFirst () {
return this.remove(0);
}
//Delete last element
public E removeLast () {
return this.remove(size - 1);
}

 

7. Search method (also divided into two types, one is based on index and the other is based on value)

//Find an element of an array by index,Return value
public E getByIndex (int index) {

if (index < 0 || index >= size) {
throw new IllegalArgumentException("get is fail, require index < 0 || index >= size");
}

return data[index];
}

 

//Find an element of an array by value,Return index
public int getByElement (E e) {
//Essence: traversal array for comparison
for (int i = 0; i < size; i++) {
if (data[i].equals(e) ) {
return i;
}
}
return -1;
}

 

//Include this element or not
public boolean contains (E e) {
//Essence: traversal array for comparison
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
return true;
}
}
return false;
}

 

8. Modification method

//Modify an element of an array
public void set (int index, E e) {

if (index < 0 || index >= size) {
throw new IllegalArgumentException("set is fail, require index < 0 || index >= size");
}

data[index] = e;
}

 

9. Expansion method
The essence of expansion: to create a new array and copy the contents of the old array

private void resize (int newCatacity) {
E[] newData = (E[])new Object[newCatacity];
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
//Reassign a new reference to the member variable data (described in the memory diagram later)
data = newData;
}

Draw a memory map of expansion reference conversion

Test code

 public static void main(String[] args) {
        Array<Integer> array = new Array(5);
        array.addLast(1);
        array.addLast(2);
        array.addLast(3);
        array.addLast(4);
        array.addLast(5);
}

 

 

 

 

10.toString method
The essence is to create a StringBuilder object, and then through the append method, traverse the contents of the array and add them to the StringBuilder object.

@Override
public String toString () {
StringBuilder stringBuilder = new StringBuilder();
//Format(String, Object, Object) Designated String Replace the format item in with the two specified Object The text equivalent of the value of the instance.
stringBuilder.append(String.format("size =%d ,capacity =%d\n ", size, data.length));
stringBuilder.append('[');
for (int i = 0; i < size; i++) {
stringBuilder.append(data[i]);
if (i != size -1) {
stringBuilder.append(',');
}
}
stringBuilder.append(']');

return stringBuilder.toString();
}

 

Last,

Floating on the surface for thousands of times,

Better think it over.

I hope this article can help you.