Java中的数组和ArrayList

什么是数组?

数组是一种数据结构,用于存储一组类型相同的数据

特点
  1. 数组也是对象,存储在堆中,变量通过引用地址访问数组
  2. 数组在内存中的地址是相邻的,内存为数组分配一段连续的空间存储数据
  3. 数组的大小是不可变的,创建数组的时候指定了大小,后续就不能更改
  4. 基本类型的数组,分配空间的默认值是基本数据类型的默认值,引用类型的默认值是 null
  5. String[] str = { } 只是创建了一个空数组对象,没有指定数组大小,所以不会分配数据空间,堆中存储的只是空的数组对象。后续赋值运行时会报下标过界的异常
    public static void main( String[] args ) {
        String[] str = { };
        str[0] = "a";                 //java.lang.ArrayIndexOutOfBoundsException
        System.out.println( str[0] );
        String[] str1 = new String[3];
        System.out.println( JSONUtil.toJsonStr( str1 ) );  // []
        str1[2] = "a";
        System.out.println( JSONUtil.toJsonStr( str1 ) );  //["a"]
        System.out.println( str1[0] );    //null
        System.out.println( str1[1] );    //null
        System.out.println( str1[2] );    //"a"

        int[] int0 = { 1, 2, 3 };
        System.out.println( int0[1] );   //2
        int[] int1 = new int[3];
        int1[2] = 3;
        System.out.println( JSONUtil.toJsonStr( int1 ) );  //[0,0,3]
    }

为什么有了数组还需要Java集合?

  1. 数组定长不可变,集合可以自动扩容

  2. 支持泛型,提高了类型的安全性和代码的可读性

  3. 提供了丰富的操作接口,极大的简化了对数据的操作

  4. 集合能更高效的处理复杂的数据

ArrayList

基于动态数组实现的集合类

特点
  1. 动态扩容:数组容量不够了会自动扩容
  2. 随机访问:可以通过数组下标(索引)快速访问元素(数据)
  3. 允许null元素:可以存入null值(后续获取这个元素进行后续操作会报空指针)
  4. 不是线程安全的
扩容机制

当list中容量不足的时候,会自动进行扩容,一般情况下是按照原数组的50%扩容

扩容的时候会创建一个新的数组,将原数组中的元素复制到新数组中

    //扩容:minCapacity:扩容的最小容量 newCapacity:按照原有的容量扩容50%
    private int newCapacity(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //如果是空数组扩容,在默认的10和minCapacity之间选个大的
        if (newCapacity - minCapacity <= 0) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return minCapacity;
        }
        //扩容50%后的容量比MAX_ARRAY_SIZE小,就选择扩容newCapacity大小,
        //否则按照hugeCapacity方法中规则扩容
        return (newCapacity - MAX_ARRAY_SIZE <= 0)
            ? newCapacity
            : hugeCapacity(minCapacity);
    }

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE)
            ? Integer.MAX_VALUE
            : MAX_ARRAY_SIZE;
    }

 数组在扩容的时候,要创建新的数组并且复制数据,时间复杂度为O(n),要避免频繁扩容

常用方法
构造方法

提供了3种构造

  1. 无参构造:创建默认容量为10的空数组
  2. 初始化容量构造:创建一个入参指定大小的空数组
  3. 特定集合构造:创建一个包含特定集合元素的数组
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
   
    private static final int DEFAULT_CAPACITY = 10;  //默认初始化容量

   
    private static final Object[] EMPTY_ELEMENTDATA = {}; //入参为初始化容量的空数组

    
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //无参构造的空数组

   
    transient Object[] elementData;  //存储数据的数组

    
    private int size;

    //无参构造函数:创建的是初始化容量为10的空数组
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    //有参构造函数:入参为初始化容量,initialCapacity > 0,创建大小为入参的数组; 
    //initialCapacity == 0 创建一个空数组
    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);
        }
    }
    
    //入参为集合的构造函数:创建一个包含指定集合元素的数组。
    //elementData 接收的是一个新数组
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // defend against c.toArray (incorrectly) not returning Object[]
            // (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }
}
 添加元素
尾部添加元素

时间复杂度为O(1)

    private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length)
            elementData = grow();   //下标(索引)为数组长度,扩容
        elementData[s] = e;
        size = s + 1;
    }

    //在list尾部添加元素
    public boolean add(E e) {
        modCount++;
        add(e, elementData, size);
        return true;
    }
指定位置添加元素

时间复杂度为O(n),添加位置后的元素都要后移

    //指定索引位(下标)添加元素
    public void add(int index, E element) {
        rangeCheckForAdd(index);  //检查索引是否超过数组长度,超过抛出IndexOutOfBoundsException异常
        modCount++;
        final int s;
        Object[] elementData;
        if ((s = size) == (elementData = this.elementData).length)
            elementData = grow();              //数组实际元素个数等于数据长度,扩容
        System.arraycopy(elementData, index,
                         elementData, index + 1,
                         s - index);                //添加索引位后元素后移
        elementData[index] = element;               //设置值
        size = s + 1;
    }
list中添加集合元素
    //向list中添加指定集合元素
    public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        modCount++;
        int numNew = a.length;
        if (numNew == 0)
            return false;
        Object[] elementData;
        final int s;
        //如果加入的Collection长度大于elementData剩余容量,扩容
        if (numNew > (elementData = this.elementData).length - (s = size))
            elementData = grow(s + numNew);
        //拷贝数据
        System.arraycopy(a, 0, elementData, s, numNew);
        size = s + numNew;
        return true;
    }
删除元素
删除指定索引位元素

删除尾部,时间复杂度为O(1);删除其他位置,时间复杂度为O(n)

     //删除指定索引位元素
     public E remove(int index) {
        Objects.checkIndex(index, size);    //检查索引位是否越界
        final Object[] es = elementData;

        @SuppressWarnings("unchecked") E oldValue = (E) es[index];
        fastRemove(es, index);

        return oldValue;
    }

    private void fastRemove(Object[] es, int i) {
        modCount++;
        final int newSize;
        if ((newSize = size - 1) > i)
            //数组数据复制(删除索引位之后的数据前移)
            System.arraycopy(es, i + 1, es, i, newSize - i);
        es[size = newSize] = null;
    }
删除指定元素

循环遍历数组找到指定元素,再删除元素,时间复杂度为O(n)

    //删除指定元素:如果被删除的元素是 null 值,循环判断es[i] == null;
    //如果元素不是 null 值,循环判断 o.equals(es[i])
    public boolean remove(Object o) {
        final Object[] es = elementData;
        final int size = this.size;
        int i = 0;
        found: {
            if (o == null) {
                for (; i < size; i++)
                    if (es[i] == null)
                        break found;
            } else {
                for (; i < size; i++)
                    if (o.equals(es[i]))
                        break found;
            }
            return false;
        }
        //删除元素
        fastRemove(es, i);
        return true;
    }
获取元素

时间复杂度为O(1)

    //获取指定索引位元素
    public E get(int index) {
        Objects.checkIndex(index, size);
        return elementData(index);
    }

    E elementData(int index) {
        return (E) elementData[index];
    }
删除所有元素
    public void clear() {
        modCount++;
        final Object[] es = elementData;
        for (int to = size, i = size = 0; i < to; i++)
            es[i] = null;
    }
评论
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值