1. The difference between ArrayList and LinkedList mainly comes from the different data structures of Array and LinkedList. ArrayList is based on Array and LinkedList is based on double linked list. In addition, the LinkedList class does not
   It is only the implementation class of the List interface, which can randomly access the elements in the collection according to the index. In addition,
   LinkedList also implements the Deque interface, which is a sub interface of the Queue interface, which represents a two-way interface
   Queue, so LinkedList can be used as a bidirectional queue, stack (see the interface method provided by Deque) and List collection, and has powerful functions.
2. Because Array is an index based data structure, it is fast to search and read data in an Array using an index
   It can directly return the element at the index position in the array, so it has better performance in random access to collection elements.
   The time complexity for Array to obtain data is O(1), but it is very expensive to insert and delete data, because it requires
   To move all elements after the insertion position in the array.
3. Compared with ArrayList, LinkedList performs worse when randomly accessing collection elements because it needs to be in a bidirectional list
   Find the location to index and return; But in insert, delete is faster. Because LinkedList is not like
   Like ArrayList, there is no need to change the size of the array, and there is no need to reset all the data when the array is full
   A new array is newly loaded. This is the worst case of ArrayList. The time complexity is O(n), and
   The time complexity of insertion or deletion in LinkedList is only O(1). ArrayList also needs to update the index when inserting data
   Index (except inserting the tail of the array).
4. LinkedList requires more memory because the location of each index in ArrayList is the actual data, and
   Each node in the LinkedList stores the actual data and the location of the front and rear nodes.

ArrayList source code

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
	 transient Object[] elementData;
	 private int size;
	 
	public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    
 	public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

    E elementData(int index) {
        return (E) elementData[index];
    }
    
    public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }
 }

LinkedList source code

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
	transient int size = 0;
    transient Node<E> first;
    transient Node<E> last;
	
	public boolean add(E e) {
        linkLast(e);
        return true;
    }

	void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }
	
	Node<E> node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

	public boolean remove(Object o) {
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

	E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;

        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }

        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }

        x.item = null;
        size--;
        modCount++;
        return element;
    }

}