basis
An array is a data structure consisting of a collection of elements of the same type, allocated a contiguous chunk of memory for storage. Arrays use indexes to access their 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 names and prints the second element of the array:
String[] names = {"Zhang"."Bill"."Fifty"};
System.out.println(names[1]);
Copy the codeBut once the array is created, its size cannot be changed. If we want to change the size of an array dynamically, we need to create a sufficiently large array of the same type, and then copy the data from the original array into the newly created array. For example, if you create an array of length 3 to store the names of three people, and then need to store the names of “Zhao 6” and “Qian 7”, you need to create a new array of length 5 to store the names of these five people. Arraycopy can be copied using the system. arrayCopy method:
String[] names = {"Zhang"."Bill"."Fifty"}; // The original array
// Now I need to store the names "Zhao 6" and "Qian 7"
String[] newNames = new String[5];
// Copy the previous data
for (int i = 0; i < names.length; i++) {
newNames[i] = names[i];
}
// Store "zhao 6" and "Qian 7"
newNames[3] = "Daisy";
newNames[4] = "Money seven";
Copy the codeAdding, deleting, and accessing elements to an array can be a hassle, but you can just use them when you need them.
API
Here is the API we defined for arrays:
An array of
pubic class Array<Element> implements Iterable<Element>
Array(a)Create an empty arrayArray(int capacity)Creates an array that initializes the capacityvoid add(Element e)Add an Element Elementget(int index)Gets the element at the specified positionvoid set(int index, Element e)Sets the Element Element at the specified locationremove(int index)Removes the element at the specified positionint size(a)Gets the size of the arrayCopy the code-
Generics: A special Java mechanism, also known as parameterized typing. In the API, the
following the class name defines Element as a type parameter, which is a placeholder for a specific data type that will be used by the class. Array
can be understood as an Array of elements. Our array can hold any type of data. For example, we could write the following code to hold a String object:
Array<String> arr = new Array<String>(); arr.add("Zhang"); .Copy the code -
Iterable collections: In many cases, only each element in the collection needs to be processed in a certain way. This pattern is commonly known as the iterator pattern. With this, we can write very clean code without relying on the implementation of specific collection types. Once Iterable is implemented, you can use for-each to iterate over each element in the collection, such as printing out all the names of people:
Array<String> names = newArray<String>(); .for (String name : names) { System.out.println(name); } Copy the codeThe above for-each is equivalent to the following code (which is obviously a lot easier to use) :
for (Iterator<String> iterator = names.iterator(); iterator.hasNext();) { String name = iterator.next(); System.out.println(name); } Copy the code
With the API above, you can write the code above using Array instead. Here, focus only on the logic that needs to be implemented, not on the specific internal implementation details:
public static void main(String[] args) {
Array<String> names = new Array<>(3);
names.add("Zhang");
names.add("Bill");
names.add("Fifty");
System.out.println(names);
// Store "zhao 6" and "Qian 7"
names.add("Daisy");
names.add("Money seven");
System.out.println(names);
}
Copy the codeimplementation
For a more detailed implementation, see Github: array.java
public class Array<Element> implements 可迭代<Element> {
private Object[] elements; / / element
private int size; // Number of elements
public Array(a) { 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(a) { return size; }
// For the implementation of these methods, see the following implementation instructions
private void resize(int capacity)
public void remove(int index)
public Iterator<Element> iterator(a)
}
Copy the codeThe default constructor creates a blank array (length 0). It also provides a version that can specify an initial capacity, so that it can provide an appropriate capacity for its own usage scenario and avoid frequent expansion of the array during the process of adding elements, which affects performance. Internal maintains an array Object[] to store elements, using the instance variable size to record the size of the array.
To make it more intuitive to see the elements in an array, we need to rewrite the toString method:
public String toString(a) {
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();
}
Copy the codeThe add, get, and set methods are all relatively simple to implement. They are all implemented by directly manipulating the array containing elements. Size () is also provided to obtain the size of the array. If the array is full, the add method expands the array before adding elements.
Array capacity
The initial length of elements is fixed. When elements are full, there is no space to store additional elements. The implementation here is also simpler: create a new array, copy the values from the original array, and 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;
}
Copy the codeIn the add method, double the size of the array of elements and add 1 (size * 2 + 1)
remove
When removing an element from the array at the specified index I, all elements after index I must be moved forward one space, and the last element in the array must be set to NULL to avoid references to elements at the invalid location.
For example, if there are five elements in the array: Zhang SAN, Li Si, Wang Wu, Zhao Liu, Qian Qi. To remove the second element, call the remove(1) method as shown in the following figure:
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;
}
Copy the codeWhen the size of an array is one-fourth of its capacity, reduce the size of the array to one-half of its capacity.
The iteration
The iterator() method is implemented as follows:
public Iterator<Element> iterator(a) {
return new Iterator<Element>() {
int cursor;
@Override
public boolean hasNext(a) {
return cursor < size;
}
@Override
public Element next(a) {
return (Element) elements[cursor++];
}
@Override
public void remove(a) {
throw new UnsupportedOperationException("remove"); }}; }Copy the codeInternal maintenance of a pointer to the current iterator cursor, the implementation of the related method is described as follows:
hasNext()If the cursor pointer does not exceed the size of the array, there is a next elementnext(): Gets the next element and points the CURSOR to the next elementremove(): There is no support for remove operation, throw directlyUnsupportedOperationExceptionabnormal
The diagram of iteration is as follows:
Garden, this article in the blog this blog park address: play algorithm – coder – qi – blog garden | array (cnblogs.com)