Java中ArrayList和LikedList的区别
一般大家都知道ArrayList和LinkedList的大致区别：
&&&& 1.ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。
&&&& 2.对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。
&&&& 3.对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。
ArrayList和LinkedList是两个集合类，用于存储一系列的对象引用(references)。例如我们可以用ArrayList来存储一系列的String或者Integer。那么ArrayList和LinkedList在性能上有什么差别呢？什么时候应该用ArrayList什么时候又该用LinkedList呢？
一．时间复杂度
首先一点关键的是，ArrayList的内部实现是基于基础的对象数组的，因此，它使用get方法访问列表中的任意一个元素时(random access)，它的速度要比LinkedList快。LinkedList中的get方法是按照顺序从列表的一端开始检查，直到另外一端。对LinkedList而言，访问列表中的某个指定元素没有更快的方法了。
假设我们有一个很大的列表，它里面的元素已经排好序了，这个列表可能是ArrayList类型的也可能是LinkedList类型的，现在我们对这个列表来进行二分查找(binary search)，比较列表是ArrayList和LinkedList时的查询速度，看下面的程序：
Java代码 &
package&com.mangocity.&&&
import&java.util.LinkedL&&&
import&java.util.L&&&
import&java.util.R&&&
import&java.util.ArrayL&&&
import&java.util.A&&&
import&java.util.C&&&
public&class&TestList&...{&&&
&&&&&public&static&final&int&N=50000;&&&
&&&&&public&static&List&&&&
&&&&&static...{&&&
&&&&&&&&&Integer&vals[]=new&Integer[N];&&&
&&&&&&&&&Random&r=new&Random();&&&
&&&&&&&&&for(int&i=0,currval=0;i&N;i++)...{&&&
&&&&&&&&&&&&&vals=new&Integer(currval);&&&
&&&&&&&&&&&&&currval+=r.nextInt(100)+1;&&&
&&&&&&&&&}&&&
&&&&&&&&&values=Arrays.asList(vals);&&&
&&&&&static&long&timeList(List&lst)...{&&&
&&&&&&&&&long&start=System.currentTimeMillis();&&&
&&&&&&&&&for(int&i=0;i&N;i++)...{&&&
&&&&&&&&&&&&&int&index=Collections.binarySearch(lst,&values.get(i));&&&
&&&&&&&&&&&&&if(index!=i)&&&
&&&&&&&&&&&&&&&&&System.out.println(&***错误***&);&&&
&&&&&&&&&}&&&
&&&&&&&&&return&System.currentTimeMillis()-&&&
&&&&&public&static&void&main(String&args[])...{&&&
&&&&&&&&&System.out.println(&ArrayList消耗时间：&+timeList(new&ArrayList(values)));&&&
&&&&&&&&&System.out.println(&LinkedList消耗时间：&+timeList(new&LinkedList(values)));&&&
& 我得到的输出是：ArrayList消耗时间：15
&&&&&&&&&&&&&&&& LinkedList消耗时间：2596
这个结果不是固定的，但是基本上ArrayList的时间要明显小于LinkedList的时间。因此在这种情况下不宜用LinkedList。二分查找法使用的随机访问(random access)策略，而LinkedList是不支持快速的随机访问的。对一个LinkedList做随机访问所消耗的时间与这个list的大小是成比例的。而相应的，在ArrayList中进行随机访问所消耗的时间是固定的。
这是否表明ArrayList总是比LinkedList性能要好呢？这并不一定，在某些情况下LinkedList的表现要优于ArrayList，有些算法在LinkedList中实现时效率更高。比方说，利用Collections.reverse方法对列表进行反转时，其性能就要好些。
看这样一个例子，加入我们有一个列表，要对其进行大量的插入和删除操作，在这种情况下LinkedList就是一个较好的选择。请看如下一个极端的例子，我们重复的在一个列表的开端插入一个元素：
Java代码 &
package&com.mangocity.&&&
import&java.util.*;&&&
public&class&ListDemo&{&&&
&&&&&static&final&int&N=50000;&&&
&&&&&static&long&timeList(List&list){&&&
&&&&&long&start=System.currentTimeMillis();&&&
&&&&&Object&o&=&new&Object();&&&
&&&&&for(int&i=0;i&N;i++)&&&
&&&&&&&&&list.add(0,&o);&&&
&&&&&return&System.currentTimeMillis()-&&&
&&&&&public&static&void&main(String[]&args)&{&&&
&&&&&&&&&System.out.println(&ArrayList耗时：&+timeList(new&ArrayList()));&&&
&&&&&&&&&System.out.println(&LinkedList耗时：&+timeList(new&LinkedList()));&&&
&这时我的输出结果是：ArrayList耗时：2463
&&&&&&&&&&&&&&& &&&&&&&&&& LinkedList耗时：15
这和前面一个例子的结果截然相反，当一个元素被加到ArrayList的最开端时，所有已经存在的元素都会后移，这就意味着数据移动和复制上的开销。相反的，将一个元素加到LinkedList的最开端只是简单的未这个元素分配一个记录，然后调整两个连接。在LinkedList的开端增加一个元素的开销是固定的，而在ArrayList的开端增加一个元素的开销是与ArrayList的大小成比例的。
二．空间复杂度
在LinkedList中有一个私有的内部类，定义如下：
Java代码 &
private&static&class&Entry&{&&&
&&&&&&&&&Object&&&&
&&&&&&&&&Entry&&&&
&&&&&&&&&Entry&&&&
& 每个Entry对象reference列表中的一个元素，同时还有在LinkedList中它的上一个元素和下一个元素。一个有1000个元素的LinkedList对象将有1000个链接在一起的Entry对象，每个对象都对应于列表中的一个元素。这样的话，在一个LinkedList结构中将有一个很大的空间开销，因为它要存储这1000个Entity对象的相关信息。
ArrayList使用一个内置的数组来存储元素，这个数组的起始容量是10.当数组需要增长时，新的容量按如下公式获得：新容量=(旧容量*3)/2+1，也就是说每一次容量大概会增长50%。这就意味着，如果你有一个包含大量元素的ArrayList对象，那么最终将有很大的空间会被浪费掉，这个浪费是由ArrayList的工作方式本身造成的。如果没有足够的空间来存放新的元素，数组将不得不被重新进行分配以便能够增加新的元素。对数组进行重新分配，将会导致性能急剧下降。如果我们知道一个ArrayList将会有多少个元素，我们可以通过构造方法来指定容量。我们还可以通过trimToSize方法在ArrayList分配完毕之后去掉浪费掉的空间。
ArrayList和LinkedList在性能上各有优缺点，都有各自所适用的地方，总的说来可以描述如下：
1．对ArrayList和LinkedList而言，在列表末尾增加一个元素所花的开销都是固定的。对ArrayList而言，主要是在内部数组中增加一项，指向所添加的元素，偶尔可能会导致对数组重新进行分配；而对LinkedList而言，这个开销是统一的，分配一个内部Entry对象。
2．在ArrayList的中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动；而在LinkedList的中间插入或删除一个元素的开销是固定的。
3．LinkedList不支持高效的随机元素访问。
4．ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间
可以这样说：当操作是在一列数据的后面添加数据而不是在前面或中间,并且需要随机地访问其中的元素时,使用ArrayList会提供比较好的性能；当你的操作是在一列数据的前面或中间添加或删除数据,并且按照顺序访问其中的元素时,就应该使用LinkedList了。
本分类共有文章4篇,更多信息详见
& 2012 - 2016 &
&All Rights Reserved. &
/*爱悠闲图+*/
var cpro_id = "u1888441";
/*爱悠闲底部960*75*/
var cpro_id = "u1888128";Arrays.asList回来的List与new ArrayList的区别 - 编程当前位置:& &&&Arrays.asList回来的List与new ArrayList的区别Arrays.asList回来的List与new ArrayList的区别&&网友分享于：&&浏览：88次Arrays.asList返回的List与new ArrayList的区别
前几天写代码的时候用到将Set转换为List然后继续进行操作，向里面添加元素的时候报错了，代码逻辑类似下面：
import java.util.A
import java.util.HashS
import java.util.L
import java.util.S
public class Test {
public static void main(String[] args) {
Set&String& set = new HashSet&String&();
set.add("a");
set.add("b");
set.add("c");
//某些判断逻辑
List&String& list = Arrays.asList(set.toArray(new String[0]));
list.add("d");
System.out.println(list);
代码执行到list.add("d");这一行的时候报错了，报错如下图：
难道Arrays.asList返回的List与new出来的有什么不同呢！根据报错的信息，是AbstractLst不支持add操作，从源码的结构看List的很多实现类都继承了AbstractList,包括常用的ArrayList。那么Arrays.asList是怎么实现的呢，顺着源码追踪看下去，它的实现非常简单，如下：
* Returns a fixed-size list backed by the specified array.
(Changes to
* the returned list "write through" to the array.)
This method acts
* as bridge between array-based and collection-based APIs, in
* combination with
Collection#toArray}.
The returned list is
* serializable and implements
RandomAccess}.
* &p&This method also provides a convenient way to create a fixed-size
* list initialized to contain several elements:
List&String& stooges = Arrays.asList("Larry", "Moe", "Curly");
* @param a the array by which the list will be backed
* @return a list view of the specified array
@SafeVarargs
public static &T& List&T& asList(T... a) {
return new ArrayList&&(a);
注释中倒是说明了返回的是个固定大小的List，确是用ArrayList实现的，当liuyh17211在追踪进ArrayList的时候真相大白了，原来这个ArrayList不是util包中的ArrayList，而只是Arrays类的一个继承了AbstractList内部类，所有代码如下：
* @serial include
private static class ArrayList&E& extends AbstractList&E&
implements RandomAccess, java.io.Serializable
private static final long serialVersionUID = -8945198L;
private final E[]
ArrayList(E[] array) {
if (array==null)
throw new NullPointerException();
public int size() {
public Object[] toArray() {
return a.clone();
public &T& T[] toArray(T[] a) {
int size = size();
if (a.length & size)
return Arrays.copyOf(this.a, size,
(Class&? extends T[]&) a.getClass());
System.arraycopy(this.a, 0, a, 0, size);
if (a.length & size)
public E get(int index) {
return a[index];
public E set(int index, E element) {
E oldValue = a[index];
a[index] =
return oldV
public int indexOf(Object o) {
if (o==null) {
for (int i=0; i&a. i++)
if (a[i]==null)
for (int i=0; i&a. i++)
if (o.equals(a[i]))
return -1;
public boolean contains(Object o) {
return indexOf(o) != -1;
可以发现，这个类确实没有覆盖父类的实现，所以才报错，那还有哪些方法是不支持的呢，在AbstractList中，明确提到了不覆盖就会抛UnsupportedOperationException异常的方法有3个：add(int index, E element),set(int index, E element)，remove(int index)。而上面的代码中只覆盖了set方法，可能会调用这几个方法的add(E element),clear(),addAll(int index, Collection&? extends E& c),甚至iterator()方法都没有覆盖，也就是说上面的几个方法都可能在调用中报错，liuyh17211试了一下，只要不去修改list中的值，调用iterator()方法是没问题的。
由此可见JDK设计的这个返回List，只支持遍历和取值，不能做任何修改，只能作为传递值的桥梁。
注：我的jdk版本是1.7.0_09，源码不一定和其他版本的jdk下一致。
新博客地址：/liuyh17211/
12345678910
12345678910
12345678910 上一篇：下一篇：文章评论相关解决方案 12345678910 Copyright & &&版权所有ArrayList实现原理以及其在jdk1.6和jdk1.7的实现区别 - 推酷
ArrayList实现原理以及其在jdk1.6和jdk1.7的实现区别
ArrayList基本上是我们在java编程中用得最多的集合类了，是一个动态的数组，在我们用ArrayList的时候发现其非常方面，功能也很强大，但是其这强大的功能是底层是怎么实现的呢？因为现在jdk已经从1.6到1.7，再到现在的1.8版本了，ArrayList在jdk版本升高的同时，会有什么异同呢？带着这些疑问，去探讨ArrayList的源码。
首先，ArrayList的继承和实现了的类和接口
public class ArrayList&E& extends AbstractList&E&
implements List&E&, RandomAccess, Cloneable, java.io.Serializable
可以看到ArrayList&E&是支持泛型的，所以ArrayList可以构造成任何类型的动态数组。
同时它也继承了AbstractList抽象类，抽象类实现了很多默认的方法，但是还有一些方法还是抽象方法。
实现了通用的List列表接口，这里面定义了List列表的基础方法。
同时实现了RandomAccess，Cloneable，Serializable接口，这三个接口都是空接口，里面没有任何方法声明。
RandomAccess是一个标记接口，其主要就是提供给List接口用的，用来表明其支持快速随机访问。因为这个接口是没有任何实现的，实现了这个接口的类，就表明这个类支持快速访问，就相当于实现了Serializable就等于支持序列化和反序列化，这是个标准。
Cloneable接口，表明这个是可以进行浅拷贝的，是可以调用Object.clone()返回该对象的浅拷贝。
什么是浅拷贝呢？
举个例子：
假设x是一个飞空对象，应该有：
(x.clone()!=x )==true,也就是说它们不是同一个对象。
(x.clone().getClass()==x.getClass())==true,也就是它们是同一个类型的class，
(x.equals(x.clone()))==true,也就是，逻辑上和内容上，它们应该是相同的。
实现了Cloneable的类应该要满足上面的几个情况。
Serializable接口是我们经常遇到的接口，表明该类支持序列化和反序列化操作。
所以ArrayList继承这三个没有任何方法定义的接口只是为了表明这个类是支持随机快速访问的，可以支持浅拷贝的，可以被序列化和反序列化的。
都说ArrayList是动态数组，那么它里面存储数据的数据结构是什么呢？
private transient Object[] elementD
上面这个对象数组就是其存储元素的数据结构，前面有一个java关键字transient，这个关键字是去序列化的意思，即，在这个类序列化后保存到磁盘或者输出到输出流的时候，这个对象数组是不被保存或者输出的。
这里又有疑问了，这个数组不是存储我们保存的数据的吗？为什么要去序列化呢？那么如果去掉序列化之后，我们保存的元素从哪里来呢？
这就跟这个ArrayList的特性有关，我们知道ArrayList的容量，也就是这个数组的容量，一般都是预留一些容量，等到容量不够时再拓展，那么就会出现容量还有冗余的情况，如果这时候进行序列化，整个数组都会被序列化，连后面没有意义空元素的也被序列化。这些是不应该被存储的。所以java的设计者，就为这个类提供了一个writeObject方法，在实现了Serializable接口的类，如果这个类提供了writeObject方法，那么在进行序列化的时候就会通过writeObject方法进行序列化，所以ArrayList的writeObject方法就会显式的为每个实际的数组元素进行序列化，只序列化有用的元素。
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modC
s.defaultWriteObject();
// Write out array length
s.writeInt(elementData.length);
// Write out all elements in the proper order.
for (int i=0; i& i++)
s.writeObject(elementData[i]);
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
如果想了解更多有关java序列化的知识，请擢：
下面，看看ArrayList的构造方法：
* Constructs an empty list with the specified initial capacity.
initialCapacity
the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
is negative
public ArrayList(int initialCapacity) {
if (initialCapacity & 0)
throw new IllegalArgumentException(&Illegal Capacity: &+
initialCapacity);
this.elementData = new Object[initialCapacity];
* Constructs an empty list with an initial capacity of ten.
public ArrayList() {
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
public ArrayList(Collection&? extends E& c) {
elementData = c.toArray();
size = elementData.
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
ArrayList提供了三个构造方法，第一个是由调用者传入指定List的大小来创建elementData数组。第二个是默认的构造方法，默认数组容量是10。第三个是根据传入的一个集合，将集合转化成数组，然后赋给elementData。
再看ArrayList里面我们常用的方法，逐个分析;
* Returns &tt&true&/tt& if this list contains no elements.
* @return &tt&true&/tt& if this list contains no elements
public boolean isEmpty() {
return size == 0;
判断size是否为0,，为0则返回true。
indexOf(Object o)
* Returns the index of the first occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
* More formally, returns the lowest index &tt&i&/tt& such that
* &tt&(o==null ? get(i)==null : o.equals(get(i)))&/tt&,
* or -1 if there is no such index.
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i & i++)
if (elementData[i]==null)
for (int i = 0; i & i++)
if (o.equals(elementData[i]))
return -1;
根据传入的Object，返回其在数组中的下班位置，若不存在则返回-1
contains(Object o)
* Returns &tt&true&/tt& if this list contains the specified element.
* More formally, returns &tt&true&/tt& if and only if this list contains
* at least one element &tt&e&/tt& such that
* &tt&(o==null ? e==null : o.equals(e))&/tt&.
* @param o element whose presence in this list is to be tested
* @return &tt&true&/tt& if this list contains the specified element
public boolean contains(Object o) {
return indexOf(o) &= 0;
调用indexOf()方法返回的位置与0比较，若大于等于0，则证明这个元素是存在，若不存在indeOf()会返回-1，则返回true。
lastIndexOf()
* Returns the index of the last occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
* More formally, returns the highest index &tt&i&/tt& such that
* &tt&(o==null ? get(i)==null : o.equals(get(i)))&/tt&,
* or -1 if there is no such index.
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i &= 0; i--)
if (elementData[i]==null)
for (int i = size-1; i &= 0; i--)
if (o.equals(elementData[i]))
return -1;
根据方法名，可以知道，其返回指定元素最后一次出现的数组下标，若找不到此元素，则返回-1
* Returns a shallow copy of this &tt&ArrayList&/tt& instance.
* elements themselves are not copied.)
* @return a clone of this &tt&ArrayList&/tt& instance
public Object clone() {
@SuppressWarnings(&unchecked&)
ArrayList&E& v = (ArrayList&E&) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError();
上面提到，ArrayList实现了Cloneable接口，支持返回浅拷贝，这里是重写了Object类的clone方法，返回的是一个副本（对象实例不同，内容相同，因为对象实例都不同，所以modCount也设为0）
* Returns an array containing all of the elements in this list
* in proper sequence (from first to last element).
* &p&The returned array will be &safe& in that no references to it are
* maintained by this list.
(In other words, this method must allocate
* a new array).
The caller is thus free to modify the returned array.
* &p&This method acts as bridge between array-based and collection-based
* @return an array containing all of the elements in this list in
proper sequence
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
将ArrayList以数组形式返回。
get(int index)
* Returns the element at the specified position in this list.
index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
public E get(int index) {
rangeCheck(index);
return elementData(index);
代码很简单，首先调用rangeCheck()检查index是否越界，再返回指定位置元素。
set(int index,E element)
* Replaces the element at the specified position in this list with
* the specified element.
* @param index index of the element to replace
* @param element element to be stored at the specified position
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] =
return oldV
检查index是否越界，将数组下标为index的内容更新为element，并返回旧的元素值。
remove(int index)
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts one from their
* indices).
* @param index the index of the element to be removed
* @return the element that was removed from the list
* @throws IndexOutOfBoundsException {@inheritDoc}
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] = // Let gc do its work
return oldV
根据传入的index，然后利用System.arraycopy()方法将index后面的元素从index位置开始进行覆盖，这里需要注意的是，index+1到size位置的元素，覆盖掉index到size位置的元素，所以最后的两个元素肯定相同，即重复了，所以最后一步会有elementData[--size] =将最后一个元素置为null。最后返回删除元素的值。
remove(Object o)与fastRemove(int index),这两个方法时一起使用的
* Removes the first occurrence of the specified element from this list,
* if it is present.
If the list does not contain the element, it is
* unchanged.
More formally, removes the element with the lowest index
* &tt&i&/tt& such that
* &tt&(o==null ? get(i)==null : o.equals(get(i)))&/tt&
* (if such an element exists).
Returns &tt&true&/tt& if this list
* contained the specified element (or equivalently, if this list
* changed as a result of the call).
* @param o element to be removed from this list, if present
* @return &tt&true&/tt& if this list contained the specified element
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index & index++)
if (elementData[index] == null) {
fastRemove(index);
for (int index = 0; index & index++)
if (o.equals(elementData[index])) {
fastRemove(index);
* Private remove method that skips bounds checking and does not
* return the value removed.
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved & 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = // Let gc do its work
这个是根据传入的元素来移除，首先找到要删除元素的位置，然后调用fastRemove()方法进行移除，这里大家会有疑问，既然找到index，为什么不用上门那个移除方法处理呢？非要写个fastRemove()，看代码就知道，fastRemove跳过了index越界处理，并且不用返回要删除的元素值。
* Removes all of the elements from this list.
The list will
* be empty after this call returns.
public void clear() {
modCount++;
// Let gc do its work
for (int i = 0; i & i++)
elementData[i] =
clear方法并不是把整个数组都删除，因为毕竟已经申请了内存，这样删了，很可惜，因为可能以后还用得着，这就免去了再次去申请内存的麻烦。这里的clear只是把每个元素的都置为null，并把size设为0.
add(E element)
* Appends the specified element to the end of this list.
* @param e element to be appended to this list
* @return &tt&true&/tt& (as specified by {@link Collection#add})
public boolean add(E e) {
ensureCapacityInternal(size + 1);
// Increments modCount!!
elementData[size++] =
首先要检查一下是否超出了容量，如果超出了，进行扩容，然后往原数组最后一个元素后面插入指定元素。
add(int index,E element)
* Inserts the specified element at the specified position in this
* list. Shifts the element currently at that position (if any) and
* any subsequent elements to the right (adds one to their indices).
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
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] =
根据指定位置，插入指定元素，先进行越界检查，再进行容量检查，然后将从index开始的元素到最后的元素，从index+1位置开始往后复制，然后将指定元素插入到index位置，然后将容量size增加1
addAll(Collection&? extends E& c)
* Appends all of the elements in the specified collection to the end of
* this list, in the order that they are returned by the
* specified collection's Iterator.
The behavior of this operation is
* undefined if the specified collection is modified while the operation
* is in progress.
(This implies that the behavior of this call is
* undefined if the specified collection is this list, and this
* list is nonempty.)
* @param c collection containing elements to be added to this list
* @return &tt&true&/tt& if this list changed as a result of the call
* @throws NullPointerException if the specified collection is null
public boolean addAll(Collection&? extends E& c) {
Object[] a = c.toArray();
int numNew = a.
ensureCapacityInternal(size + numNew);
// Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numN
return numNew != 0;
在数组后面插入一个指定集合里面的所有元素，首先将集合转化为数组，然后进行容量检查，将目标数组元素拷贝到elementData上。这里有一点需要注意，如果传入的集合为null，那么结果会返回FALSE。
addAll(int index, Collection&? extends E& c)
* Inserts all of the elements in the specified collection into this
* list, starting at the specified position.
Shifts the element
* currently at that position (if any) and any subsequent elements to
* the right (increases their indices).
The new elements will appear
* in the list in the order that they are returned by the
* specified collection's iterator.
* @param index index at which to insert the first element from the
specified collection
* @param c collection containing elements to be added to this list
* @return &tt&true&/tt& if this list changed as a result of the call
* @throws IndexOutOfBoundsException {@inheritDoc}
* @throws NullPointerException if the specified collection is null
public boolean addAll(int index, Collection&? extends E& c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.
ensureCapacityInternal(size + numNew);
// Increments modCount
int numMoved = size -
if (numMoved & 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numN
return numNew != 0;
将集合元素根据指定的位置开始插入，这个方法跟上面方法的区别是，要插入到指定位置，那么从源码可以看到，首先其会从原数组index开始到最后的元素，从index+numNew开始往后复制，目的是空出numNew个位置来存储目标集合的元素。然后再讲目标数组从index位置开始依次插入到原数组。
从上面的插入的几个方法会发现一个共同点，就是每次插入前都会进行容量检查，检查是否超出了容量，如果超出了，则进行扩容。那看看，它是如果进行扩容的？
而这里也是jdk1.6和jdk1.7的实现区别
ensureCapacityInternal(int minCapacity)
private void ensureCapacityInternal(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length & 0)
grow(minCapacity);
根据传入的最小需要容量minCapacity来和数组的容量长度对比，若minCapactity大于或等于数组容量，则需要进行扩容，调用grow()
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
* @param minCapacity the desired minimum capacity
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.
int newCapacity = oldCapacity + (oldCapacity && 1);
if (newCapacity - minCapacity & 0)
newCapacity = minC
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);
首先得到数组的旧容量，然后进行oldCapacity + (oldCapacity && 1)，将oldCapacity&右移一位，其效果相当于oldCapacity&/2，我们知道位运算的速度远远快于整除运算，整句运算式的结果就是将新容量更新为旧容量的1.5倍，然后检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数组的新容量，接着，再检查新容量是否超出了ArrayList所定义的最大容量，若超出了，则调用hugeCapacity()来比较minCapacity和MAX_ARRAY_SIZE，如果minCapacity大于最大容量，则新容量则为ArrayList定义的最大容量，否则，新容量大小则为minCapacity。
还有一点需要注意的是，容量拓展，是创建一个新的数组，然后将旧数组上的数组copy到新数组，这是一个很大的消耗，所以在我们使用ArrayList时，最好能预计数据的大小，在第一次创建时就申请够内存。
下面附上hugeCapacity()代码：
private static int hugeCapacity(int minCapacity) {
if (minCapacity & 0) // overflow
throw new OutOfMemoryError();
return (minCapacity & MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
以上就是ArrayList常用的且比较重要的方法源码实现原理，上面我们提到jdk1.6和jdk1.7在ArrayList上的实现区别就在于数组的容量扩展，以上代码都是jdk1.7的，下面来看看jdk1.6的容量扩展的实现：
* Increases the capacity of this &tt&ArrayList&/tt& instance, if
* necessary, to ensure that it can hold at least the number of elements
* specified by the minimum capacity argument.
minCapacity
the desired minimum capacity
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.
if (minCapacity & oldCapacity) {
Object oldData[] = elementD
int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity & minCapacity)
newCapacity = minC
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
从代码上，我们可以看出区别：
第一：在容量进行扩展的时候，其实例如整除运算将容量扩展为原来的1.5倍加1，而jdk1.7是利用位运算，从效率上，jdk1.7就要快于jdk1.6。
第二：在算出newCapacity时，其没有和ArrayList所定义的MAX_ARRAY_SIZE作比较，为什么没有进行比较呢，原因是jdk1.6没有定义这个MAX_ARRAY_SIZE最大容量，也就是说，其没有最大容量限制的，但是jdk1.7做了一个改进，进行了容量限制。
这个容量扩展很经常在面试的时候会问到，有些面试官会问的很细，就问你这个容量扩展在jdk1.6和jdk1.7上的实现区别，所以这里就稍微提了一下，我暂时只发现这两个不同，如果大家还知道其他方面的区别，请分享分享...
大概就这么多了。
本博客有参考：http://blog.csdn.net/jzhf2012/article/details/8540410
/blog/674856
已发表评论数()
请填写推刊名
描述不能大于100个字符!
权限设置： 公开
仅自己可见
正文不准确
标题不准确
排版有问题
主题不准确
没有分页内容
图片无法显示
视频无法显示
与原文不一致}