一篇文章搞定ArrayList和LinkedList所有面试问题
在面试中经常碰到：ArrayList和LinkedList的特点和区别？
这个问题的回答应该分成这几部分
- 介绍ArrayList底层实现
- 介绍LinkedList底层实现
- 两者个适用于哪些场合
ArrayList的源码解读
public class ArrayList
extends AbstractList implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final long serialVersionUID = 8683452581122892189L;/*** Default initial capacity.*///默认容量是10private static final int DEFAULT_CAPACITY = 10;/*** Shared empty array instance used for empty instances.*///当传入ArrayList构造器的容量为0时用这个数组表示：容器的容量为0private static final Object[] EMPTY_ELEMENTDATA = {};/*** Shared empty array instance used for default sized empty instances. We* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when* first element is added.*///主要作为一个标识位，在扩容时区分：默认大小和容量为0，使用默认容量时采取的是“懒加载”//即等到add元素的时候才进行实际容量的分配，后面扩容函数讲解还会提到这private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};/*** The array buffer into which the elements of the ArrayList are stored.* The capacity of the ArrayList is the length of this array buffer. Any* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA* will be expanded to DEFAULT_CAPACITY when the first element is added.*///ArrayList底层使用Object数组保存的元素的transient Object[] elementData; // non-private to simplify nested class access/*** The size of the ArrayList (the number of elements it contains).** @serial*///记录当前容器中有多少元素private int size;//最常用的构造器之一，实际上就是创建了一个指定大小的Object数组来保存之后add的元素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);}}
//无参构造器，指向的是默认容量大小的Object数组，注意使用无参构造函数的时候并没有直接创建容量
//为10的Object数组,而是采取懒加载的策略：使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA（实际容量为0）
//作为标识，在真正add元素时才会开辟Object数组，即在扩容函数中有处理默认容量的逻辑，后面会有分析public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}
//省略一部分不常用代码函数
//add是ArrayList最常用的接口，逻辑很简单，public boolean add(E e) {//主要用于标识线程安全，即ArrayList只能在单线程环境下使用，在多线程环境下会出现并发安全问//题，modCount主要用于记录对ArrayList的修改次数，如果一个线程操作期间modCount发生了变化//即，有多个线程同时修改当前这个ArrayList，此时会抛出“ConcurrentModificationException”//异常，这又被称为“failFast机制”，在很多非线程安全的类中都有failFast机制：HashMap、//LinkedList等。这个机制主要用于迭代器、加强for循环等相关功能，也就是一个线程在迭代一个容器//时，如果其他线程改变了容器内的元素，迭代的这个线程会抛//出“ConcurrentModificationException”异常modCount++;//add操作的核心函数，当使用无参构造器时并没有直接分配大小为10的Object数组，这里面有对应//的处理逻辑add(e, elementData, size);return true;}private void add(E e, Object[] elementData, int s) {if (s == elementData.length)//如果使用无参构造器：开始时length为0，s也为0elementData = grow();//核心函数elementData[s] = e;size = s + 1;}private Object[] grow() {return grow(size + 1);//继续追踪}private Object[] grow(int minCapacity) {//使用数组复制的方式，扩容：将elementData所有元素复制到一个新数组中，这个新数组的长度是//newCapacity()函数的返回值，之后再把这个新数组赋值给elementData，完成扩容//进入newCapacity()函数return elementData = Arrays.copyOf(elementData,newCapacity(minCapacity));}private int newCapacity(int minCapacity) {//返回的是扩容后数组的长度// overflow-conscious codeint oldCapacity = elementData.length;int newCapacity = oldCapacity + (oldCapacity >> 1);//扩容后为原来容量的1.5倍if (newCapacity - minCapacity <= 0) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)//默认容量的处理return Math.max(DEFAULT_CAPACITY, minCapacity);//minCapacity是int类型，有溢出的可能，也就是ArrayList最大大小是Integer.MAX_VALUEif (minCapacity < 0) // overflowthrow new OutOfMemoryError();return minCapacity;}//MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8,当扩容后大于MAX_ARRAY_SIZE ，返回//hugeCapacity(minCapacity),其实就是Integer.MAX_VALUEreturn (newCapacity - MAX_ARRAY_SIZE <= 0)? newCapacity: hugeCapacity(minCapacity);}private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflowthrow new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE)? Integer.MAX_VALUE: MAX_ARRAY_SIZE;}//最后看下ArrayList的failFast机制private class Itr implements Iterator<E> {int cursor; // index of next element to returnint lastRet = -1; // index of last element returned; -1 if no such//在迭代之前先保存modCount的值，modCount在改变容器元素、容器大小时会自增int expectedModCount = modCount;// prevent creating a synthetic constructorItr() {}public boolean hasNext() {return cursor != size;}@SuppressWarnings("unchecked")public E next() {//使用迭代器遍历元素的时候先检查modCount的值是否等于预期的值，进入该函数checkForComodification();int i = cursor;if (i >= size)throw new NoSuchElementException();Object[] elementData = ArrayList.this.elementData;if (i >= elementData.length)throw new ConcurrentModificationException();cursor = i + 1;return (E) elementData[lastRet = i];}//可以发现：在迭代期间如果有线程改变了容器，此时会抛出“ConcurrentModificationException”final void checkForComodification() {if (modCount != expectedModCount)throw new ConcurrentModificationException();}ArrayList的其他操作：get、remove、indexOf其实就很简单了，都是对Object数组的操作：获取数组某个索引位置的元素，删除数组中某个元素，查找数组中某个元素的位置......所以说理解原理很重要上面注释的部分就是ArrayList的考点，主要有：初始容量、最大容量、使用Object数组保存元素（数组与链表的异同）、扩容机制（1.5倍）、failFast机制 等
LinkedList源码分析
public class LinkedList
extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
//LinkedList的size是int类型，但是后面会看到LinkedList大小实际只受内存大小的限制//也就是LinkedList的size大小可能发生溢出，返回负数transient int size = 0;/*** Pointer to first node.*///LinkedList底层使用双向链表实现，并保留了头尾两个节点的引用transient Node<E> first;//头节点/*** Pointer to last node.*/transient Node<E> last;//尾节点
//省略一部分无关代码，LinkedList内部类Nodeprivate static class Node<E> {E item;//元素值Node<E> next;//后继节点Node<E> prev;//前驱节点,即Node是双向链表Node(Node<E> prev, E element, Node<E> next) {//Node的构造器this.item = element;this.next = next;this.prev = prev;}}//LinkedList无参构造器：什么都没做public LinkedList() {}//LinkedList的大部分接口都是基于这几个接口实现的：//1.往链表头部插入元素//2.往链表尾部插入元素//3.在指定节点的前面插入一个节点//4.删除链表的头结点//5.删除除链表的尾节点//6.删除除链表中的指定节点private void linkFirst(E e) {//1.往链表头部插入元素final Node<E> f = first;final Node<E> newNode = new Node<>(null, e, f);first = newNode;if (f == null)last = newNode;elsef.prev = newNode;size++;modCount++;//failFast机制}/*** Links e as last element.*/void linkLast(E e) {//2.往链表尾部插入元素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++;//failFast机制}/*** Inserts element e before non-null Node succ.*/void linkBefore(E e, Node<E> succ) {//3.在指定节点(succ)的前面插入一个节点// assert succ != null;final Node<E> pred = succ.prev;final Node<E> newNode = new Node<>(pred, e, succ);succ.prev = newNode;if (pred == null)first = newNode;elsepred.next = newNode;size++;modCount++;//failFast机制}/*** Unlinks non-null first node f.*/private E unlinkFirst(Node<E> f) {//4.删除链表的头结点// assert f == first && f != null;final E element = f.item;final Node<E> next = f.next;f.item = null;f.next = null; // help GCfirst = next;if (next == null)last = null;elsenext.prev = null;size--;modCount++;//failFast机制return element;}/*** Unlinks non-null last node l.*/private E unlinkLast(Node<E> l) {//5.删除除链表的尾节点// assert l == last && l != null;final E element = l.item;final Node<E> prev = l.prev;l.item = null;l.prev = null; // help GClast = prev;if (prev == null)first = null;elseprev.next = null;size--;modCount++;//failFast机制return element;}/*** Unlinks non-null node x.*/E unlink(Node<E> x) {//6.删除除链表中的指定节点// 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++;//failFast机制return element;}//LinkedList常用接口的实现public E removeFirst() {final Node<E> f = first;if (f == null)throw new NoSuchElementException();return unlinkFirst(f);//调用 4.删除链表的头结点 实现}public E removeLast() {final Node<E> l = last;if (l == null)throw new NoSuchElementException();return unlinkLast(l);//调用 5.删除除链表的尾节点 实现}public void addFirst(E e) {linkFirst(e);//调用 1.往链表头部插入元素 实现}public void addLast(E e) {linkLast(e);//调用 2.往链表尾部插入元素 实现}public boolean add(E e) {linkLast(e);//调用 2.往链表尾部插入元素 实现return true;}public boolean remove(Object o) {if (o == null) {for (Node<E> x = first; x != null; x = x.next) {if (x.item == null) {unlink(x);//调用 6.删除除链表中的指定节点 实现return true;}}} else {for (Node<E> x = first; x != null; x = x.next) {if (o.equals(x.item)) {unlink(x);//调用 6.删除除链表中的指定节点 实现return true;}}}return false;}//省略其他无关函数//迭代器中的failFast机制private class ListItr implements ListIterator<E> {private Node<E> lastReturned;private Node<E> next;private int nextIndex;//在迭代之前先保存modCount的值，modCount在改变容器元素、容器大小时会自增private int expectedModCount = modCount;ListItr(int index) {// assert isPositionIndex(index);next = (index == size) ? null : node(index);nextIndex = index;}public boolean hasNext() {return nextIndex < size;}public E next() {使用迭代器遍历元素的时候先检查modCount的值是否等于预期的值，进入该函数checkForComodification();if (!hasNext())throw new NoSuchElementException();lastReturned = next;next = next.next;nextIndex++;return lastReturned.item;}//可以发现：在迭代期间如果有线程改变了容器，此时会抛出“ConcurrentModificationException”final void checkForComodification() {if (modCount != expectedModCount)throw new ConcurrentModificationException();}LinkedList的实现较为简单：底层使用双向链表实现、保留了头尾两个指针、LinkedList的其他操作基本都是基于上面那7个函数实现的，另外LinkedList也有FailFast机制：这个机制主要在迭代器中会使用。
- 数组和链表各自的特性
数组和链表的特性差异，本质是：连续空间存储和非连续空间存储的差异，主要有下面两点：
- ArrayList：底层是Object数组实现的：由于数组的地址是连续的，数组支持O(1)随机访问；数组在初始化时需要指定容量；数组不支持动态扩容，像ArrayList、Vector和Stack使用的时候看似不用考虑容量问题（因为可以一直往里面存放数据）；但是它们的底层实际做了扩容；数组扩容代价比较大，需要开辟一个新数组将数据拷贝进去，数组扩容效率低；适合读数据较多的场合
- LinkedList：底层使用一个Node数据结构，有前后两个指针，双向链表实现的。相对数组，链表插入效率较高，只需要更改前后两个指针即可；另外链表不存在扩容问题，因为链表不要求存储空间连续，每次插入数据都只是改变last指针；另外，链表所需要的内存比数组要多，因为他要维护前后两个指针；它适合删除，插入较多的场景。另外，LinkedList还实现了Deque接口。
扫描下方二维码，及时获取更多互联网求职面经、java、python、爬虫、大数据等技术，和海量资料分享：
公众号菜鸟名企梦后台发送“csdn”即可免费领取【csdn】和【百度文库】下载服务；
公众号菜鸟名企梦后台发送“资料”:即可领取5T精品学习资料、java面试考点和java面经总结，以及几十个java、大数据项目，资料很全，你想找的几乎都有
扫码关注，及时获取更多精彩内容。（博主今日头条大数据工程师）
妖狐艹你老母
左手的ㄟ右手
红太狼
今天药忘吃喽~
灰太狼
还没有评论，来说两句吧...