在Java中，ArrayList和LinkedList是两种常见的汇合类。它们都实现了List接口，提供了相似数组的性能，能够存储任意类型的对象。尽管它们都能够实现雷同的性能，然而它们的底层实现形式有所不同，因而在性能和用处上也存在一些差别。
ArrayList
ArrayList是一个基于数组实现的动静数组，它能够主动扩大容量以包容新的元素。在ArrayList中，元素存储在一个Object数组中，能够通过索引拜访数组中的元素。
底层原理
ArrayList底层应用数组实现，每个ArrayList实例都蕴含一个Object类型的数组elementData，用于存储元素。当ArrayList中的元素数量超过数组容量时，ArrayList会主动扩容，创立一个新的数组，并将原数组中的元素复制到新数组中。
private transient Object[] elementData;在ArrayList中，增加元素的操作能够分为两种状况：
- 如果数组容量足够，间接将元素增加到数组开端。
- 如果数组容量有余，须要先对数组进行扩容，而后将元素增加到数组开端。
public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true;}private void ensureCapacityInternal(int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity);}private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity);}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);}在ArrayList中，删除元素的操作能够分为两种状况：
- 如果要删除的元素在数组两头，须要将后续的元素向前挪动，笼罩要删除的元素。
- 如果要删除的元素在数组开端，间接将数组长度减一即可。
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;}特点
- ArrayList是一个基于数组实现的动静数组，能够主动扩容以包容新的元素。
- 在ArrayList中，元素能够通过索引拜访，因而随机拜访效率较高。
- 在ArrayList中，插入和删除操作可能须要挪动后续的元素，因而效率较低。
源码
ArrayList的源码能够在JDK中找到，位于java.util包中。
LinkedList
LinkedList是一个基于链表实现的双向链表，它能够动静地增加、删除元素。在LinkedList中，元素存储在一个节点(Node)中，每个节点蕴含一个元素和前后指针。
底层原理
LinkedList底层应用双向链表实现，每个LinkedList实例都蕴含一个Node类型的first和last节点，用于示意链表的头和尾。
java
Copy
private transient Node<E> first;private transient Node<E> last;在LinkedList中，增加元素的操作能够分为三种状况：
- 如果链表为空，将新节点设置为first和last节点。
- 如果要增加的元素在链表头部，将新节点设置为first节点，并将原first节点作为新节点的后继。
- 如果要增加的元素在链表尾部，将新节点设置为last节点，并将原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++;}在LinkedList中，删除元素的操作能够分为三种状况：
- 如果要删除的元素是first节点，将first节点设置为原first节点的后继。
- 如果要删除的元素是last节点，将last节点设置为原last节点的前驱。
- 如果要删除的元素在链表两头，将要删除的节点的前驱和后继节点连接起来，而后将要删除的节点的前驱和后继节点别离指向要删除节点的前驱和后继节点。
public E remove(int index) { checkElementIndex(index); return unlink(node(index));}E unlink(Node<E> x) { 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;}特点
- LinkedList是一个基于链表实现的双向链表，能够动静地增加、删除元素。
- 在LinkedList中，元素不能通过索引拜访，因而随机拜访效率较低。
- 在LinkedList中，插入和删除操作只须要扭转相邻节点的指针，因而效率较高。
源码
LinkedList的源码能够在JDK中找到，位于java.util包中。
ArrayList和LinkedList的比拟
从底层实现上来看，ArrayList和LinkedList有以下区别：
- ArrayList底层应用数组实现，LinkedList底层应用链表实现。
- 在ArrayList中，元素能够通过索引拜访，因而随机拜访效率较高，然而插入和删除操作效率较低。在LinkedList中，元素不能通过索引拜访，因而随机拜访效率较低，然而插入和删除操作效率较高。
- 在ArrayList中，增加和删除操作须要挪动后续的元素，因而效率较低。在LinkedList中，增加和删除操作只须要扭转相邻节点的指针，因而效率较高。
- 在ArrayList中，扩容时须要创立一个新的数组，并将原数组中的元素复制到新数组中，效率较低。在LinkedList中，不须要扩容，因为链表能够动静地增加、删除节点。
因为ArrayList和LinkedList的底层实现形式不同，因而它们实用的场景也不同：
- 如果须要频繁拜访汇合中的元素，并且汇合的大小不会常常扭转，抉择ArrayList会更加适合，因为ArrayList能够通过索引快速访问元素，效率较高。
- 如果须要频繁增加、删除汇合中的元素，抉择LinkedList会更加适合，因为LinkedList能够疾速地增加、删除节点，效率较高。
总结
ArrayList和LinkedList是Java中常见的汇合类，它们都实现了List接口，提供了相似数组的性能，能够存储任意类型的对象。ArrayList底层应用数组实现，LinkedList底层应用链表实现。