Basics

Array is a data structure composed of a collection of elements of the same type, which allocates a continuous piece of memory for storage. An array uses an index to access its elements. If we have n values, the array index ranges from 0 to n-1. For any I between 0 and n-1, we can use arr[i] in Java code to access the value of the ith element.

The following code creates an array of person names, and then prints the second element in the array:

String[] names = {"Zhang San", "Li Si", "Wang Wu"};
System.out.println(names[1]);

However, after the array is created, its size cannot be changed. If we want to dynamically change the size of the array, we need to create a large enough array of the same type, and then copy the data in the original array to the newly created array. For example, if you originally created an array with a length of 3 to store the names of 3 people, and later need to store the names of "Zhao Liu" and "Qian Qi", you need to re create an array with a length of 5 to store the names of 5 people. The relevant codes are as follows (Note: the System.arraycopy method can be used to copy the array):

String[] names = {"Zhang San", "Li Si", "Wang Wu"}; // Original array

// Now we need to store the names of "Zhao Liu" and "Qian Qi"
String[] newNames = new String[5];
// Copy previous data
for (int i = 0; i < names.length; i++) {
    newNames[i] = names[i];
}
// Deposit "Zhao Liu" and "Qian Qi"
newNames[3] = "Zhao Liu";
newNames[4] = "Qian Qi";

It's really troublesome to manually expand the array every time. We can encapsulate the methods of adding, deleting and accessing elements in the array and use them directly when needed.

API

The following are the related API s we define for arrays:

array

pubic class Array<Element> implements Iterable<Element>

            Array()                             Create an empty array
            Array(int capacity)                 Create an array of initialization capacity
            void add(Element e)                 Add an element
            Element get(int index)              Gets the element at the specified location
            void set(int index, Element e)      Sets the element at the specified location
            Element remove(int index)           Removes the element at the specified location
            int size()                          Gets the size of the array

• Generics: a special Java mechanism, also known as parameterized types. In the API, < Element > after the class name defines Element as a type parameter, which is a placeholder representing a specific data type that the class will use. Array < Element > can be understood as an array of certain elements. The array here can store any type of data. For example, you can write the following code to store String objects:

  Array<String> arr = new Array<String>();
  arr.add("Zhang San");
  ...
  

• Iteratable set: in many cases, you only need to process each element in the set in some way. This pattern is generally called iterator pattern. With it, we can write clear code without relying on the implementation of specific collection types. As long as Iterable is implemented, you can use for each to traverse each element in the collection. For example, the following code prints out the names of all people:

  Array<String> names = new Array<String>();
  ...
  for (String name : names) {
      System.out.println(name);
  }
  

  The above for each is equivalent to the following code (obviously, it is much easier to use for each):

  for (Iterator<String> iterator = names.iterator(); iterator.hasNext();) {
      String name = iterator.next();
      System.out.println(name);
  }
  

With the above API, the above code can be written using Array. Here, you only need to focus on the logic to be implemented, rather than the specific internal implementation details:

public static void main(String[] args) {
    Array<String> names = new Array<>(3);
    names.add("Zhang San");
    names.add("Li Si");
    names.add("Wang Wu");
    System.out.println(names);

    // Deposit "Zhao Liu" and "Qian Qi"
    names.add("Zhao Liu");
    names.add("Qian Qi");
    System.out.println(names);
}

realization

For more detailed implementation, see github: Array.java

public class Array<Element> implements Iterable<Element> {
	private Object[] elements;	// element
    private int size;			// Number of elements

    public Array() { this(0); }
    public Array(int capacity) { elements = new Object[capacity]; }
	public void add(Element e) {
        if (size == elements.length) {
            resize(size * 2 + 1);
        }
        elements[size++] = e;
    }
    public Element get(int index) { return (Element) elements[index]; }
    public void set(int index, Element e) {  elements[index] = e; }
    public int size() { return size; } 
    // For the implementation of the following methods, please see the following implementation instructions
    private void resize(int capacity)
	public void remove(int index)
    public Iterator<Element> iterator()
}

The default constructor creates a blank array (0 in length) and provides a version that can specify the initialization capacity, so that it can provide an appropriate capacity according to its own usage scenario, so as to avoid frequent internal expansion of the array during the process of adding elements, which will affect the performance. An array Object [] is maintained internally It is used to store elements and use the instance variable size to record the size of the array.

In order to more intuitively see the elements stored in the array, you also need to override the toString method:

public String toString() {
    StringBuilder sb = new StringBuilder("[");
    for (int i = 0; i < size; i++) {
        if (i > 0) {
            sb.append(",");
        }
        sb.append(elements[i]);
    }
    sb.append("]");
    return sb.toString();
}

The implementation of add, get and set methods is relatively simple. They are implemented by directly operating the array storing elements. The size() method is also provided to obtain the size of the array. If the element array is full, the add method will expand the array before adding elements. The related implementation is as follows:

Array expansion

The initialization length of elements is fixed. When elements are full, there is no free space to store subsequent added elements. At this time, it needs to be expanded. The implementation here is also relatively simple. Create a new array, copy the values in the original array, and then assign the new array to elements.

private void resize(int capacity) {
    Object[] newElements = new Object[capacity];
    for (int i = 0; i < size; i++) {
        newElements[i] = elements[i];
    }
    elements = newElements;
}

In the add method, adjust the length of the element array to twice the original length plus 1 (size * 2 + 1)

remove

When removing the element at the specified index i in the array, all elements after index i need to be moved forward one grid, and the last element in the array needs to be set to null to avoid the reference to the element at the invalid position.

For example, five elements are stored in the array: [Zhang San, Li Si, Wang Wu, Zhao Liu, Qian Qi]. If you want to delete the second element, the example of calling the remove(1) method is as follows:

Removal process (gray squares indicate locations that have not yet been processed):

The implementation is as follows:

public Element remove(int index) {
    for (int i = index + 1; i < size; i++) {
        elements[i - 1] = elements[i];
    }
    size--;
    Element oldValue = (Element) elements[size];
    elements[size] = null;
    if (size > 0 && size < elements.length / 4) {
        resize(elements.length / 2);
    }
    return oldValue;
}

When the size of the array is one fourth of its capacity, reduce the capacity of the array to one-half of its capacity.

iteration

The iterator() method is implemented as follows:

public Iterator<Element> iterator() {
    return new Iterator<Element>() {
        int cursor;

        @Override
        public boolean hasNext() {
            return cursor < size;
        }

        @Override
        public Element next() {
            return (Element) elements[cursor++];
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException("remove");
        }
    };
}

A pointer cursor of the current iterator is maintained internally. The implementation of relevant methods is described as follows:

• hasNext(): indicates whether there is another element. If the cursor pointer does not exceed the size of the array, it indicates that there is another element
• next(): get the next element and point the cursor pointer to the next element
• remove(): remove operation is not supported here. UnsupportedOperationException is thrown directly

The iteration diagram is as follows:

This article was launched in the blog park. The address of the blog park is: Playing algorithm | array - coder Qi - blog Garden (cnblogs.com)