ArrayList

ArrayList 的底层是数组队列，相当于动态数组。与 Java 中的数组相比，它的容量能动态增长。ArrayList实现了List接口，是顺序容器，即元素存放的数据与放进去的顺序相同，允许放入null元素，底层通过数组实现。

add自动扩容

每当向数组中添加元素时，都要去检查添加后元素的个数是否会超出当前数组的长度，如果超出，数组将会进行扩容，以满足添加数据的需求：

 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 void ensureExplicitCapacity(int minCapacity) {modCount++;// overflow-conscious codeif (minCapacity - elementData.length > 0)grow(minCapacity);}private void grow(int minCapacity) {// overflow-conscious codeint 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);}

数组进行扩容时，会将老数组中的元素重新拷贝一份到新的数组中，每次数组容量的增长大约是其原容量的1.5倍(>> 1)。这种操作的代价是很高的，因此在实际使用时，我们应该尽量避免数组容量的扩张。

ArrayList的remove()方法

删除操作是add()操作的逆过程，需要将删除点之后的元素向前移动一个位置。需要注意的是为了让GC起作用，必须显式的为最后一个位置赋null值。

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; //清除该位置的引用，让GC起作用return oldValue;
}

查找 indexof

获取元素的第一次出现的index:

public int indexOf(Object o) {if (o == null) {for (int i = 0; i < size; i++)if (elementData[i]==null)return i;} else {for (int i = 0; i < size; i++)if (o.equals(elementData[i]))return i;}return -1;}

LinkedList

LinkedList同时实现了List接口和Deque接口，也就是说它既可以看作一个顺序容器，又可以看作一个队列(Queue)，同时又可以看作一个栈(Stack)。不过，关于栈或队列，现在的首选是ArrayDeque，它有着比LinkedList(当作栈或队列使用时)有着更好的性能。

 transient int size = 0;transient Node<E> first;transient Node<E> last;private static class Node<E> {E item;Node<E> next;Node<E> prev;Node(Node<E> prev, E element, Node<E> next) {this.item = element;this.next = next;this.prev = prev;}}

LinkedList的add方法

add()方法有两个版本，一个是add(E e)，该方法在LinkedList的末尾插入元素，因为有last指向链表末尾，在末尾插入元素的花费是常数时间。只需要简单修改几个相关引用即可；另一个是add(int index, E element)，该方法是在指定下表处插入元素，需要先通过线性查找找到具体位置，然后修改相关引用完成插入操作。

public boolean add(E e) {linkLast(e);return true;}/*** Links e as last element.*/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;elsel.next = newNode;size++;modCount++;}

LinkedList的remove方法

删除元素 - 指的是删除第一次出现的这个元素, 如果没有这个元素，则返回false；判断的依据是equals方法， 如果equals，则直接unlink这个node；由于LinkedList可存放null元素，故也可以删除第一次出现null的元素。
我们可以给出一些示例比如LinkedList存在6，7，8三个元素，实现即是：

1. 前一个节点的变化：6的下一个节点指向8，且断开7的上一个节点
2. 后一个节点的变化：8的上一个节点指向6，且断开7的下一个节点

 public E remove(int index) {checkElementIndex(index);return unlink(node(index));}/*** 从链表中移除非空节点x，并返回该节点存储的元素。* @param x 需要被移除的非空节点* @return 被移除节点存储的元素*/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 {// 将前一个节点的next指针指向当前节点的下一个节点prev.next = next;x.prev = null;}if (next == null) {last = prev;} else {// 将下一个节点的prev指针指向当前节点的前一个节点next.prev = prev;x.next = null;}
// // 清空节点的元素，以便垃圾回收x.item = null;// 更新链表大小size--;modCount++;return element;}

查找 indexof

在链表中查找指定元素首次出现的索引位置。如果链表中不存在该元素，则返回-1。

 public int indexOf(Object o) {int index = 0;if (o == null) {for (Node<E> x = first; x != null; x = x.next) {if (x.item == null)return index;index++;}} else {for (Node<E> x = first; x != null; x = x.next) {if (o.equals(x.item))return index;index++;}}return -1;}

arraylist和linkedlist的区别

ArrayList和LinkedList在数据结构、性能特点以及内存空间等方面存在显著差异。

1. 数据结构：ArrayList是基于动态数组实现的，而LinkedList是基于双向链表实现的。这导致它们在功能上和使用方式上有所不同。
2. 随机访问速度：由于ArrayList基于数组，可以直接通过数组下标以常数时间O(1)来访问元素，因此它在随机访问集合元素时性能更优。相比之下，LinkedList需要从头或尾遍历节点来找到特定位置的元素，这使得随机访问的时间复杂度为O(n)，较慢于ArrayList。
3. 插入和删除操作：LinkedList在插入和删除操作上具有优势，因为它只需要改变节点指针，不需要移动其他元素。其插入和删除的时间复杂度为O(1)，而ArrayList在插入和删除时需要移动数组中的其他元素，时间复杂度为O(n)。
4. 内存空间：LinkedList的每个元素需要额外的空间存储前后节点的地址信息，因此它比ArrayList占用更多的内存空间。
5. 线程安全性：ArrayList不是线程安全的，而Vector是它的同步版本，是线程安全的。相反，LinkedList也不是线程安全的。
6. 功能多样性：除了作为List接口的实现类外，LinkedList还实现了Deque接口，可以作为栈、队列和双端队列使用，因此在功能上更为多样。

总的来说，如果应用程序对数据的随机访问需求较多，则ArrayList的性能较优；而如果应用程序中插入和删除操作更为频繁，则LinkedList可能更加适合。选择ArrayList还是LinkedList取决于具体的应用场景。