Dynamic array data structure implementation process (Java implementation)

A brief review of array basics

An array is a data structure used to store a collection of values of the same type.
An array is a container that stores data of a fixed length, ensuring that multiple data types are consistent.
An array is a reference data type.
Simply put, an array is a row of stored data.
The index of the array is counted from 0, and the index of the last position is the length of the array (n) -1 (that is, n-1).
You can access data using an index of an array.
The index of an array may or may not have semantics.

For example, if the index of an array storing students’ grades has meaning, then the index can be regarded as the student number, and the operation of the array using the index can be regarded as the operation of accessing students’ grades whose student number is XXX. So if you don’t have semantics, you’re randomly accessing the student’s scores into this array.
The biggest advantage of arrays: quick queries. For example, array[index].

Based on this advantage, arrays are best used in cases where “indexes have meaning.” Because the index has semantics, so we can know what data to take, is in which location, can be very convenient to query the data.

But not all meaningful indexes work with arrays, such as id numbers. As we know, an ID number is 18 digits long. If the index is an ID number, which corresponds to a person, then the array has to open up a lot of space. In short, it has to open up space to an index that has 18 digits long. So if the only access to a few people, at this time is a waste of space, but not so much space each index can be a id number, some is not id and the format of the corresponding, the space will be wasted, so all have semantic index is not suitable for array, to decide to use according to the situation.
Arrays can also handle the “index has no meaning” case. For example, an array has 10 Spaces, among which the first four Spaces have data, and the index has no meaning. For the user, the following space has no elements. Then, we need to consider how to deal with it. So we can double encapsulate an array class according to the Java static array to handle the “index has no meaning” situation, so as to master the array data structure.

Secondary wrapper array class design

The basic design

Here, I named the encapsulated Array class Array, which encapsulated a Java static Array data[] variable, and then based on this data[] for secondary encapsulation to achieve add, delete, change, search operations. We’ll implement them one by one.

Since the array itself is static, you need to specify the size when creating it. In this case, I use the variable capacity to represent the maximum number of elements in the array. You don’t need to declare it in the class, just in the constructor argument list, because the size of the array is the length of data[], and you don’t need to declare a variable to maintain it.

For the actual number of elements in the array, I’m using the variable size. The initial value is 0.

This size can also be represented as the first location in the array where no element is stored.

For example, if the array is empty, size is 0, and index 0 is the first location in the array where no element is stored. If there are two elements in the array, size = 2; if there are two elements in the array, size = 2; if there are two elements in the array, size = 2;

Create an Array class like this:

/** * Array class based on static array encapsulation **@authorSnow's looking for mei *@dateThe 2019-12-17 - then * /
public class Array {
    /** * static array data, based on the array to encapsulate the array class * data length corresponding to its capacity */
    private int[] data;

    /** * The number of elements the array currently has */
    private int size;

    /** * the default constructor is used when the user does not know how large an array to create
    public Array(a) {
        // Create an array of size 10 by default
        this(10);
    }

    /** * constructor, pass in the capacity of the Array to construct Array **@paramCapacity Specifies the array capacity. */ is specified by the user
    public Array(int capacity) {
        // Initialize data[] and size
        data = new int[capacity];
        size = 0;
    }

    /** * gets the current number of elements **@returnReturns the current number of elements */
    public int getSize(a) {
        return size;
    }

    /** * Get the capacity of the array **@returnReturns the size of the array */
    public int getCapacity(a) {
        // the length of data[] is relative to its capacity
        return data.length;
    }

    /** * check whether the array is empty **@returnReturns true if array is empty; Otherwise return false */
    public boolean isEmpty(a) {
        // The current number of elements in data[] is 0, indicating that the array is empty; otherwise, it is not empty
        return size == 0; }}Copy the code

Adds elements to an array

Adds elements to the end of the array

To add elements to an array, it is easiest to add elements to the end of the array, as follows:

Obviously, added to the end to the array elements is to add one of the most simple operation, because we already know the size of this variable points to is the first no element of the array, it is easy to understand, the size of the location is at the end of the array, what ever the place also is added to the end to the array elements when adding elements, Maintain the value of size after adding it by one. When adding, you also need to be aware that the array space is full.

The adding process is as follows:

The code is as follows:

/** * adds a new element ** to the end of the array@paramElement adds a new element */
public void addLast(int element) {
    // Check if the array space is full
    if (size == data.length) {
        throw new IllegalArgumentException("Failed to add element to end of array, array is full!");
    }
    // Add a new element to the end of the array
    data[size] = element;
    // Maintain the size variable after adding
    size++;
}
Copy the code

Adds an element to the array at the specified index location

Of course, you can’t always add elements to the end of an array, but you can do that when the user wants to add elements to the specified index position.

The first thing you need to do to add an element to the specified index position is to move the index position and all subsequent elements one place behind, leaving the index position empty.

Note: it is not really empty, the location is still the original element if there was one before, but a copy of the original element has been made and moved back one position.

The element is then added to the index location.

If there’s an element before that, you’re essentially overlaying the element on top of the original element.

Finally, maintain the size variable that stores the current number of elements in the array and increment its value by one.

Make sure there is enough space in the array and that the index position is valid (the valid value should be 0 to size).

The specific process is shown in the figure below:

This process is represented in code as follows:

/** * inserts a new element at the index of the array, element **@paramIndex Specifies the index * of the element to be inserted@paramElement The new element to insert */
public void add(int index, int element) {
    // Check if the array space is full
    if (size == data.length) {
        throw new IllegalArgumentException(Failed to add element to array at specified index location, array is full!);
    }

    // Check whether index is valid
    if (index < 0 || index > size) {
        throw new IllegalArgumentException("Failed to add element to array at index position, index should be in range [0, size]!");
    }

    // Move index and all elements after it one place
    for (int i = size - 1; i >= index; i--) {
        data[i + 1] = data[i];
    }

    // Add the new element element to the index position
    data[index] = element;
	
    // Maintain the size variable
    size++;
}
Copy the code

After implementing the above method, the addLast method can be simplified by simply reusing the add method and passing in the size variable and the element variable to be added, Element. As follows:

/** * adds a new element ** to the end of the array@paramElement adds a new element */
public void addLast(int element) {
	// reuse the add method to implement this method
    add(size, element);
}
Copy the code

Similarly, we could implement a method like this to add a new element to the array head, as follows:

/** * adds a new element ** to the head of the array@paramElement adds a new element */
public void addFirst(int element) {
	// reuse the add method to implement this method
    add(0, element);
}
Copy the code

Now that you’ve written the basic implementation of the add operation, it’s time to query and modify elements in an array.

Query and modify elements in an array

ToString = toString; toString = toString; toString = toString; toString = toString;

/** * override toString to display array information **@returnReturns the information in the array */
@Override
public String toString(a) {
    StringBuilder arrayInfo = new StringBuilder();

    arrayInfo.append(String.format("Array: size = %d, capacity = %d\n", size, data.length));

    arrayInfo.append("[");
    for (int i = 0; i < size; i++) {
        arrayInfo.append(data[i]);
        
        // Check if it is the last element
        if(i ! = size -1) {
            arrayInfo.append(",");
        }
    }
    arrayInfo.append("]");

    return arrayInfo.toString();
}
Copy the code

Now you can start implementing these operations:

The first implementation of the query method, here to achieve a method to obtain the specified index position of the element provided to the user to query the specified position of the element.

For this method, we know that the class is encapsulated based on a static array data[], so for the element to obtain the specified index position, we only need to use data[index] to obtain the corresponding element, and the user specified index position index validity detection can be done.

At the same time, we have done private processing for data before, so using this method to encapsulate the operation of obtaining elements can also avoid users to operate directly on data, and the validity of IDNEx has been tested in this method. Therefore, for the user, the unused space in the array, they will never be able to access, which ensures the security of the data, they just need to know that the elements in the used space in the array can be accessed.

The specific code is as follows:

/** * gets the element ** at the index position@paramIndex Gets the index position of the element *@returnReturns the element */ at the user-specified index position
public int get(int index) {
    // Check whether index is valid
    if (index < 0 || index >= size) {
        throw new IllegalArgumentException(Failed to get the element at index position, index should be in range [0, size]!);
    }

    // Returns the element at the user-specified index position
    return data[index];
}
Copy the code

Similarly, you can modify elements as follows:

/** * change index position element to element **@paramIndex Indicates the index position *@paramElement The element to be placed at index */
public void set(int index, int element) {
    // Check whether index is valid
    if (index < 0 || index >= size) {
        throw new IllegalArgumentException(Failed to change index position to specified element, index should be in range [0, size]!);
    }

    // Change the index position to element
    data[index] = element;
}
Copy the code

The content of this method is to modify the specified location of the old element into a new element, also index validity check, for the user is not able to modify the array of those unused space.

Once you’ve implemented the above methods, you can then implement the include, search, and delete methods in the array.

Contains, searches, and deletes elements from an array

Most of the time, we store a lot of elements in an array, and sometimes we need to know whether the elements in the array contain an element, so we need to implement a method to determine whether the array contains the elements we need.

This method is also easy to implement by iterating through the array to see if it contains the desired elements one by one.

/** * find if element ** exists in the array@paramElement The user needs to know if an element exists in the array *@returnReturn true if the array contains an element; Otherwise return false */
public boolean contains(int element) {
    // Go through the number group, judge one by one
    for (int i = 0; i < size; i++) {
        if (data[i] == element) {
            return true; }}return false;
}
Copy the code

However, sometimes the user needs to know not only whether the array contains the desired element, but also its index position. In this case, the user needs to implement a method to search for the desired element position in the array.

If an element is present, the index of the element is returned. If it is not present, the index of the element is returned. If it is not present, the index of the element is returned.

/** * find the element element in the array index **@paramElement The element to search for *@returnReturn the index of element Element if it exists; If it does not exist, -1 */ is returned
public int find(int element) {
    // Go through the number group, judge one by one
    for (int i = 0; i < size; i++) {
        if (data[i] == element) {
            returni; }}return -1;
}
Copy the code

Finally, implement the method of deleting elements in the array, first implement the method of deleting elements in the specified position.

This method is similar to the previous method of adding elements at the specified location, but reversed.

To delete, just starting from the specified location in a position, the specified position moves forward one by one all the elements of a position behind the front cover of elements, and then to maintain the size and return to delete its value minus one of elements, completes the delete this operation, specify the location of the element, of course, also need to specify the location of the legitimacy of judgment.

After the deletion is complete, size may contain the last element of the previous array or the default value of the array. When you create an array, each position has a default value of 0. But for users, this data is not available to them. As for the method of obtaining elements, index validity detection has been set, which limits the range of index to be greater than or equal to 0 and smaller than size, so the user cannot obtain the element at size position. To sum up, this position does not affect subsequent operations if it contains the previous element.

The process for deleting elements at a given location is shown as follows:

The code implementation is as follows:

/** * removes the element at index position from the array and returns the deleted element **@paramIndex Indicates the index * of the element to be deleted@returnReturns the deleted element */
public int remove(int index) {
    // Check whether index is valid
    if (index < 0 || index >= size) {
        throw new IllegalArgumentException("Failed to delete element at specified location, index should be in range [0, size]!");
    }

    // Store the element to be deleted for return
    int removeElement = data[index];

    // Delete
    for (int i = index + 1; i < size; i++) {
        data[i - 1] = data[i];
    }

    Size / / maintenance
    size--;

    // Returns the deleted element
    return removeElement;
}
Copy the code

Once we have implemented a method to delete an element at a given location, we can derive two simple methods from that method: a method to delete the first element in an array, and a method to delete the last element in an array. The implementation is as follows:

Delete the first element in the array:

/** * removes the first element from the array and returns the deleted element **@returnReturns the deleted element */
public int removeFirst(a) {
    // reuse the remove method to implement this method
    return remove(0);
}
Copy the code

Delete the last element in the array:

/** * removes the last element from the array and returns the deleted element **@returnReturns the deleted element */
public int removeLast(a) {
    // reuse the remove method to implement this method
    return remove(size - 1);
}
Copy the code

We can also implement a method that removes the specified element element from the remove method in conjunction with the previously implemented find method:

The implementation logic of this method is as follows:

Find is used to find the element to be removed. If found, the element index is returned. Remove is used with the index and returns true, or false if not found.

The implementation is as follows:

/** * Removes element element ** from the array@paramElement Specifies the element * to be deleted@returnReturn true if element was removed successfully; Otherwise return false */
public boolean removeElement(int element) {
    // Use find to find the index of the element
    int index = find(element);

    // If found, delete
    if(index ! = -1) {
        remove(index);
        return true;
    } else {
        return false; }}Copy the code

Note that duplicate elements can exist in the current array. If there are duplicate elements, only one element is deleted, not all of the elements in the array are deleted. forfindThe same is true for the method. If there are duplicate elements, the index found is the index of the first element found.

We can then implement a removeAllElement method that removes duplicate elements from the array:

For this method, the implementation logic is:

Use the find method to find the index of the element element that the user specified to remove.
Then use the while loop to judge the index:
If index is not equal to -1, the remove method is called in the loop to pass in the first found index for deletion.
We then use find again to see if the element is still there and determine that on the next loop.
And so on until the end of the loop removes all of the elements in the array.

To determine if there are any deletions in the array, I use a variable I to count the number of deletions:

ifwhileAfter the loopiIf the value of is greater than 0, it indicates that the deletion operation has been performedtrueIndicates that the element was deleted successfully, otherwise returnedfalseIndicates that there is no element to delete.

The specific implementation code is as follows:

/** * remove all elements from the array@paramElement Specifies the element * to be deleted@returnReturn true on success; Otherwise return false */
public boolean removeAllElement(int element) {
    // Use find to find the index of the element
    int index = find(element);

    // Used to record whether element element was deleted
    int i = 0;

    // Remove all this element from the array through the white loop
    while(index ! = -1) {
        remove(index);
        index = find(element);
        i++;
    }

    // The element element was deleted, returning true
    // Unable to find element element to delete, return false
    return i > 0;
}
Copy the code

The method of finding all indexes of an element in an array is no longer implemented here, but can be implemented by interested friends.

Now that the basic methods of the class are basically implemented, the next step is to use generics to modify the class to make it more generic, able to hold data of “any” data type.

Using generics to make the class more generic (able to hold data of “arbitrary” data types)

We know that we can’t store basic data types with generics, but they all have their own wrapper classes, so we can just use their wrapper classes for these basic data types.

Changing this class to a generic class is very simple and requires only a few changes, but the following points need to be noted:

For generics, Java does not support forms such as data = new E[capacity]; To create a new generic array, you need to go around a curve, as shown below:
```
data = (E[]) new Object[capacity];
Copy the code
```
If (data[I] == element); if (data[I] == element) After we converted our class to a generic class, we needed to make some changes to this judgment, because after using generics, the data in our array was reference objects, and we knew that it was better to use equals to compare reference objects, so we made the following changes:
```
if (data[i].equals(element)) {
    ...
}
Copy the code
```
As mentioned above, after the use of generics, the data in the array are reference objects, so in the implementation of remove method, after the maintenance of the size variable, we already know that the size position may have the previous reference, so we can set the size position to null. Make the garbage collection a faster way to reclaim the unwanted reference, avoiding object drift. Modified as follows:
```
/** * removes the element at index position from the array and returns the deleted element **@paramIndex Indicates the index * of the element to be deleted@returnReturns the deleted element */
public E remove(int index) {...Size / / maintenance
    size--;

    // Release references at size to avoid object drift
    data[size] = null; . }Copy the code
```

To sum up, the total changes to make this class generic are as follows:

public class Array<E> {

    /** * static array data, based on the array to encapsulate the array class * data length corresponding to its capacity */
    private E[] data;

    /** * The number of elements the array currently has */
    private int size;

    /** * the default constructor used when the user does not know how large an array to create
    public Array(a) {
        // Create an array of size 10 by default
        this(10);
    }

    /** * constructor, pass in the capacity of the Array to construct Array **@paramCapacity Specifies the array capacity. */ is specified by the user
    public Array(int capacity) {
        // Initialize data
        data = (E[]) new Object[capacity];
        size = 0;
    }

    /** * gets the current number of elements **@returnReturns the current number of elements */
    public int getSize(a) {
        return size;
    }

    /** * Get the capacity of the array **@returnReturns the size of the array */
    public int getCapacity(a) {
        return data.length;
    }

    /** * check whether the array is empty **@returnReturns true if array is empty; Otherwise return false */
    public boolean isEmpty(a) {
        return size == 0;
    }

    /** * inserts a new element at the index of the array, element **@paramIndex Specifies the index * of the element to be inserted@paramElement The new element to insert */
    public void add(int index, E element) {
        // Check if the array space is full
        if (size == data.length) {
            throw new IllegalArgumentException(Failed to add element to array at specified index location, array is full!);
        }
    
        // Check whether index is valid
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("Failed to add element to array at index position, index should be in range [0, size]!");
        }
    
        // Move index and all elements after it one place
        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }

        // Add the new element element to the index position
        data[index] = element;
        
        // Maintain the size variable
        size++;
    }

    /** * adds a new element ** to the head of the array@paramElement adds a new element */
    public void addFirst(E element) {
        // reuse the add method to implement this method
        add(0, element);
    }

    /** * adds a new element ** to the end of the array@paramElement adds a new element */
    public void addLast(E element) {
        // reuse the add method to implement this method
        add(size, element);
    }

    /** * gets the element ** at the index position@paramIndex Gets the index position of the element *@returnReturns the element */ at the user-specified index position
    public E get(int index) {
        // Check whether index is valid
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException(Failed to get the element at index position, index should be in range [0, size]!);
        }
        
        // Returns the element at the user-specified index position
        return data[index];
    }

    /** * change index position element to element **@paramIndex Indicates the index position *@paramElement The element to be placed at index */
    public void set(int index, E element) {
        // Check whether index is valid
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException(Failed to change index position to specified element, index should be in range [0, size]!);
        }

        // Change the index position to element
        data[index] = element;
    }

    /** * find if element ** exists in the array@paramElement The user needs to know if an element exists in the array *@returnReturn true if the array contains an element; Otherwise return false */
    public boolean contains(E element) {
        // Go through the number group, judge one by one
        for (int i = 0; i < size; i++) {
            if (data[i].equals(element)) {
                return true; }}return false;
    }

    /** * find the element element in the array index **@paramElement The element to search for *@returnReturn the index of element Element if it exists; If it does not exist, -1 */ is returned
    public int find(E element) {
        // Go through the number group, judge one by one
        for (int i = 0; i < size; i++) {
            if (data[i].equals(element)) {
                returni; }}return -1;
    }

    /** * removes the element at index position from the array and returns the deleted element **@paramIndex Indicates the index * of the element to be deleted@returnReturns the deleted element */
    public E remove(int index) {
        // Check whether index is valid
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Failed to delete element at specified location, index should be in range [0, size]!");
        }

        // Store the element to be deleted for return
        E removeElement = data[index];

        // Delete
        for (int i = index + 1; i < size; i++) {
            data[i - 1] = data[i];
        }

        Size / / maintenance
        size--;

        // Release references at size to avoid object drift
        data[size] = null;

        // Returns the deleted element
        return removeElement;
    }

    /** * removes the first element from the array and returns the deleted element **@returnReturns the deleted element */
    public E removeFirst(a) {
        // reuse the remove method to implement this method
        return remove(0);
    }

    /** * removes the last element from the array and returns the deleted element **@returnReturns the deleted element */
    public E removeLast(a) {
        // reuse the remove method to implement this method
        return remove(size - 1);
    }

    /** * Removes element element ** from the array@paramElement Specifies the element * to be deleted@returnReturn true if element was removed successfully; Otherwise return false */
    public boolean removeElement(E element) {
        // Use find to find the index of the element
        int index = find(element);

        // If found, delete
        if(index ! = -1) {
            remove(index);
            return true;
        } else {
            return false; }}/** * remove all elements from the array@paramElement Specifies the element * to be deleted@returnReturn true on success; Otherwise return false */
    public boolean removeAllElement(E element) {
        // Use find to find the index of the element
        int index = find(element);

        // Used to record whether element element was deleted
        int i = 0;

        // Remove all this element from the array through the white loop
        while(index ! = -1) {
            remove(index);
            index = find(element);
            i++;
        }

        // The element element was deleted, returning true
        // Unable to find element element to delete, return false
        return i > 0;
    }

    /** * override toString to display array information **@returnReturns the information in the array */
    @Override
    public String toString(a) {
        StringBuilder arrayInfo = new StringBuilder();

        arrayInfo.append(String.format("Array: size = %d, capacity = %d\n", size, data.length));

        arrayInfo.append("[");
        for (int i = 0; i < size; i++) {
            arrayInfo.append(data[i]);
            // Check if it is the last element
            if(i ! = size -1) {
                arrayInfo.append(",");
            }
        }
        arrayInfo.append("]");

        returnarrayInfo.toString(); }}Copy the code

Here are some tests to do:

Test code:

public static void main(String[] args) {
    Array<Integer> array = new Array<>(20);

    for (int i = 0; i < 10; i++) {
        array.addLast(i);
    }

    System.out.println(array + "\n");

    array.add(1.20);
    System.out.println(array);

    array.addFirst(35);
    System.out.println(array);

    array.addLast(40);
    System.out.println(array + "\n");

    Integer e = array.remove(6);
    System.out.println("e: " + e);
    System.out.println(array + "\n");

    e = array.removeLast();
    System.out.println("e: " + e);
    System.out.println(array + "\n");

    e = array.removeFirst();
    System.out.println("e: " + e);
    System.out.println(array + "\n");

    int size = array.getSize();
    int capacity = array.getCapacity();
    System.out.println("size: " + size + ", capacity: " + capacity + "\n");

    e = array.get(3);
    System.out.println("e: " + e);

    array.set(3.66);
    e = array.get(3);
    System.out.println("e: " + e);
    System.out.println(array + "\n");

    boolean empty = array.isEmpty();
    System.out.println("empty: " + empty);

    boolean contains = array.contains(9);
    System.out.println("contains: " + contains + "\n");

    int index = array.find(9);
    System.out.println(array);
    System.out.println("index: " + index + "\n");

    boolean b = array.removeElement(9);
    System.out.println(array);
    System.out.println("b: " + b + "\n");

    array.addLast(88);
    array.addLast(88);
    array.addLast(88);
    System.out.println(array);

    b = array.removeAllElement(88);
    System.out.println(array);
    System.out.println("b: " + b);
}
Copy the code

Test results:

Array: size = 10, capacity = 20 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] Array: size = 11, capacity = 20 [0, 20, 1, 2, 3, 4, 5, 6, 7, 8, 9] Array: size = 12, capacity = 20 [35, 0, 20, 1, 2, 3, 4, 5, 6, 7, 8, 9] Array: size = 13, capacity = 20 [35, 0, 20, 1, 2, 3, 4, 5, 6, 7, 8, 9, 40] e: 4 Array: size = 12, capacity = 20 [35, 0, 20, 1, 2, 3, 5, 6, 7, 8, 9, 40] e: 40 Array: size = 11, capacity = 20 [35, 0, 20, 1, 2, 3, 5, 6, 7, 8, 9] e: 35 Array: size = 10, capacity = 20 [0, 20, 1, 2, 3, 5, 6, 7, 8, 9] size: 10, capacity: 20 e: 2 e: 66 Array: size = 10, capacity = 20 [0, 20, 1, 66, 3, 5, 6, 7, 8, 9] empty: false contains: true Array: size = 10, capacity = 20 [0, 20, 1, 66, 3, 5, 6, 7, 8, 9] index: 9 Array: size = 9, capacity = 20 [0, 20, 1, 66, 3, 5, 6, 7, 8] b: true Array: size = 12, capacity = 20 [0, 20, 1, 66, 3, 5, 6, 7, 8, 88, 88, 88] Array: Size = 9, Capacity = 20 [0, 20, 1, 66, 3, 5, 6, 7, 8] b: trueCopy the code

After converting the class to a generic class to support storing “arbitrary” types of data, you can modify the class so that it can dynamically expand and shrink itself to conserve resources based on the amount of data stored.

Upgrade to a dynamic array

For a dynamic array, we need to achieve the effect that it can automatically expand its space according to the size of its data, so there are two relative cases: when the array space is full, when the array space is small enough to reduce the size. Let’s do it one by one.

Expand when the array space is full

In this case, in our previous implementation, when we ran out of array space we were adding new data to it and we couldn’t add any more data to the array, so we needed to expand our add method so that we could add new data.

For capacity expansion, you can implement a method resize to change the capacity:

Construct a new array, newData, with twice the capacity of the current array.
- The reason why I’m going to double my space and not just expand it by a constant, is because I don’t know how much space I need to expand it by if I expand it by a constant.
- For example, if you have tens of thousands of elements, it’s very inefficient to expand a few dozen, because if you want to add a lot of data, you need to expand many times.
- Another example is that it is very wasteful to expand a lot of capacity at a time. For example, if the original 10 data are expanded by 1000 capacity, a lot of space may be wasted.
- The capacity expansion is related to the current capacity of the array. The capacity expansion is the same as the existing capacity. For example, if the original capacity is 100, the capacity expansion is 200; if the original capacity is 10000, the capacity expansion is 20000. This method of expansion has advantages, and complexity analysis will be conducted later to analyze the advantages.
Use a loop to copy the data from the current array to the new array.
Reference the current array’s reference variable data to newData.
The operation of size is still the same as the operation in the previous add method, so it is not necessary to operate in the capacity expansion method.
Previous references to data are automatically reclaimed by garbage collection because data is already referenced to the new array and no other variables reference them.
The newData variable is a local variable that will disappear automatically after the add data method is executed, so there is no need to perform additional operations on it.
So in the end, the data variable refers to all the data that was added after the array was expanded.

The above process is illustrated as follows:

The modified code looks like this:

/** * inserts a new element at the index of the array, element **@paramIndex Specifies the index * of the element to be inserted@paramElement The new element to insert */
public void add(int index, E element) {
    // Check whether index is valid
    if (index < 0 || index > size) {
       throw new IllegalArgumentException("Failed to add element to array at index position, index should be in range [0, size]!");
    }

    // Check whether the array space is used up. If so, expand the array and add data
    if (size == data.length) {
        // Double the capacity of data
        resize(2 * data.length);
    }

    // Move index and all elements after it one place
    for (int i = size - 1; i >= index; i--) {
        data[i + 1] = data[i];
    }

    // Add the new element element to the index position
    data[index] = element;

    // Maintain the size variable
    size++;
}

/** * Change the capacity of data **@paramNewCapacity newCapacity of data */
private void resize(int newCapacity) {
    E[] newData = (E[]) new Object[newCapacity];

    for (int i = 0; i < size; i++) {
        newData[i] = data[i];
    }

    data = newData;
}
Copy the code

When the array space is small enough to reduce the size

In this case, in the previous implementation of the remove method, no other operations were carried out after the element was deleted. At this time, we need to make a judgment to determine whether the number of remaining elements in the array after the element is deleted reaches a relatively small value. If so, we will perform the reduction operation. Set this value to half the original size of the array. If the number of elements remaining is equal to this value, temporarily reduce the size of the array by half.

At this point, you can reuse the above implementation to change the size of the array method, the specific code implementation is as follows:

/** * removes the element at index position from the array and returns the deleted element **@paramIndex Indicates the index * of the element to be deleted@returnReturns the deleted element */
public E remove(int index) {
    // Check whether index is valid
    if (index < 0 || index >= size) {
        throw new IllegalArgumentException("Failed to delete element at specified location, index should be in range [0, size]!");
    }

    // Store the element to be deleted for return
    E removeElement = data[index];

    // Delete
    for (int i = index + 1; i < size; i++) {
        data[i - 1] = data[i];
    }

    Size / / maintenance
    size--;

    // Release references at size to avoid object drift
    data[size] = null;

    // Check whether the number of elements in the current data reaches the threshold for capacity reduction. If so, perform capacity reduction
    if (size == data.length / 2) {
        // Reduce the capacity by half
        resize(data.length / 2);
    }

    // Returns the deleted element
    return removeElement;
}
Copy the code

At this point, we have basically implemented the functions of dynamic arrays, and then we do some simple time complexity analysis of the current implementation method to find some efficiency improvements to make the array class more complete.

Simple time complexity analysis with some improvements

Time complexity analysis for add operations

For add operations, three methods have been implemented: addLast, addFirst, and Add. Here is a brief analysis of their time complexity:

AddLast: For this method, each addition is assigned directly at the end of the array without moving elements, so the time complexity of this method is O(1).

AddFirst: For this method, each addition requires all elements of the array to be moved back one place to make room for the first element, which gives the time complexity of O(n).

Add: For this method, it may sometimes be added at the front of the array, and it may sometimes be added at the back of the array, but overall, the number of moves is about N /2, so the time complexity of this method is O(n/2) = O(n).

So in general, the time complexity of the add operation is O(n). (Worst case)

For the resize method in the add operation, all elements in the array are copied once with each execution, so the time complexity of this method is O(n).

Time complexity analysis of delete operations

From the above time complexity analysis of add operations, it can be quickly concluded that the time complexity of delete operations is as follows:

RemoveLast: O (1)

RemoveFirst: O (n)

Remove: O(n/2) = O(n)

In general, the time complexity of delete operations is O(n). (Worst case)

The resize method has been analyzed above, and the time complexity is O(n).

Time complexity analysis for modification operations

For modification operations, the set method is implemented, for which there are two cases:

Know the index of the element to be modified: If you know the index, you can find the element to be modified and change it to the new element in a flash, so the time complexity is O(1).

Do not know the index of the element to be modified: If you do not know the index, you can use the find method to find the index location and then modify it, so this case is O(n) time.

Time complexity analysis for lookup operations

For query operations, three methods get, contains, and find are implemented:

Get: This method uses the index to get elements, and the time complexity is O(1).

Contains: This method is to determine the existence of elements one by one, the time complexity is O(n).

Find: This method determines whether an element exists and finds its location one by one. The time complexity is O(n).

In general, if the index is known, the time complexity of the search operation is O(1); If the index is not known, the time complexity is O(n).

Looking at the add and remove operations again, if we always operate on the last element (addLast or removeLast), is the time still O(n)? Does the resize method affect?

Some simple analyses can be made:

Let’s start with the resize method. Does this affect the performance of the array every time an element is added or removed? Obviously not, it is not triggered every time an add or remove operation is performed for Reszie.
For example, if an array has an initial size of 10, it takes 10 additions to resize once, then 20, then 10 more additions to resize again, and then 40, It takes 20 add operations before the resize method is executed again.
Normally, n add operations are required to trigger one add operationresizeMethods.

Then the following analysis is carried out:

Suppose the array has a current capacity of 10 and addLast is used for each addition:
The first ten additions were done without any problems, and the addLast operation was done 10 times.
On the eleventh add, a resize method is triggered, at which point 10 elements are copied and 10 basic operations are performed.
After the resize method is executed, the eleventh element is added, at which point the addLast operation is performed.
So up to this point, there have been 11 addLast operations, one resize, and a total of 21 basic operations.
So on average, for every addLast operation, there are about two base operations. Time complexity is O(1).

The above can be summarized as follows:

Let’s say the array size is n, n+1 timesaddLastTo triggerresize, a total of 2n+1 basic operations, average eachaddLastThe operation performs about two basic operations, so the amortized calculation is O(1) time.

In the same way,removeLastThe amortized complexity of the operation is also O(1).

However, there was a special case in our previous code implementation where addLast and removeLast operations were performed simultaneously (complexity flapping).

Take an example:

Assuming the current array is full of n, an addLast operation will trigger a resize method to expand the array to 2N, followed by a removeLast operation. If the number of elements is half of 2n, resize is triggered again, addLast is executed again, removeLast is executed again, and so on, resize is triggered all the time, O(n) each time. Instead of triggering the resize method once every n additions, as previously analyzed, the complexity is no longer amortized, which is the complexity oscillation (from O(1) to O(n)).

In this case, some improvements need to be made. From the example above, we can see the reason for this special situation: When removeLast triggers resize too quickly.

That is, when the number of elements is half of the current capacity, the operation is performed to reduce the capacity to half, at this time the capacity is full, then add another element naturally trigger the resize method again to expand.

So you can modify it like this: For removeLast procedures, realize the judgment of the original number of elements is equal to half of the capacity is modifying the operation of the capacity reduction for when the element number is equal to the capacity of 1/4 to reduce capacity operation, reduce the capacity of the original half, like this after reducing capacity, also reserved half space is used to add elements, to avoid the complexity of the above.

If the size of the array is 1, the parameter passed into resize is 1/2=0. In this case, a new array with 0 space will be created, so we need to avoid this situation:

/** * removes the element at index position from the array and returns the deleted element **@paramIndex Indicates the index * of the element to be deleted@returnReturns the deleted element */
public E remove(int index) {
    // Check whether index is valid
    if (index < 0 || index >= size) {
        throw new IllegalArgumentException("Failed to delete element at specified location, index should be in range [0, size]!");
    }

    // Store the element to be deleted for return
    E removeElement = data[index];

    // Delete
    for (int i = index + 1; i < size; i++) {
        data[i - 1] = data[i];
    }

    Size / / maintenance
    size--;

    // Release references at size to avoid object drift
    data[size] = null;

    // Perform capacity reduction when size == capacity / 4
    if (size == data.length / 4 && data.length / 2! =0) {
        // Reduce the capacity by half
        resize(data.length / 2);
    }

    // Returns the deleted element
    return removeElement;
}
Copy the code

At this point, the array class is wrapped. In general, the class implements an array data structure based on a static array that supports adding, deleting, changing, and viewing data, dynamically changing array space, and storing data of “arbitrary” data types.

If there is insufficient writing, please forgive me, please give more advice.

My personal blog website:www.xilikeli.cnWelcome to visit (#.#)

And welcome to mineMaking the home page, my personal blog has been open source, interested partners can dot star, thank you (#.#)

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

Detailed analysis of dynamic array data structure implementation process (Java implementation)

Dynamic array data structure implementation process (Java implementation)

A brief review of array basics

Secondary wrapper array class design

The basic design

Adds elements to an array

Adds elements to the end of the array

Adds an element to the array at the specified index location

Query and modify elements in an array

Contains, searches, and deletes elements from an array

Using generics to make the class more generic (able to hold data of “arbitrary” data types)

Upgrade to a dynamic array

Expand when the array space is full

When the array space is small enough to reduce the size

Simple time complexity analysis with some improvements

Time complexity analysis for add operations

Time complexity analysis of delete operations

Time complexity analysis for modification operations

Time complexity analysis for lookup operations

Detailed analysis of dynamic array data structure implementation process (Java implementation)

Dynamic array data structure implementation process (Java implementation)

A brief review of array basics

Secondary wrapper array class design

The basic design

Adds elements to an array

Adds elements to the end of the array

Adds an element to the array at the specified index location

Query and modify elements in an array

Contains, searches, and deletes elements from an array

Using generics to make the class more generic (able to hold data of “arbitrary” data types)

Upgrade to a dynamic array

Expand when the array space is full

When the array space is small enough to reduce the size

Simple time complexity analysis with some improvements

Time complexity analysis for add operations

Time complexity analysis of delete operations

Time complexity analysis for modification operations

Time complexity analysis for lookup operations

Related Posts

ACM player illustration LeetCode sliding window Max

C language information representation

Core Java – 9.3.1 LinkedList