Features of arrays
- The biggest advantage of arrays is that they can be queried quickly, because arrays are quickly queried directly through the index: Array [2], so there are certain advantages in random access. Its data structure is a simple linear sequence, which makes element access very fast and traverses arrays by index.
- Arrays are best used when “indexes have meaning.
- But not all meaningful indexes are applicable to arrays. For example, indexes that are numbers of such length as id numbers cannot be used as indexes
- Arrays can also handle the “index has no meaning” case
- The disadvantages of arrays are: – It is slow to find elements by content – the size of arrays cannot be changed once determined – arrays can only store one type of data – it is inefficient to insert and delete elements – no methods are encapsulated and all operations need to be defined by the user
Array secondary encapsulation
Problems encountered in the case of “index without meaning” on appeal:
- Index has no semantics, how to indicate that there is no element?
- How do I add elements? How do I delete elements? How do I modify elements?
So we solve these problems by rewrapping Java arrays into our own array containers.
The main frame
We wrap it in a class named Array. Let’s start by writing the basic framework of the Array class:
public class Array {
/** * The actual array of data */
private int[] data;
/** * indicates the number of elements in the array */
private int size;
Capacity Construct Array * so that the user can define the capacity of Array **@param* / capacity capacity
public Array(int capacity) {
data = new int[capacity];
size = 0;
}
public Array(a) {
// The default array size is 10
this(10);
}
/** * Gets the number of elements in the array **@returnThe number of elements in the array */
public int getSize(a) {
return size;
}
/** * Gets the capacity of the array **@returnThe size of the array */
public int getCapacity(a) {
return data.length;
}
/** * returns whether the array is empty **@returnReturns true for null, false */ otherwise
public boolean isEmpty(a) {
return size == 0;
}
@Override
public String toString(a) {
if (isEmpty()) {
return "[]";
}
StringBuilder sb = new StringBuilder();
sb.append(String.format("Array: size = %d, capacity = %d\n", size, data.length));
sb.append("[");
for (int i = 0; i < size; i++) {
sb.append(data[i]);
if(i ! = size -1) {
sb.append(","); }}return sb.append("]").toString(); }}Copy the codeAdds elements to an array
Once the body frame is written, you need to add elements to the array. The easiest way to do this is to add elements to the end of the array, because size always points to the last element +1, the first place at the end of the array that has no elements. So when we add an element, we just put the element at size, and then we need to maintain size to be +1, so that size goes back to the end of the array, and so on.
/** * adds a new element ** to the position of the last element +1@paramE New element */
public void addLast(int e) {
// If the array is full, an exception is thrown
if (size == data.length) {
throw new IllegalArgumentException("AddLast failed. Array is full.");
}
data[size] = e;
size++;
}
Copy the codeHowever, for some special needs, you may need to add elements to the specified location. For example, if the elements in an array are ordered, I want to insert the new elements into the appropriate location to ensure the order of the elements in the array, as shown in the following figure:
/** * inserts a new element e ** at the index position@paramThe index index *@paramE New element */
public void add(int index, int e) {
if (size == data.length) {
throw new IllegalArgumentException("Add failed. Array is full.");
}
// If the index is negative or larger than size, an exception is thrown
// If index is greater than size, the elements in the array are not continuous, and if index is less than 0, it is invalid
if (index < 0 || index > size) {
throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
}
// Iterate through the array of elements from the last element until you reach the index pointed to by index
for (int i = size - 1; i >= index; i--) {
// Move each element back one bit
data[i + 1] = data[i];
}
// It is possible to use the array copy function directly to implement this logic
// System.arraycopy(data, index, data, index + 1, size - index);
// Insert a new element at index
data[index] = e;
// The final size needs to be +1
size++;
}
Copy the codeOnce we have implemented the insert method at the specified location, we can reuse this method and simplify the previous addLast as follows:
/** * adds a new element ** to the position of the last element +1@paramE New element */
public void addLast(int e) {
add(size, e);
}
Copy the codeWe can also use this method to add a new element to the front of the array as follows:
/** * adds a new element ** to all elements@paramE New element */
public void addFirst(int e) {
add(0, e);
}
Copy the codeQuery and modify elements in an array
Many times we need to query specific elements and modify specific elements, both of which are simple to implement. The user needs to pass in the index when modifying or querying a particular element, so we can encapsulate a private method to check that the index is valid so that other methods can reuse this logic without having to write the same logic to check the index.
/** * check whether the index is valid **@param index index
*/
private void checkIndex(int index) {
// If the index is negative or greater than or equal to size, an exception is thrown
// If index is greater than or equal to size, the user can access invalid data. If index is less than 0, the user can access invalid data
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Require index >= 0 and index <= size."); }}Copy the codeWe then implement methods to query specific elements and modify specific elements:
/** * gets the element ** at the index position@param index index
* @returnIndex The element of the index position */
public int get(int index) {
checkIndex(index);
return data[index];
}
/** * gets the last element in the array **@returnThe last element */
public int getLast(a) {
return get(size - 1);
}
/** * gets the first element in the array **@returnThe first element */
public int getFirst(a) {
return get(0);
}
/** * change the index position to e **@param index index
* @param e e
*/
public void set(int index, int e) {
checkIndex(index);
data[index] = e;
}
Copy the codeInclude, search and delete
When we have a certain number of elements in an array, we often encounter a requirement to check whether those elements contain a particular element. Another common requirement is to query the index position of a particular element, that is, to search for the element and return the index of the element, or a specific value if the element does not exist, usually -1, because -1 usually represents an invalid index.
/** * finds the element e ** in the array@param e e
* @returnReturns true if yes, false */ if no
public boolean contains(int e) {
int index = indexOf(e);
returnindex ! = -1;
}
/** * find the index of the element e in the array, if there is no element e, return -1 **@param e e
* @returnThe index of element e, or -1 */
public int indexOf(int e) {
for (int i = 0; i < size; i++) {
if (data[i] == e) {
returni; }}return -1;
}
Copy the codeLet’s look at how to delete the element with the specified index position. For example, I want to delete the element with index 1, as shown in the following figure:
In fact, this deletion is similar to the insert logic we implemented before, but can be reversed. As shown in figure, we need to delete the index for 1 element, only need to move the index of 2 elements to the left one, covering the index of 1 elements, and then the index for 3 elements to move to the left one, covering index for 2 elements, and then the index of 4 elements, then move to the left one, covering index for 3 elements, and so on… Until all the elements have moved one space to the left, add size-1. Finally, the element whose index was 1 has been overwritten, and the element 77 is no longer in the array, so the deletion logic is realized, as shown in the figure below:
Some of you might wonder, does it matter if there’s one more element in the array at the end? It doesn’t really matter, because the index position that size points to and the index position after it is invisible to the user. And array at the time of initialization is also will have a default value, for example, here is the data type int the default value is 0, as users can only access to he added to the array elements, and in the previous section we also wrote a check index method, can ensure the user’s index is legal, so the user doesn’t know here more than one element, It wouldn’t have any effect. Of course, you can also empty the extra element after size-1. Last but not least, arrays of primitive data types can be ignored, but if they are reference arrays, it is best to overwrite the extra element as null so that the data can be quickly garbage collected to slightly optimize performance.
/** * removes the element at index position from the array and returns the deleted element **@param index index
* @returnThe deleted element */
public int remove(int index) {
checkIndex(index);
int ret = data[index];
for (int i = index + 1; i < size; i++) {
data[i - 1] = data[i];
}
// Again, we can use the array copy function directly to implement this logic
// System.arraycopy(data, index + 1, data, index, size - index + 1);
size--;
data[size] = 0;
return ret;
}
Copy the codeThen, based on this deletion method, we can extend some convenient methods for users to use, as follows:
/** * removes the first element from the array and returns the deleted element **@returnThe deleted element */
public int removeFirst(a) {
return remove(0);
}
/** * removes the last element from the array and returns the deleted element **@returnThe deleted element */
public int removeLast(a) {
return remove(size - 1);
}
/** * removes the element e ** from the array@paramE The element to be deleted *@returnReturn true on success, false */ otherwise
public boolean removeElement(int e) {
int index = indexOf(e);
if(index ! = -1) {
remove(index);
return true;
}
return false;
}
/** * delete all elements e **@paramE The element to be deleted *@returnReturn true on success, false */ otherwise
public boolean removeAllElement(E e) {
for (int i = 0; i < size; ) {
if (data[i] == e) {
remove(i);
} else{ i++; }}return indexOf(e) == -1;
}
Copy the codeUse generic
So far, our Array class has only been able to store data of type int, but as a container for storing data, it should be able to store data of any type, not just one type. In order for our Array class to store data of any type, we need to use generics in Java. However, it is important to know that generics in Java cannot accept primitive data types, only reference types. The good news, however, is that basic data types in Java have their own wrapper classes, which encapsulate the basic types into a class that generics can accept.
public class Array<E> {
/** * The actual array of data */
private E[] data;
/** * The number of elements in the array */
private int size;
Capacity Construct Array * so that the user can define the capacity of Array **@param* / capacity capacity
public Array(int capacity) {
// Java syntax does not support direct new generics or generic arrays, so we need to force the new Object first
data = (E[]) new Object[capacity];
size = 0;
}
public Array(a) {
// The default array size is 10
this(10);
}
/** * Gets the number of elements in the array **@returnThe number of elements in the array */
public int getSize(a) {
return size;
}
/** * Gets the capacity of the array **@returnThe size of the array */
public int getCapacity(a) {
return data.length;
}
/** * returns whether the array is empty **@returnReturns true for null, false */ otherwise
public boolean isEmpty(a) {
return size == 0;
}
/** * adds a new element ** to the position of the last element +1@paramE New element */
public void addLast(E e) {
add(size, e);
}
/** * adds a new element ** to all elements@paramE New element */
public void addFirst(E e) {
add(0, e);
}
/** * inserts a new element e ** at the index position@paramThe index index *@paramE New element */
public void add(int index, E e) {
// Throw an exception if the array is full
if (size == data.length) {
throw new IllegalArgumentException("Add failed. Array is full.");
}
// If the index is negative or larger than size, an exception is thrown
// If index is greater than size, the elements in the array are not continuous, and if index is less than 0, it is invalid
if (index < 0 || index > size) {
throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
}
// Iterate through the array of elements from the last element until you reach the index pointed to by index
for (int i = size - 1; i >= index; i--) {
// Move each element back one bit
data[i + 1] = data[i];
}
// It is possible to use the array copy function directly to implement this logic
// System.arraycopy(data, index, data, index + 1, size - index);
data[index] = e;
size++;
}
/** * gets the element ** at the index position@param index index
* @returnIndex The element of the index position */
public E get(int index) {
checkIndex(index);
return data[index];
}
/** * gets the last element in the array **@returnThe last element */
public E getLast(a) {
return get(size - 1);
}
/** * gets the first element in the array **@returnThe first element */
public E getFirst(a) {
return get(0);
}
/** * change the index position to e **@param index index
* @param e e
*/
public void set(int index, E e) {
checkIndex(index);
data[index] = e;
}
/** * finds the element e ** in the array@param e e
* @returnReturns true if yes, false */ if no
public boolean contains(E e) {
int index = indexOf(e);
returnindex ! = -1;
}
/** * find the index of the element e in the array, if there is no element e, return -1 **@param e e
* @returnThe index of element e, or -1 */
public int indexOf(E e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
returni; }}return -1;
}
/** * removes the element at index position from the array and returns the deleted element **@param index index
* @returnThe deleted element */
public E remove(int index) {
checkIndex(index);
E ret = data[index];
for (int i = index + 1; i < size; i++) {
data[i - 1] = data[i];
}
// Again, we can use the array copy function directly to implement this logic
// System.arraycopy(data, index + 1, data, index, size - index + 1);
size--;
data[size] = null;
return ret;
}
/** * removes the first element from the array and returns the deleted element **@returnThe deleted element */
public E removeFirst(a) {
return remove(0);
}
/** * removes the last element from the array and returns the deleted element **@returnThe deleted element */
public E removeLast(a) {
return remove(size - 1);
}
/** * removes the element e ** from the array@paramE The element to be deleted *@returnReturn true on success, false */ otherwise
public boolean removeElement(E e) {
int index = indexOf(e);
if(index ! = -1) {
remove(index);
return true;
}
return false;
}
/** * delete all elements e **@paramE The element to be deleted *@returnReturn true on success, false */ otherwise
public boolean removeAllElement(E e) {
for (int i = 0; i < size; ) {
if (data[i] == e) {
remove(i);
} else{ i++; }}return indexOf(e) == -1;
}
@Override
public String toString(a) {
if (isEmpty()) {
return "[]";
}
StringBuilder sb = new StringBuilder();
sb.append(String.format("Array: size = %d, capacity = %d\n", size, data.length));
sb.append("[");
for (int i = 0; i < size; i++) {
sb.append(data[i]);
if(i ! = size -1) {
sb.append(","); }}return sb.append("]").toString();
}
/** * check whether the index is valid **@param index index
*/
private void checkIndex(int index) {
// If the index is negative or greater than or equal to size, an exception is thrown
// If index is greater than or equal to size, the user can access invalid data. If index is less than 0, the user can access invalid data
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Require index >= 0 and index <= size."); }}}Copy the codeThe dynamic array
With the introduction of generics, our Array can now store any type of data, and we’ve already implemented the basic add, delete, and change methods. The last problem is that the Array inside an Array is still a static Array, and static arrays are finite in size and cannot be changed at initialization. In real development, we usually can’t determine the size of an array, and we want to automatically expand the array when it becomes full, rather than throw an out-of-bounds exception, so we implement dynamic arrays.
Create an array with a larger capacity. For example, create a new array that is twice the size of the original array (1.5 times the size of an ArrayList), and copy all the elements of the old array into the new array. You can then point a reference to data to the new array, and the old array will lose its reference and be garbage collected, thus completing the expansion. The rest of the logic is to just add the new element to data as usual.
/** * Resets the array capacity **@paramNewCapacity newCapacity */
private void resize(int newCapacity) {
E[] newData = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
// You can use array copy directly
// System.arraycopy(data, 0, newData, 0, size);
data = newData;
}
Copy the codeThen modify the method of adding elements as follows:
/** * inserts a new element e ** at the index position@paramThe index index *@paramE New element */
public void add(int index, E e) {
// If the index is negative or larger than size, an exception is thrown
// If index is greater than size, the elements in the array are not continuous, and if index is less than 0, it is invalid
if (index < 0 || index > size) {
throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
}
// If the array is full, expand it
if (size == data.length) {
resize(data.length * 2);
}
// Iterate through the array of elements from the last element until you reach the index pointed to by index
for (int i = size - 1; i >= index; i--) {
// Move each element back one bit
data[i + 1] = data[i];
}
// It is possible to use the array copy function directly to implement this logic
// System.arraycopy(data, index, data, index + 1, size - index);
data[index] = e;
size++;
}
Copy the codeWhen deleting elements, we also want to reduce the size of the array if the number of elements in the array is less than half of the size. Again, we just need to call the resize method previously written. The code for modifying the remove method is as follows:
/** * removes the element at index position from the array and returns the deleted element **@param index index
* @returnThe deleted element */
public E remove(int index) {
checkIndex(index);
E ret = data[index];
for (int i = index + 1; i < size; i++) {
data[i - 1] = data[i];
}
// Again, we can use the array copy function directly to implement this logic
// System.arraycopy(data, index + 1, data, index, size - index + 1);
size--;
data[size] = null;
// Determine whether the capacity needs to be scaled down. Here, 1/4 of the capacity is scaled down to avoid complexity shock
if (size == data.length / 4 && data.length / 2! =0) {
resize(data.length / 2);
}
return ret;
}
Copy the codeTime complexity comparison
AddLast (e) : Since this method just adds one element to the end of the array, the complexity is O(1) because there is only one operation. If the array is full, it will trigger resize. Resize is O(n). Why is addLast still O(1)? This is because resize doesn’t happen every time, and resize is not unpredictable, we know exactly when resize will happen and how many times resize will occur, so we should spread the complexity evenly. Assume that capacity is 8 and each addLast operation is performed. After the addLast operation is performed for the ninth time, resize is triggered. A total of 17 basic operations (double resize) are performed. On average, each addLast operation takes two basic operations, so the time complexity is O(1). In this case, the amortized calculation makes more sense than the worst-case calculation
AddFirst (e) : This method adds the first element to the array, and then moves the remaining n elements one space to the right, so the complexity is O(n).
Add (index, e) : The complexity of this method depends on the value of index. When index is 0, the complexity is the same as addFirst, and when index is size, the complexity is the same as addLast. The index range is the number of elements in the array, so each index is equally likely to be specified. Complexity analysis is about figuring out what the worst case complexity is. The worst case of add is that index is 0, because when index is 0 all the elements in the array need to be moved, so it’s the same complexity as addFirst, order n.
Set (index, e) : The complexity of modifying elements by index is obviously O(1), because the elements of an array can be accessed/manipulated directly through the index
Get (index) : Again, this method is O(1).
Contains (e) : Without knowing the index, we can only determine whether the array contains an element by iterating through the array of elements, so the complexity is O(n).
IndexOf (e) : query the indexOf the element. In the worst case, traversing the entire array is O(n).
In the worst case, our add operation is O(N) :
- Add: O (n)
- Delete: O (n)
- Change: given index O(1); Unknown index O(n)
- O(1); Unknown index O(n)
Source code address: github.com/perkinls/ja…
Pay attention to the public number data craftsman record, focus on Java big data field offline, real-time technology dry goods regular sharing! Personal website www.lllpan.top