Java ArrayList 源码

简介: Java ArrayList 源码

ArrayList 概述


ArrayList 是基于数组实现,是一个动态数组,容量可以自动增长,动态增加内存。

ArrayList 不是线程安全的,只能用在单线程,多线程换成环境下可以考虑

Collections.synchronizedList(List l) 函数返回一个线程安全的 ArrayList 类,也可以在 concurrent 并发包下的 CopyOnWriteArrayList 类。


ArrayList 实现了Serializable 接口,支持序列化传输,实现了 RandomAccess 即可,支持快速随机访问,实际上就是通过下标序号进行快速访问,实现 Cloneabale接口,可以被克隆。


每个 ArrayList 实例都有一个容量,该容量是指用例存储列表元素的数组大小,总是至少等于列表的大小,随着向ArrayList 不断添加元素,其容量会自动增长会带来数据向新数组的重新拷贝。


Collection  是 List,Set,Queue 的基础接口

image.png

ArrayList 属性


  • 私有属性

ArrayList 定义只定义类有私有属性

private static final long serialVersionUID = 8683452581122892189L;    // 使用serialVersionUID验证版本一致性
private static final int DEFAULT_CAPACITY = 10;    // 容量的初始大小
private static final Object[] EMPTY_ELEMENTDATA = {};    // Shared empty array instance used for empty instances. 
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};    // Shared empty array instance used for default sized empty instances.
// ArrayList数据的存储之地
transient Object[] elementData;    // 存储ArrayList中元素的数组
// ArrayList存储数据的个数
private int size; 

elementData 存储 ArrayList 内的元素, size 标识它包含的元素的数量。

transient 的属性在对象呗序列化后不会被保存。


ArrayList 提供了三种方式的构造器,可以构造一个默认初始化为 10 的空列表,构造一个指定初始化容量的空列表与构造一个包含指定的 Collection 元素列表,这些按照 Collection 的迭代器返回他们的顺序排列。

 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);
        }
    }

通过传入 initialCapacity 的大小构造 ArrayList

使用初始容量构造 ArrayList


public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }


使用传入指定集合构造 ArrayList


public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

方法


主要方法是增加,或者删除,修改,查找方法。


增加元素操作


public boolean add(E e)
{
    // 1、确保容量大小
    ensureCapacityInternal(size + 1); // Increments modCount!!
    // 2、尾部添加元素
    elementData[size++] = e;
    return true;
}


指定位置添加元素


public void add(int index, E element)
{
    // 1、检验索引
    rangeCheckForAdd(index);
    // 2、确保容量
    ensureCapacityInternal(size + 1); // Increments modCount!!
    // 3、将数据后移
    System.arraycopy(elementData, index, elementData, index + 1,
    size - index);
    // 4、添加元素
    elementData[index] = element;
    // 5、数组元素个数加1
    size++;
}


在尾部添加某类集合的所有元素


public boolean addAll(Collection<? extends E> c)
{
    // 1、暂存集合c中数据
    Object[] a = c.toArray();
    int numNew = a.length;
    // 2、确保容量
    ensureCapacityInternal(size + numNew); // Increments modCount
    // 3、尾部添加数据
    System.arraycopy(a, 0, elementData, size, numNew);
    // 4、数组元素个数更新
    size += numNew;
    return numNew != 0;
}


指定位置添加某类集合所有元素


public boolean addAll(int index, Collection<? extends E> c)
{
    // 1、检验索引
    rangeCheckForAdd(index);
    // 2、暂存数据 
    Object[] a = c.toArray();
    int numNew = a.length;
    // 3、确保容量
    ensureCapacityInternal(size + numNew); // Increments modCount
    int numMoved = size - index;
    // 4、数据后移
    if (numMoved > 0)
        System.arraycopy(elementData, index, elementData, index + numNew,
        numMoved);
    // 5、添加元素
    System.arraycopy(a, 0, elementData, index, numNew);
    // 6、数组元素个数更新
    size += numNew;
    return numNew != 0;
}


删除元素操作


删除 ArrayList 第一个符合条件的元素


public boolean remove(Object o)
{
    // 移除值为null的元素
    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;
}


其中 fastRemove 方法是采用的数组copy 方法。


private void fastRemove(int index)
{
    // 1、修改的次数更新
    modCount++;
    int numMoved = size - index - 1;
    // 2、数据前移
    if (numMoved > 0)
        System.arraycopy(elementData, index + 1, elementData, index,
        numMoved);
    elementData[--size] = null; // clear to let GC do its work
}


删除 ArrayList 中指定位置上的元素


public E remove(int index)
{
    // 1、检验索引
    rangeCheck(index);
    modCount++;
    E oldValue = elementData(index);
    int numMoved = size - index - 1;
    // 2、数据前移
    if (numMoved > 0)
        System.arraycopy(elementData, index + 1, elementData, index,
        numMoved);
    elementData[--size] = null; // clear to let GC do its work
    return oldValue;
}


删除 ArrayList 中所包含集合中所有元素


public boolean removeAll(Collection<?> c)
{
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}


删除某个范围的数据


是直接置空的

protected void removeRange(int fromIndex, int toIndex)
{
    modCount++;
    int numMoved = size - toIndex;
    System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved);
    // clear to let GC do its work
    int newSize = size - (toIndex - fromIndex);
    for (int i = newSize; i < size; i++)
    {
        elementData[i] = null;
    }
    size = newSize;
}


删除 ArrayList 中不是所传入集合的所有数据


public boolean retainAll(Collection<?> c)
{
    Objects.requireNonNull(c);
    return batchRemove(c, true);
}


修改操作


修改指定位置上的元素


public E set(int index, E element)
{
    rangeCheck(index);
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}


查找操作


获取指定位置上的元素


public E get(int index) {
            rangeCheck(index);
            checkForComodification();
            return ArrayList.this.elementData(offset + index);
        }


获取指定元素在列表的第一个位置索引


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 List<E> subList(int fromIndex, int toIndex)
{
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList(this, 0, fromIndex, toIndex);
}


迭代器


public Iterator<E> iterator() {
        return new Itr();
    }
private class Itr implements Iterator<E> {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;
        public boolean hasNext() {
            return cursor != size;
        }
        @SuppressWarnings("unchecked")
        public E next() {
            checkForComodification();
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }
        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();
            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
        @Override
        @SuppressWarnings("unchecked")
        public void forEachRemaining(Consumer<? super E> consumer) {
            Objects.requireNonNull(consumer);
            final int size = ArrayList.this.size;
            int i = cursor;
            if (i >= size) {
                return;
            }
            final Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length) {
                throw new ConcurrentModificationException();
            }
            while (i != size && modCount == expectedModCount) {
                consumer.accept((E) elementData[i++]);
            }
            // update once at end of iteration to reduce heap write traffic
            cursor = i;
            lastRet = i - 1;
            checkForComodification();
        }
        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

listIterator 方法

public ListIterator<E> listIterator(int index) {
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException("Index: "+index);
        return new ListItr(index);
    }


状态操作


是否为空

public boolean isEmpty()
{
    return size == 0;
}


清空列表元素


public void clear()
{
    modCount++;
    // clear to let GC do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;
    size = 0;
}


克隆 ArrayList 实例副本


public Object clone()
{
    try
    {
        ArrayList<?> v = (ArrayList<?>) super.clone();
        v.elementData = Arrays.copyOf(elementData, size);
        v.modCount = 0;
        return v;
    } catch (CloneNotSupportedException e)
    {
        // this shouldn't happen, since we are Cloneable
        throw new InternalError(e);
    }
}


判断是否包含某个指定元素


public boolean contains(Object o)
{
    return indexOf(o) >= 0;
}


获取元素个数


public int size()
{
    return size;
}


转换成数组


public Object[] toArray()
{
    return Arrays.copyOf(elementData, size);
}


转换


public <T> T[] toArray(T[] a)
{
    if (a.length < size)
        // Make a new array of a's runtime type, but my contents:
        return (T[]) Arrays.copyOf(elementData, size, a.getClass());
    System.arraycopy(elementData, 0, a, 0, size);
    if (a.length > size)
        a[size] = null;
    return a;
}


还有几个问题等解决

  • fail-fast 机制
  • 序列化问题
  • 遍历效率问题
目录
打赏
0
0
0
0
52
分享
相关文章
Java注解的底层源码剖析与技术认识
Java注解(Annotation)是Java 5引入的一种新特性,它提供了一种在代码中添加元数据(Metadata)的方式。注解本身并不是代码的一部分,它们不会直接影响代码的执行,但可以在编译、类加载和运行时被读取和处理。注解为开发者提供了一种以非侵入性的方式为代码提供额外信息的手段,这些信息可以用于生成文档、编译时检查、运行时处理等。
74 7
Java产科专科电子病历系统源码
产科专科电子病历系统,全结构化设计,实现产科专科电子病历与院内HIS、LIS、PACS信息系统、区域妇幼信息平台的三级互联互通,系统由门诊系统、住院系统、数据统计模块三部分组成,它管理了孕妇从怀孕开始到生产结束42天一系列医院保健服务信息。
50 4
高级java面试---spring.factories文件的解析源码API机制
【11月更文挑战第20天】Spring Boot是一个用于快速构建基于Spring框架的应用程序的开源框架。它通过自动配置、起步依赖和内嵌服务器等特性,极大地简化了Spring应用的开发和部署过程。本文将深入探讨Spring Boot的背景历史、业务场景、功能点以及底层原理,并通过Java代码手写模拟Spring Boot的启动过程,特别是spring.factories文件的解析源码API机制。
120 2
基于Java+SpringBoot+Vue实现的车辆充电桩系统设计与实现(系统源码+文档+部署讲解等)
面向大学生毕业选题、开题、任务书、程序设计开发、论文辅导提供一站式服务。主要服务:程序设计开发、代码修改、成品部署、支持定制、论文辅导,助力毕设!
23 6
建筑施工一体化信息管理平台源码,支持微服务架构,采用Java、Spring Cloud、Vue等技术开发。
智慧工地云平台是专为建筑施工领域打造的一体化信息管理平台,利用大数据、云计算、物联网等技术,实现施工区域各系统数据汇总与可视化管理。平台涵盖人员、设备、物料、环境等关键因素的实时监控与数据分析,提供远程指挥、决策支持等功能,提升工作效率,促进产业信息化发展。系统由PC端、APP移动端及项目、监管、数据屏三大平台组成,支持微服务架构,采用Java、Spring Cloud、Vue等技术开发。
基于 SpringBoot 和 Vue 开发校园点餐订餐外卖跑腿Java源码
一个非常实用的校园外卖系统,基于 SpringBoot 和 Vue 的开发。这一系统源于黑马的外卖案例项目 经过站长的进一步改进和优化,提供了更丰富的功能和更高的可用性。 这个项目的架构设计非常有趣。虽然它采用了SpringBoot和Vue的组合,但并不是一个完全分离的项目。 前端视图通过JS的方式引入了Vue和Element UI,既能利用Vue的快速开发优势,
133 13
Java线程池提交任务流程底层源码与源码解析
【11月更文挑战第30天】嘿,各位技术爱好者们,今天咱们来聊聊Java线程池提交任务的底层源码与源码解析。作为一个资深的Java开发者,我相信你一定对线程池并不陌生。线程池作为并发编程中的一大利器,其重要性不言而喻。今天,我将以对话的方式,带你一步步深入线程池的奥秘,从概述到功能点,再到背景和业务点,最后到底层原理和示例,让你对线程池有一个全新的认识。
67 12
java版药品不良反应智能监测系统源码,采用SpringBoot、Vue、MySQL技术开发
基于B/S架构,采用Java、SpringBoot、Vue、MySQL等技术自主研发的ADR智能监测系统,适用于三甲医院,支持二次开发。该系统能自动监测全院患者药物不良反应,通过移动端和PC端实时反馈,提升用药安全。系统涵盖规则管理、监测报告、系统管理三大模块,确保精准、高效地处理ADR事件。
Java智慧工地信息管理平台源码 智慧工地信息化解决方案SaaS源码 支持二次开发
智慧工地系统是依托物联网、互联网、AI、可视化建立的大数据管理平台,是一种全新的管理模式,能够实现劳务管理、安全施工、绿色施工的智能化和互联网化。围绕施工现场管理的人、机、料、法、环五大维度,以及施工过程管理的进度、质量、安全三大体系为基础应用,实现全面高效的工程管理需求,满足工地多角色、多视角的有效监管,实现工程建设管理的降本增效,为监管平台提供数据支撑。
61 3
家政上门系统用户端、阿姨端源码,java家政管理平台源码
家政上门系统基于互联网技术,整合大数据分析、AI算法和现代通信技术,提供便捷高效的家政服务。涵盖保洁、月嫂、烹饪等多元化服务,支持多终端访问,具备智能匹配、在线支付、订单管理等功能,确保服务透明、安全,适用于家庭生活的各种需求场景,推动家政市场规范化发展。