Hi, my name is ArrayList. I was created by Josh Bloch and Neal Gafter in JDK1.2. Here is my “genetic sequence” (interface to inheritance)

Also, I have many brothers and sisters, and I will introduce them one by one in the future:

  • LinkedList
  • Vector
  • .

Interpretation of the self

First, I’m a Java world implementation of an array, a data structure. And I’m a dynamic array that’s inherently scalable.

So, I’m going to talk a little bit about what an array is, and then I’m going to go into a little bit more detail about how I automatically expand it.

An array of

See, this is a one-dimensional array. It is a continuous space and cannot be expanded. Elements of the same data type are arranged in order, and each element has a subscript. The index starts at 0.

In Java, you can create an array using the following methods.

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

Multidimensional array

Since we have one-dimensional arrays, we have multidimensional arrays. As the figure above shows, a theory can create arrays with no number of dimensions.

The rest of the operation is basically the same as a one-bit array. To put it bluntly, Russian nesting dolls

In Java, you can create multidimensional arrays using the following methods.

    int[][] _2DArray = {{1.2}, {3.4}};
Copy the code

To find the

Since arrays have subscripts, if you have the subscript of the element. So you find that element very quickly, in order one time.

If you don’t understand what time complexity is, click the portal.

But if you don’t have a subscript, it’s unfortunate. You need to go through all the nodes to find the element you want. The time complexity is O(n). There may be algorithms that can help you, but that’s beyond the scope of this article.

In Java, you can use the subscript to get.

class Scratch {
    public static void main(String[] args) {
        int[] array = new int[] {99.88.77.66.55};
        System.out.println(array[0]); // output is 99}}Copy the code

You can also iterate through foreach to find the desired element.

class Scratch {
    public static void main(String[] args) {
        int[] array = new int[] {99.88.77.66.55};
        Integer ninety_nine = findNinetyNine(array);
        if(ninety_nine ! =null)
            System.out.println(ninety_nine);  // output is 99
        System.out.println("Can not found 99!");
    }

    private static Integer findNinetyNine(int[] array) {
        for (int i : array) 
            if (i == 99) return i;
        return null; }}Copy the code

add

Since the array is allocated memory each time, no elements are allowed to be added. But you can do that by reassigning the value to a new array.

delete

Deleting an array simply sets the elements of the array to null, but it does not adjust the length of the array after deleting.

The dynamic array

Now that we know what an array is, we know the general pros and cons:

Advantages:

  • The elements in an array are arranged in order
  • Arrays depend on subscriptsindexWhen indexing, the time complexity isO(1)

Disadvantages:

  • Arrays do not support dynamic node addition or capacity expansion
  • The array length cannot be automatically adjusted after a node is deleted

To address the above shortcomings, dynamic arrays come into being.

In the Java world, I’m a standard implementation of dynamic arrays. Next I and everyone together to analyze how I achieve automatic expansion and delete after adjusting the length of it ~

Automatic expansion

The theory of

In theory, it’s very simple. We apply for a memory space in advance. Each time we add a node, we determine whether the current node reaches our maximum length, and if so, we can expand it.

practice

Open my (ArrayList) source code, there is an add method that describes this process in detail. We’ve taken snippets of code for brevity.

/** * This helper method split out from add(E) to keep method * bytecode size under 35 (the -XX:MaxInlineSize default value), * which helps when add(E) is called in a C1-compiled loop. */
    private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length)  / / (1)
            elementData = grow();     / / (2)
        elementData[s] = e;           / / (3)
        size = s + 1;                 / / (4)
    }
Copy the code
  • (1) Determine whether the current subscript exceeds the maximum length of the current array.
  • (2) Expand the array if it exceeds the maximum length
  • (3) Assign values
  • (4) Length + 1
/**
     * Increases the capacity to ensure that it can hold at least the
     * number of elements specified by the minimum capacity argument.
     *
     * @param minCapacity the desired minimum capacity
     * @throws OutOfMemoryError if minCapacity is less than zero
     */
    private Object[] grow(int minCapacity) {
        return elementData = Arrays.copyOf(elementData,             / / (1)
                                           newCapacity(minCapacity));
    }
    
    /**
     * Returns a capacity at least as large as the given minimum capacity.
     * Returns the current capacity increased by 50% if that suffices.
     * Will not return a capacity greater than MAX_ARRAY_SIZE unless
     * the given minimum capacity is greater than MAX_ARRAY_SIZE.
     *
     * @param minCapacity the desired minimum capacity
     * @throws OutOfMemoryError if minCapacity is less than zero
     */
    private int newCapacity(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;              
        int newCapacity = oldCapacity + (oldCapacity >> 1);       / / (2)
        if (newCapacity - minCapacity <= 0) {                     / / (3)
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return minCapacity;
        }
        return (newCapacity - MAX_ARRAY_SIZE <= 0)                / / (4)
            ? newCapacity
            : hugeCapacity(minCapacity);
    }
Copy the code
  • (1) Use the copyOf provided by Arrays to expand the capacity and become a bigger oneAn array of
  • (2) the capacity is the current array length plus the current array lengthI'm going to move to the right one bit.
  • (3) The initial array length is too small for compatibility
  • (4) For some particularly large array length compatibility

Automatic length change

In this case, let’s remove an element.

The theory of

When we perform the delete operation, we move all the elements following the subscript element forward and remove the last extra element. The length can be automatically changed when deleted.

practice

Open my (ArrayList) source code, there is a delete method to describe the process in detail. We’ve taken snippets of code for brevity.

/**
     * Removes the element at the specified position in this list.
     * Shifts any subsequent elements to the left (subtracts one from their
     * indices).
     *
     * @param index the index of the element to be removed
     * @return the element that was removed from the list
     * @throws IndexOutOfBoundsException {@inheritDoc} * /
    public E remove(int index) {
        Objects.checkIndex(index, size);  / / (1)
        final Object[] es = elementData; 

        E oldValue = (E) es[index];        
        fastRemove(es, index);           //  (2)

        return oldValue;
    }
Copy the code
  • (1) Check whether subscripts exist
  • (2) Delete the element
  /** * Private remove method that skips bounds checking and does not * return the value removed. */
    private void fastRemove(Object[] es, int i) {
        modCount++;
        final int newSize;
        if ((newSize = size - 1) > i)                       / / (1)
            System.arraycopy(es, i + 1, es, i, newSize - i); / / (2)
        es[size = newSize] = null;                          / / (3)
    }
Copy the code
  • (1) Determine whether it is the last element
  • (2) callNativeMethods theindexAll subsequent elements are moved forward (overridden by copy)
  • (3) Delete the last element

Adding a new element at a specified location is similar to deleting it, except that all elements at that location are copied and moved back. The value to be added is then assigned to the specified position.

conclusion

After my self-introduction, I believe that you have a deep understanding of me. And you already know how I implemented dynamic arrays. In the next article, I’ll introduce my sibling LinkedList, a linked list-based implementation.

reference

  • JDK8 official document: Oracle

  • Data structure — Array: DobbyKim