ArrayList和LinkedList都是List的实现类，是在日常开发中经常被使用到的两个集合，我们来结合源码看下两个集合的不同之处。
先来看下ArrayList的源码：
//默认的初始化大小privatestaticfinalintDEFAULT_CAPACITY=10;
ArrayList的底层数数组结构，我们创建ArrayList的时候，可以使用指定数组大小的构造函数或者直接是默认的构造函数。当使用默认构造函数的时候，数组的初始化大小是0，当第一次调用add()方法的时候，会变成默认的初始化大小10。
使用ArrayList的最多的就是add()方法了，我们直接来看add()方法的源码：
publicbooleanadd(Ee){//调用ensureCapacityInternal()看是否需要初始化以及扩容ensureCapacityInternal(size+1);//IncrementsmodCount!!//将数据添加到数组中elementData[size++]=e;returntrue;}
来看ensureCapacityInternal()方法：
privatevoidensureCapacityInternal(intminCapacity){//如果elementData为空，也就是第一次add的话，则返回默认容量和minCapacity中的最大值if(elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA){minCapacity=Math.max(DEFAULT_CAPACITY,minCapacity);}//ensureExplicitCapacity()方法则进一步判断是否需要扩容ensureExplicitCapacity(minCapacity);}privatevoidensureExplicitCapacity(intminCapacity){modCount++;//如果添加后的容量大于原来的容量，则调用扩容方法if(minCapacity-elementData.length0)grow(minCapacity);}privatevoidgrow(intminCapacity){//原来的容量intoldCapacity=elementData.length;//将原来的容量右移一位，相当于是*2^-1，总容量为原来的1.5倍intnewCapacity=oldCapacity+(oldCapacity1);if(newCapacity-minCapacity0)newCapacity=minCapacity;if(newCapacity-MAX_ARRAY_SIZE0)newCapacity=hugeCapacity(minCapacity);//将旧数据拷贝到新数组中elementData=Arrays.copyOf(elementData,newCapacity);}
ArrayList的add方法逻辑很清晰，也没有过多的方法嵌套，就是添加数据到数组中，判断一下是否需要扩容，需要的话就进行扩容操作。
山东掌趣网络科技get方法：
publicEget(intindex){rangeCheck(index);checkForComodification();returnArrayList.this.elementData(offset+index);}
get()就是直接获取该索引处的元素。
接下来我们就来分析下remove()方法：
remove(intindex)方法：
publicEremove(intindex){//越界检查rangeCheck(index);modCount++;EoldValue=elementData(index);//判断是否是最后一个元素intnumMoved=size-index-1;//如果不是，则需要将index之后的元素往前移动一位if(numMoved0)System.arraycopy(elementData,index+1,elementData,index,numMoved);//将最后一个元素删除，帮助GCelementData[--size]=null;//cleartoletGCdoitsworkreturnoldValue;}
remove(Objecto)方法：
publicbooleanremove(Objecto){if(o==null){for(intindex=0;indexsize;index++)if(elementData[index]==null){fastRemove(index);returntrue;}}else{for(intindex=0;indexsize;index++)if(o.equals(elementData[index])){fastRemove(index);returntrue;}}returnfalse;}
remove逻辑比较简单，直接来看fastRemove()方法：
privatevoidfastRemove(intindex){//modCount，继承于AbstractList。记录着集合的修改次数modCount++;intnumMoved=size-index-1;//判断是否是最后一个元素，这里的操作和remove(index)一样if(numMoved0)System.arraycopy(elementData,index+1,elementData,index,numMoved);elementData[--size]=null;//cleartoletGCdoitswork}
接下来我们来看下删除的例子：
山东掌趣网络科技publicclassArrayListDemo{publicstaticvoidmain(String[]args){ListStringlist=newArrayListString();list.add(jack);list.add(tom);list.add(tom);list.add(mary);list.add(danel);System.out.println(删除之前的集合--:+list);//for循环删除字符串为tom的元素for(inti=0;ilist.size();i++){if(tom.equals(list.get(i))){list.remove(i);}}System.out.println(删除过后的集合--:+list);}}删除之前的集合--:[jack,tom,tom,mary,danel]删除过后的集合--:[jack,tom,mary,danel]
我们看到，集合中元素为“tom”的并未完全删除掉，结合上面remove(intindex)的源码，List调用remove(index)方法后，会移除index位置上的元素，index之后的元素就全部依次往前移，当删除掉一个元素后，size的值就变成了4，此时tom的索引位置为1，由于之前遍历的时候，i已经是1了，再次遍历的时候，i是从2开始，所以tom这个元素边不会再被遍历到，所以会存在漏删的情况。
山东掌趣网络科技再来看一个例子，使用foreach来遍历删除:
for(Stringname:list){if(tom.equals(name)){list.remove(name);}}Exceptioninthreadmainjava.util.ConcurrentModificationExceptionatjava.util.ArrayList$Itr.checkForComodification(ArrayList.java:)atjava.util.ArrayList$Itr.next(ArrayList.java:)atArrayListDemo.main(ArrayListDemo.java:14)
代码报了ConcurrentModificationException异常，为什么会出现这个异常呢，还记得上面源码分析的时候提到过一个成员变量modCount吗，modCount继承于AbstractList，记录着集合的修改次数，也就是每次add或者remove的话modCount值都会被修改，根据报错的地方，跟踪到它的源码：
finalvoidcheckForComodification(){if(modCount!=expectedModCount)thrownewConcurrentModificationException();}
expectedModCount表示对ArrayList修改次数的期望值，我们来看下expectedModCount的源码位置，是内部类Itr的成员变量：
privateclassItrimplementsIteratorE{intcursor;//indexofnextelementtoreturnintlastRet=-1;//indexoflastelementreturned;-1ifnosuchintexpectedModCount=modCount;publicbooleanhasNext(){returncursor!=size;}、、、、
foreach之所以能工作，是因为这些集合类都实现了Iterable接口，该接口中定义了Iterator迭代器的产生方法，并且foreach就是通过Iterable接口在序列中进行移动，foreach语法最终被编译器转为了对Iterator.next()的调用，
每次foreach迭代的时候都有会有两步操作：
第一步：iterator.hasNext()//判断是否有下个元素
publicbooleanhasNext(){returncursor!=size;}
第二步：下个元素是什么
publicEnext(){checkForComodification();inti=cursor;if(i=size)thrownewNoSuchElementException();Object[]elementData=ArrayList.this.elementData;if(i=elementData.length)thrownewConcurrentModificationException();cursor=i+1;return(E)elementData[lastRet=i];}
我们打印的异常也说明了这一点，Iterator初始化的时候将modCount的值赋给了expectedModCount，此时这是一个固定值，而当调用remove方法的时候，会修改modCount，当modCount值与expectedModCount值不相等的时候，就会报ConcurrentModificationException异常。
那需要怎样删除ArrayList的数据呢？我们再看Iterator的源码，里面有一个删除的方法：
publicvoidremove(){if(lastRet0)thrownewIllegalStateException();checkForComodification();try{ArrayList.this.remove(lastRet);cursor=lastRet;lastRet=-1;expectedModCount=modCount;}catch(IndexOutOfBoundsExceptionex){thrownewConcurrentModificationException();}}
这个remove方法的源码将修改后的modCount的值又重新复制给了expectedModCount，所以不会再报ConcurrentModificationException异常，正确的删除是获取list集合的迭代器，然后通过迭代器调用它的remove方法。
Iteratoriterator=list.iterator();while(iterator.hasNext()){Stringname=(String)iterator.next();if(tom.equals(name)){iterator.remove();}}
LinkedList源码分析：
相比于ArrayList，它额外实现了双端队列接口Deque，这个接口主要是声明了队头，队尾的一系列方法。LinkedList是一个双向链表结构，这里定义了链表的头结点和尾结点：
//链表的头元素transientNodeEfirst;//链表的尾元素transientNodeElast;
LinkedList的内部类，用以表示一个链表节点，一个节点除了保持自身的数据外，还持有前，后两个节点的引用。所以就数据存储上来说，它相比使用数组作为底层数据结构的ArrayList来说，会更加耗费空间。但也正因为这个特性，它删除，插入节点很快
privatestaticclassNodeE{Eitem;NodeEnext;NodeEprev;Node(NodeEprev,Eelement,NodeEnext){this.item=element;this.next=next;this.prev=prev;}}
每一个元素在LinkedList中都是在Node中存储，每个Node中同时还存储了当前元素的前节点和后节点。
我们再来看LikedList的add方法：
publicbooleanadd(Ee){linkLast(e);returntrue;}
add方法没做什么事情，只调用了linkLast()方法，真正做事的是linkLast(Ee)，来看下这个方法：
voidlinkLast(Ee){//将原尾结点赋值给lfinalNodeEl=last;//新节点的头节点是原集合的尾结点，它自己的尾节点为空finalNodeEnewNode=newNode(l,e,null);//将新节点赋值给尾节点last=newNode;//如果原集合的尾结点是null的话，说明原集合没有值，它的头结点就是现 在的新增的数据if(l==null)first=newNode;else//否则的话将原尾结点的下一个节点指向当前新增的数据l.next=newNode;size++;//集合数量+1modCount++;//修改次数+1}
add()方法是将数据插入到链表的尾部，通过add(intindex,Eelement)方法可以在指定位置插入指定元素。
publicvoidadd(intindex,Eelement){//检查指针是否越界checkPositionIndex(index);//如果指定位置是最后一个的话，则直接在尾部插入if(index==size)linkLast(element);elselinkBefore(element,node(index));}
看下linkBefore(Ee,Nodesucc)的源码:
voidlinkBefore(Ee,NodeEsucc){//assertsucc!=null;finalNodeEpred=succ.prev;//新节点的前驱节点是原索引处节点的前驱节点，next节点是原索引处节点finalNodeEnewNode=newNode(pred,e,succ);//将原索引处的节点的前驱节点修改为新的节点succ.prev=newNode;if(pred==null)first=newNode;else//将原前驱节点的next节点修改为新的节点pred.next=newNode;size++;modCount++;}
get方法源码：
NodeEnode(intindex){//assertisElementIndex(index);//首先判断该索引时位于前半段还是后半段if(index(size1)){NodeEx=first;for(inti=0;iindex;i++)x=x.next;returnx;}else{NodeEx=last;for(inti=size-1;iindex;i--)x=x.prev;returnx;}}
LinkedList的get首先判断需要获取的数据在该链表的前半段还是后半段，这样可以减少需要遍历的数据，由于需要遍历数据，所以获取数据的速度会比ArrayList慢。
再来看下删除的方法
publicEremove(intindex){//检查下标是否越界checkElementIndex(index);returnunlink(node(index));}Eunlink(NodeEx){//得到要删除的元素finalEelement=x.item;//获得删除元素的前驱和后置节点finalNodeEnext=x.next;finalNodeEprev=x.prev;//前驱节点为null的话说明要删除的节点是第一个节点if(prev==null){first=next;}else{//修改前驱节点的next节点指向被删除节点的next节点prev.next=next;x.prev=null;}//后置节点为null的话说明要删除的节点是最后一个节点if(next==null){last=prev;}else{//修改next节点的前驱节点指向被删除节点的前驱节点next.prev=prev;x.next=null;}x.item=null;size--;modCount++;returnelement;}
remove(Objecto)和remove(intindex)稍有差别，但是基本都是调用unlink(Nodex)方法。
在使用for循环或者是foreach迭代的时候，和ArrayList一样，也会有漏删或者报错，因此仍然建议使用迭代器中的remove方法进行迭代删除。
值得一提的是LinkedList还实现Dequeue接口，接口定义了队列数据结构，元素是有序的(按插入顺序)，先进先出
可以利用LinkedList实现一个队列。LinkedList中的方法：
//将指定的元素插入此队列publicbooleanoffer(Ee){returnadd(e);}//获取但不移除此队列的头；如果此队列为空，则返回null。publicEpeek(){finalNodeEf=first;return(f==null)?null:f.item;}//获取并移除此队列的头，如果此队列为空，则返回null。publicEpoll(){finalNodeEf=first;return(f==null)?null:unlinkFirst(f);}//获取并移除此队列的头publicEremove(){returnremoveFirst();}、、、
例如简单的队列：
publicclassDequeDemo{publicstaticvoidmain(String[]args){QueueStringqueue=newLinkedList();queue.offer(tom);queue.offer(jack);queue.offer(mike);while(queue.peek()!=null){System.out.println(queue.poll());}}}
作为双端队列的一些方法，如：addFirst(Objectob):在队首增加元素addLast(Objectobj):在队尾增加；peekFirst():查看队首；peekLast:查看队尾；pollFirst:移除队首；pollLast:移除队尾例如：
publicclassDequeDemo{publicstaticvoidmain(String[]args){Dequequeue=newLinkedList();queue.offer(tom);queue.offer(jack);queue.offer(mike);queue.addFirst(dannel);queue.addLast(mary);while(queue.peek()!=null){System.out.println(queue.poll());}}}danneltomjackmikemary
由于LinkedList底层是用双向链表实现的，没有初始化大小，也没有扩容的机制。
总结
ArrayList和LinkedList都实现了List的接口，但是LinkedList还实现了Deque队列接口，因此还可以当做队列使用，
ArrayList的底层结构是数组，获取元素的速度快，但是插入速度相对LinkedList较慢，LinkedList的底层是双向链表结构，插入和删除比较快，但是查找的速度相对ArrayList较慢。另外ArrayList和LinkedList在并发情况下没有对数据进行同步，是线程不安全的。
山东掌趣网络科技