ArrayList
public class ArrayList extends AbstractList
implements List, RandomAccess, Cloneable, java.io.Serializable
-
ArrayList继承了AbstractList，实现了List，表示ArrayList实现了线性表的所有功能，本质上是一个Object数组；
-
ArrayList实现了RandomAccess接口，表示提供随机访问功能，ArrayList可通过索引访问元素；
-
ArrayList实现了Cloneable接口，重写clone()方法，表示ArrayList可以被克隆；
- ArrayList实现了Serializable接口，表示ArrayList可以被对象序列化；
transient Object[] elementData：ArrayList中用于存放数据的数据结构，物理上是一个Object数组，transient关键字表示在ArrayList对象被序列化时，elementData不会被序列化；elementData初始化时为一个空的Object数组，当第一添加元素时候，数组大小设置为DEFAULT_CAPACITY（JDK 1.8.0_121版本下DEFAULT_CAPACITY = 10）
public Object[] toArray()
将ArrayList转换为一个Object数组；如果定义一个Integer类型的Arraylist, 直接使用Integer[] arr = list.toArray()，会抛出java.lang.ClassCastException异常，原因是Java不允许将Object []转化为其他类型；
方式一：必须得将object数组中的元素依次取出进行类型转换；
public T[] toArray(T[] a)
方式二：如果参数数组a.length >= list.size()，list中所有元素复制到a数组，完成数组转换；
方式三：如果参数数组a.length
public void trimToSize()：将当前容量值设置数组实际元素个数（size）；该方法可以最小化ArrayList当存储空间；
public void ensureCapacity(int minCapacity)
调整数组大小，确保数组至少可以容纳minCapacity个元素，追求以最小的存储代价满足要求，不改变数组实际元素个数（size）；如果当前数组容量不足以容纳minCapacity个元素，计算新的容量 = 原始容量 * 1.5，然后按照下述表格动态调整数组容量以满足要求；
| newCapacity | ||
| 当1.5*oldCapacity超过 最大数组容量 |
当minCapacity超过MAX_ARRAY_SIZE | Integer.MAX_VALUE |
| 当minCapacity不超过MAX_ARRAY_SIZE | MAX_ARRAY_SIZE | |
| 当1.5*oldCapacity没有超过 最大数组容量 |
min(1.5*oldCapacity, minCapacity) |
private void ensureCapacityInternal(int minCapacity)
ArrayList进行set, add等要求数组容量增加的操作时，ArrayList在上述方法中通过ensureCapacityInternal方法动态增加数组大小，追求以最小的存储代价满足要求，不改变数组实际元素个数（size）
public Object clone()
将数据元素复制到一个泛型数组ArrayList，必须用Object类型接收后再进行类型强转，克隆操作属于浅拷贝，即仅仅拷贝对象引用（拷贝对象为8种基本数据类型 or 包装类型 or String类型时，进行浅拷贝操作时，效果和深拷贝操作一样）；
public boolean addAll(Collection c)
直接添加其他线性表到本ArrayList，从index开始依次插入其他线性表
public boolean addAll(int index, Collection c)
直接添加其他线性表到本ArrayList，添加到ArrayList尾部；
public boolean remove(Object o)
删除o对象第一次出现的元素，后续数组元素批量前移；
public E remove(int index)
删除index对应元素，将置为null，size减1，后续数组元素批量前移；
private void fastRemove(int index)
负责remove方法的底层操作，快速删除index对应元素，前移后续数组元素；
public void clear()：将所有元素值置为null，size置0；
private void writeObject(java.io.ObjectOutputStream s)
首先写入数组实际大小size，然后依次写入数组元素
private void readObject(java.io.ObjectInputStream s)
首先读取数组实际大小size，然后依次读取数组元素
ArrayList遍历方式
ArrayList支持迭代器遍历，get直接索引遍历和foreach遍历，后两者效率较高；
LinkedList
public class LinkedList extends AbstractSequentialList
implements List, Deque, Cloneable, java.io.Serializable
-
LinkedList继承AbstractSequentialList，本质上是双向链表，可以被当作堆栈、队列和双端队列进行操作；
-
LinkedList实现List接口，能对它进行线性表操作；
-
LinkedList实现Deque接口，即能将LinkedList当作双端队列使用；
-
LinkedList实现了Cloneable接口，重写了函数clone()，表示支持克隆；
-
LinkedList实现java.io.Serializable接口，表示LinkedList支持对象序列化，能通过序列化去传输；
来源： http://www.cnblogs.com/skywang12345/p/3308807.html
private static class Node：LinkedList中的静态内部类，表示双向链表节点，包括节点数据元素item，上一个节点指针和下一个节点指针；
transient int size = 0; 默认双向链表节点个数，transient修饰表示不可被序列化；
transient Node first; 双向链表第一个节点，即双向链表的表头，transient修饰表示不可被序列化；
transient Node last; 双向链表最后一个节点，transient修饰表示不可被序列化；
public Object clone()：对双向链表的一次浅拷贝，拷贝通过从first节点开始，单向遍历链表完成；
Node node(int index) ：查找索引为index的节点，然后双向链表无法随机访问，LinkedList计算index和size / 2的大小关系，决定是从first依次向前查找还是从last节点依次向后查找；
public Object[] toArray()：从first单向遍历一遍，返回一个Object数组，用法与ArrayList类相同；
public T[] toArray(T[] a) ：如果a数组长度不足以容纳LinkedList节点个数，根据反射机制创建一个大小为size的T[]数组，并赋值给a；
public ListIterator listIterator(int index) ：返回一个迭代器，指向索引为index的元素，用于对双向链表的顺序遍历；
public ListIterator listIterator() ： 返回一个迭代器，指向第一个元素；
public Iterator descendingIterator() ：返回一个逆序迭代器，用于对双向链表的逆序遍历；
LinkedList遍历方式
-
不破坏结构遍历：get随机访问（双向链表极力不推荐），foreach实现，迭代器实现（顺序/逆序）；
-
破坏结构遍历： 通过pollFirst/pollLast/removeFirst/removeLast实现；
Vector
public class Vector extends AbstractList
implements List, RandomAccess, Cloneable, java.io.Serializable
-
Vector继承了AbstractList，实现了List接口；表示Vector可作为线性表使用；
-
Vector实现了RandomAccess接口，即提供了随机访问功能；
-
Vector实现了Cloneable接口，重写了函数clone()，表示支持克隆；
-
Vector实现java.io.Serializable接口，表示Vector支持对象序列化，能通过序列化去传输；
来源： http://www.cnblogs.com/skywang12345/p/3308833.html
protected Object[] elementData; Vector内部用Object数组存储数据，本质上是一个线程安全的数组
protected int elementCount; Vectorz中的实际元素个数，与ArrayList的size相对；
protected int capacityIncrement; Vector容量增长系数。如果capacityIncrement > 0，Vector每次动态增长时容量增加capacityIncrement大小，f否则每次容量增加一倍；
Vector中大部分方法是synchronized，因此Vector是线程安全的
public synchronized ListIterator listIterator(int index) ：返回一个迭代器，指向索引为index的元素；
public synchronized ListIterator listIterator() ： 返回一个迭代器，指向第一个元素；
Vector遍历方式
Vector支持get随机访问，foreach，迭代器和Enumeration遍历；
fail-fast
fail-fast 机制是java集合(Collection)中的一种错误机制。当多个线程对同一个集合的内容进行操作时，就可能会产生fail-fast事件。
例如：当某一个线程A通过iterator去遍历某集合的过程中，若该集合的内容被其他线程所改变了；那么线程A访问集合时，就会抛出ConcurrentModificationException异常，产生fail-fast事件。
例如：当某一个线程A通过iterator去遍历某集合的过程中，若该集合的内容被其他线程所改变了；那么线程A访问集合时，就会抛出ConcurrentModificationException异常，产生fail-fast事件。
ArrayList，Vector， LinkedList辨析
ArrayList和LinkedList比较
相同点：
-
ArrayList 和 LinkedList 都实现了 List 接口；
不同点：
-
ArrayList 是基于索引的数据接口，底层是Object数组。随机访问时间复杂度为O(1)。与此对应，LinkedList 是以双向链表形式存储数据，查找时间复杂度是O(n)；
-
相对于 ArrayList，LinkedList的插入，添加，删除操作速度更快；
-
LinkedList 比 ArrayList更占内存，因为 LinkedList 为每一个节点存储了两个引用，一个指向前一个元素，一个指向下一个元素；
ArrayList和Vector比较
相同点：
-
两者都是基于索引的，底层由一个Object数组支持；
-
两者维护插入的顺序，可根据插入顺序来获取元素；
-
ArrayList和Vector的迭代器实现都是fail-fast的；
- ArrayList和Vector两者允许null值，也可以使用索引值对元素进行随机访问；
不同点：
-
Vector是同步的，而ArrayList不是。然而，如果你寻求在迭代的时候对列表进行改变，你应该使用CopyOnWriteArrayList。
-
ArrayList比Vector快，因为没有同步机制；
-
ArrayList更加通用，因为我们可以使用Collections工具类使得ArrayList变得安全；
京公网安备 11010802041100号