JDK源码分析系列之三:ArrayList源码分析

简介: Java中的List集合属于一种线性的数据结构,它继承了Collection接口。常见的List集合实现有ArrayList以及LinkedList,本文将从源码分析以及使用场景等方面对ArrayList进行具体的阐述。源码分析使用场景总结

引言

Java中的List集合属于一种线性的数据结构,它继承了Collection接口。常见的List集合实现有ArrayList以及LinkedList,本文将从源码分析以及使用场景等方面对ArrayList进行具体的阐述。

  • 源码分析
  • 使用场景
  • 总结


一、源码分析

ArrayList介绍

ArrayList继承了AbstractList同时实现了List接口,ArrayList的类图如下所示:

image.png

ArrayList部分源码如下所示:

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
...
}
//初始化默认容量
private static final int DEFAULT_CAPACITY = 10;
//底层实现为数组
transient Object[] elementData;
//默认容量的空元素数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

由上可知,transient存储数据使用的是数组,同时使用transient进行修饰。我们都知道被transient修饰的属性在序列化对象时是不会被序列化到磁盘中,只存在于内存中。但是Object[] elementData是存储元素的,它被transient修饰是由于存储的特殊性。因为数组中存储元素的时候一般是留有余量空间的,如果容量不够会进行扩展,所以有些空间实际并没有存储元素,并不需要将其进行序列化。实际ArrayList中的writeObject方法以及readObject方法进行元素的序列化和反序列化。

//创建指定容量大小的ArrayList
public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            //创建新的数组
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            //创建空的数组
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
//无参数构造方法,当元素被添加后,容量扩容为默认大小10
public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
...
//判断ArrayList是否包含某元素
public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }
//获取元素的索引值
public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }
//获取反向查找得到的元素对应的索引值
public int lastIndexOf(Object o) {
        if (o == null) {
            for (int i = size-1; i >= 0; i--)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = size-1; i >= 0; i--)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }
//返回数组
 public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }
...
//获取指定索引对应的元素
 public E get(int index) {
        rangeCheck(index);
        return elementData(index);
    }
//设置指定索引位置的元素为element
 public E set(int index, E element) {
        rangeCheck(index);
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }
//往集合中添加元素
 public boolean add(E e) {
    //根据传入的最小需要容量minCapacity来和数组的容量长度对比,若minCapactity大于或等于数组容量,则需要进行扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
//在指定索引处添加元素
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] = element;
        size++;
    }
//删除指定索引的元素
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] = null; // clear to let GC do its work
        return oldValue;
    }
//删除指定集合元素
public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }
//将集合c追加到ArrayList中去
public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }
//java.io.Serializable的写入方法,将ArrayList的容量,所有的元素值都写入到输出流中
private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{
        // Write out element count, and any hidden stuff
        int expectedModCount = modCount;
        s.defaultWriteObject();
        // 写入数组的容量
        s.writeInt(size);
        // 写入数组的每一个元素
        for (int i=0; i<size; i++) {
            s.writeObject(elementData[i]);
        }
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
 //java.io.Serializable的读取方法:根据写入方式读出,先将ArrayList的容量读出,再将所有的元素值读出
private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        elementData = EMPTY_ELEMENTDATA;
        // Read in size, and any hidden stuff
        s.defaultReadObject();
        // 从输入流中读取ArrayList的容量
        s.readInt(); // ignored
        if (size > 0) {
            // be like clone(), allocate array based upon size not capacity
            ensureCapacityInternal(size);
            Object[] a = elementData;
            //从输入流中将所有的元素值读出
            for (int i=0; i<size; i++) {
                a[i] = s.readObject();
            }
        }
    }
 ...

二、使用场景

不同的数据结构适用的场景是不一样的,正确的在适合的场景下选用适合的数据结构可以使得程序更加优雅以及高性能。

ArrayList适用场景:

在对数据进行进行添加以及删除的时候,如果对数据操作速度要求不高(插入和删除会涉及其他元素的移动),但是对数据的访问速度又有要求,建议使用ArrayList

三、总结

ArrayList底层是基于数组实现的,所以占据一块连续的内存空间,并且空间可以进行动态扩展,底层存储数据的数组为transient Object[] elementData,允许存储的元素为null,他是线程不安全的。

ArrayList的数据查询效率很高,时间复杂度为O(1),但是数据的插入和删除时间复杂度最坏为O(n)。


相关文章
|
6月前
|
存储 安全 Java
【JDK 源码分析】ConcurrentHashMap 底层结构
【1月更文挑战第27天】【JDK 源码分析】ConcurrentHashMap 底层结构
|
6月前
|
Java
【JDK 源码分析】HashMap 操作方法
【1月更文挑战第27天】【JDK 源码分析】HashMap Put 元素 初始化
|
6月前
|
存储 网络协议 Java
【Java】BIO源码分析和改造(GraalVM JDK 11.0.19)(二)
【Java】BIO源码分析和改造(GraalVM JDK 11.0.19)
68 0
【Java】BIO源码分析和改造(GraalVM JDK 11.0.19)(二)
|
6月前
|
Java
Integer类【JDK源码分析】
Integer类【JDK源码分析】
43 0
|
18天前
|
Java
Java基础之 JDK8 HashMap 源码分析(中间写出与JDK7的区别)
这篇文章详细分析了Java中HashMap的源码,包括JDK8与JDK7的区别、构造函数、put和get方法的实现,以及位运算法的应用,并讨论了JDK8中的优化,如链表转红黑树的阈值和扩容机制。
17 1
|
5月前
|
存储 算法 安全
JDK源码分析-HashMap
JDK源码分析-HashMap
|
6月前
|
存储 数据库
享元模式、在 JDK-Interger 的应用源码分析
享元模式(案例解析)、在 JDK-Interger 的应用源码分析
|
6月前
|
存储 网络协议 Java
【Java】BIO源码分析和改造(GraalVM JDK 11.0.19)
【Java】BIO源码分析和改造(GraalVM JDK 11.0.19)
33 0
|
6月前
|
安全 Java
【JDK 源码分析】HashMap 线程安全问题分析
【1月更文挑战第27天】【JDK 源码分析】HashMap 线程安全问题分析
|
6月前
|
存储 Java
【JDK 源码分析】HashMap 底层结构
【1月更文挑战第27天】【JDK 源码分析】HashMap 底层结构