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

ArrayList/LinkedList/Vector源码分析

2024-09-12 14:17:26   219人阅读

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源码分析


联系
我们