First, ArrayList and linkedlist are implementation classes of the List interface, and both are thread unsafe

ArrayList and linkedlist

1.ArrayList uses dynamic array to store data, and linkedlist uses bidirectional list to store data.

2.ArrayList can be accessed randomly through the address, and linkedlist can only be accessed by moving the pointer

3.ArrayList has a length limit. The default length is 10. When the length limit is exceeded, it needs to be expanded

When are ArrayList and linkedlist used

Because ArrayList uses dynamic arrays to store data and can be accessed randomly through addresses, linkedlist needs to move the pointer. Therefore, when querying data, ArrayList is much faster than linkedlist.

For add and remove operations, it is generally said that linkedlist is faster than ArrayList, but this is not necessarily the case.

ArrayList needs to move the data behind the index when adding and deleting, which is the main reason affecting its speed. linkedlist needs to iterate first to find the location to be added or deleted. When there is little data, linkedlist can quickly find the location to be operated, so the speed will be faster than ArrayList. However, when there is a large amount of data, if the location to be operated is later, it may take a lot of time for linkedlist to move the pointer, ArrayList may only take a small amount of time to move data.

In summary, it is generally recommended to use ArrayList. When there are many array insertion and deletion operations, a large amount of data, and the operation position is determined to be in the front, you can choose linkedlist.

ArrayList capacity expansion mechanism

1.ArrayList has three constructors. Different constructors will affect the judgment of capacity expansion mechanism
The code is as follows

    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }


   public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

2. When adding, you will judge whether the array can add data or whether the array has been initialized

  public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }


  public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

 private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    
 private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
 private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

ArrayList first determines whether another element can be added through the ensureCapacityInternal method. There is a calculateCapacity method in ensureCapacityInternal. This method will judge whether the array has been initialized. If not, it will compare the size of the new address and the default address, and then judge whether the array needs to be expanded through ensureExplicitCapacity

   private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

During capacity expansion, first obtain the length of the old array, then expand it by 1.5 times, and finally create a new ArrayList through the third construction method and newCapacity.