Java implements custom dynamic arrays

Array Basics review

1. Arrays are a common data structure used to store collections of values of the same type

2. An array is a container for storing data of a fixed length, ensuring that the data types of multiple data are consistent

3. An array is a sequential linear list with contiguous memory addresses for all elements

4, for example: new an array of basic type int array

• int[] array = new int[] {11.22.33};
  Copy the code

• 

5. Advantages and disadvantages of arrays

• Arrays have very high random access capability, and the value can be read by array subscript
• The insertion and deletion of elements in an array causes a large number of element movements
• The size of the array is fixed and cannot be dynamically expanded. In real development, we would prefer that the size of the array be dynamically changed
• Summary – Arrays are suitable for scenarios where there are many reads and few writes

Custom dynamic array

Dynamic array design

/** * The number of elements */
protected int size;
/** * all elements and memory addresses point to */
private E[] elements;
Copy the code

Illustrated structure:

Abstract superclass interface design

The attributes and methods common to dynamic array and linked list are extracted as abstract classes to improve reusability

Abstract superclass interfaceList

public interface List<E> {

    // check the return flag of no element
    int ELEMENT_NOT_FOUND = -1;
    
    /** * Number of elements *@return* /
    int size(a);

    /** * is null *@return* /
    boolean isEmpty(a);

    /** * Sets the element * at index position@param index
     * @param element
     * @returnThe original element ֵ */
    E set(int index, E element);

    /** * gets the element * at index position@param index
     * @return* /
    E get(int index);

    /** * Whether to contain an element *@param element
     * @return* /
    boolean contains(E element);

    /** * View the index of the element *@param element
     * @return* /
    int indexOf(E element);

    /** * add the element to the end *@param element
     */
    void add(E element);


    /** * inserts an element * at index position@param index
     * @param element
     */
    void add(int index, E element);

    /** * delete element * at index position@param index
     * @return* /
    E remove(int index);

    /** * removes the specified element *@param element
     * @return* /
    public E remove(E element);

    /** * clears all elements */
    void clear(a);
Copy the code

Abstract superclass design

Abstract parent classAbstractListIs the interfaceListThe implementation of the

public abstract class AbstractList<E> implements List<E>  {
    /** * The number of elements */
    protected int size;

    /** * Number of elements *@return* /
    public int size(a) {
        return size;
    }

    /** * is null *@return* /
    public boolean isEmpty(a) {
        return size == 0;
    }

    /** * Whether to contain an element *@param element
     * @return* /
    public boolean contains(E element) {
        returnindexOf(element) ! = ELEMENT_NOT_FOUND; }/** * add the element to the end *@param element
     */
    public void add(E element) {
        add(size, element);
    }

    /** * Invalid index access array exception *@param index
     */
    protected void outOfBounds(int index) {
        throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
    }

    /** * index check function *@param index
     */
    protected void rangeCheck(int index) {
        if (index < 0|| index >= size) { outOfBounds(index); }}/** * array adds element index check function *@param index
     */
    protected void rangeCheckForAdd(int index) {
        //index > size, the element can be added to the array size, that is, the next storage location at the end of the array
        if (index < 0|| index > size) { outOfBounds(index); }}}Copy the code

DynamicArray of dynamic arrays

public class DynamicArray<E> extends AbstractList<E> {

    /** * all elements and memory addresses point to */
    private E[] elements;

    // Default initialization value for array
    private static final int DEFAULT_CAPACITY = 10;

    /** * takes an array initialization value *@param capacity
     */
    public DynamicArray(int capacity) {

        // If capacity> the default initial value, take capacity; otherwise, take the default value
        capacity = Math.max(capacity, DEFAULT_CAPACITY);
        // With new Object[], dynamic arrays can achieve multiple objects
        elements = (E[]) new Object[capacity];
    }

    /** * constructor to initialize the array */
    public DynamicArray(a) {
        this(DEFAULT_CAPACITY);
    }

    /** * sets the element value * at index position@param index
     * @param element
     * @return old
     */
    public E set(int index,E element){
        // Check whether the index is valid
        rangeCheck(index);

        //
        E old = elements[index];
        elements[index] = element;
        return old;
    }

    /** * gets the element * at position index of array@param index
     * @returnelements[index]; * /
    public E get(int index){
        rangeCheck(index);
        return elements[index];
    }

    /** * View the index of the element *@param element
     * @return* /
    public int indexOf(E element){
        // If the element is empty, judge separately to prevent NPE
        if (element == null) {for (int i = 0; i < size; i++){if (elements[i] == null) returni; }}else {
        // The element is not empty
            for (int i = 0; i < size; i++){if (element.equals(elements[i])) returni; }}// There is no such element
        return ELEMENT_NOT_FOUND;
    }

    /** * adds an element to the array at the specified position *@param index
     * @param element
     */
    public void add(int index,E element){
        // Check whether the index is valid
        rangeCheckForAdd(index);
        // Check whether the array is large enough
        ensureCapacity(size + 1);

        for (inti = size; i > index; i--){ elements[i] = elements[i -1];
        }
        elements[index] = element;
        size++;
    }

    /** * removes the specified element *@param element
     * @return* /
    public E remove(E element){
        // Call indexOf to get the index, which deletes the specified element
        return remove(indexOf(element));
    }

    /** * removes the element * at the index position@param index
     * @return* /
    public E remove(int index){
        // Check whether the index is valid
        rangeCheck(index);

        E old = elements[index];
        for (int i = index + 1; i < size; i++){ elements[i -1] = elements[i];
        }
        // Set the position of the last element at the end of the array to null, freeing the memory corresponding to the original address reference
        elements[--size] = null;
        // Check whether the capacity needs to be reduced
        trim();
        return old;
    }

    /** * clears all elements */
    public void clear(a) {
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }
        size = 0;
    }

    /** * ensure that there is a capacity **@param capacity
     */
    private void ensureCapacity(int capacity){
        int oldCapacity = elements.length;
        // Return if the array is large enough
        if (oldCapacity >= capacity) return;

        // Otherwise, the array is expanded by 1.5 times
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        E[] newElements = (E[]) new Object[newCapacity];
        // Copy the elements of the original array into the new array
        for (int i = 0; i < size; i++){ newElements[i] = elements[i]; }// Point to a new array
        elements = newElements;
        System.out.println(oldCapacity + "Expand to" + newCapacity);
    }

    /** * override toString to print array *@return* /
    @Override
    public String toString(a) {
        // size=3, [99, 88, 77]
        StringBuilder string = new StringBuilder();
        string.append("size=").append(size).append("[");
        for (int i = 0; i < size; i++) {
            if(i ! =0) {
                string.append(",");
            }
            string.append(elements[i]);
        }
        string.append("]");
        returnstring.toString(); }}Copy the code

Add an array shrink

Each time an array element is deleted and emptied, a reduction check is performed

/** * If the memory usage is tight and the dynamic array has a lot of free space, you can consider reducing the size of the array * for example: After the expansion of the array is very large, after the deletion operation, the number of elements in the array is not many, but the space of the array is large enough * for example, when the remaining space occupies half of the total capacity, the size is reduced (the rule can be customized) */
private void trim(a){
    int oldCapacity = elements.length;
    int newCapacity = oldCapacity >> 1;

    // If the number of elements is greater than the size of the array, or smaller than the initial size, no scaling is performed
    if (size >= (newCapacity) || size <= DEFAULT_CAPACITY) return;;

    // There is plenty of space left
    E[] newElements = (E[]) new Object[newCapacity];
    for (int i = 0; i < size; i++) {
        newElements[i] = elements[i];
    }
    elements = newElements;

    System.out.println(oldCapacity + "Shrink to" + newCapacity);
}
Copy the code

/** * clears all elements */
public void clear(a) {

    // Empty the array, should be reduced according to the situation, to avoid memory waste
    if(elements ! =null && elements.length > DEFAULT_CAPACITY) {
        elements = (E[]) new Object[DEFAULT_CAPACITY];
    }else {
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }
    }
    size = 0;
}
Copy the code

The global diagram

The statement

Personal ability is limited, have incorrect place, also please correct

The article is original, welcome to reprint, just indicate the source

The code for this article has been uploadedgithub, welcomestar

GitHubaddress