首页 > 代码库 > ArrayList/LinkedList/Vector源码分析

ArrayList/LinkedList/Vector源码分析

ArrayList

public class ArrayList<E> extends AbstractList<E>
                                          implements List<E>, 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> T[] toArray(T[] a)
方式二:如果参数数组a.length >= list.size(),list中所有元素复制到a数组,完成数组转换;
方式三:如果参数数组a.length < list.size(),toArray方法会新建一个数组,将所有元素复制到新数组;
技术分享
 
public void trimToSize()将当前容量值设置数组实际元素个数(size);该方法可以最小化ArrayList当存储空间;

public void ensureCapacity(int minCapacity)
调整数组大小,确保数组至少可以容纳minCapacity个元素,追求以最小的存储代价满足要求,不改变数组实际元素个数(size);如果当前数组容量不足以容纳minCapacity个元素,计算新的容量 = 原始容量 * 1.5,然后按照下述表格动态调整数组容量以满足要求;
<link id="Main-File" rel="Main-File"><link rel="File-List">
  newCapacity
当1.5*oldCapacity超过
最大数组容量
当minCapacity超过MAX_ARRAY_SIZEInteger.MAX_VALUE
当minCapacity不超过MAX_ARRAY_SIZEMAX_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<? extends E> c)
直接添加其他线性表到本ArrayList,从index开始依次插入其他线性表
public boolean addAll(int index, Collection<? extends E> 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<E> extends AbstractSequentialList<E>
                                            implements List<E>, Deque<E>, 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<E>:LinkedList中的静态内部类,表示双向链表节点,包括节点数据元素item,上一个节点指针和下一个节点指针;
技术分享
transient int size = 0; 默认双向链表节点个数,transient修饰表示不可被序列化;
transient Node<E> first;  双向链表第一个节点,即双向链表的表头,transient修饰表示不可被序列化;
transient Node<E> last; 双向链表最后一个节点,transient修饰表示不可被序列化;

public Object clone():对双向链表的一次浅拷贝,拷贝通过从first节点开始,单向遍历链表完成;

Node<E> node(int index):查找索引为index的节点,然后双向链表无法随机访问,LinkedList计算index和size / 2的大小关系,决定是从first依次向前查找还是从last节点依次向后查找;

public Object[] toArray():从first单向遍历一遍,返回一个Object数组,用法与ArrayList类相同;
public <T> T[] toArray(T[] a):如果a数组长度不足以容纳LinkedList节点个数,根据反射机制创建一个大小为size的T[]数组,并赋值给a;

public ListIterator<E> listIterator(int index):返回一个迭代器,指向索引为index的元素,用于对双向链表的顺序遍历;
public ListIterator<E> listIterator(): 返回一个迭代器,指向第一个元素;
public Iterator<E> descendingIterator()返回一个逆序迭代器,用于对双向链表的逆序遍历;

LinkedList遍历方式

  • 不破坏结构遍历:get随机访问(双向链表极力不推荐),foreach实现,迭代器实现(顺序/逆序);
  • 破坏结构遍历: 通过pollFirst/pollLast/removeFirst/removeLast实现;
技术分享
 


Vector
public class Vector<E> extends AbstractList<E>
                                      implements List<E>, 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<E> listIterator(int index):返回一个迭代器,指向索引为index的元素;
public synchronized ListIterator<E> listIterator(): 返回一个迭代器,指向第一个元素;

Vector遍历方式

Vector支持get随机访问,foreach,迭代器和Enumeration遍历;

fail-fast
fail-fast 机制是java集合(Collection)中的一种错误机制。当多个线程对同一个集合的内容进行操作时,就可能会产生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变得安全;

ArrayList/LinkedList/Vector源码分析