【Java集合-3】ArrayList简析

待我称王封你为后i 2023-10-18 21:37 27阅读 0赞

#### Java集合03 ArrayList简析 ####

*  1 ArrayList说明
 *   *  1.1 ArrayList简介
     *  ArrayList继承关系
     *  1.2 ArrayList数据结构
     *  1.3 ArrayList构造函数
     *  1.4 ArrayList的API
 *  2 ArrayList常用操作
 *   *  2.1 ArrayList遍历
     *  2.2 ArrayList排序
     *  2.3 ArrayList删除元素
 *  3 ArrayList部分方法源码（基于JDK1.8）
 *   *  3.1 get(int index)
     *  3.2 add(E e)
     *  3.3 remove(Object o)
     *  3.4 addAll(Collection<? extends E> c)

在前面的集合框架那一章中，简单总结了Java集合的架构，List是Collection下的一大分支，而ArrayList又是List中最为常用的。本章将对ArrayList做一个总结，以供将来回顾之用。

## 1 ArrayList说明 ##

### 1.1 ArrayList简介 ###

ArrayList是一个数组队列，相当于动态数组。与Java中的数组相比，它的容量能动态增长。

1.  ArrayList 是一个数组队列，继承了AbstractList，实现了List，提供了元素添加、删除、修改、遍历等功能。
2.  ArrayList 实现了RandmoAccess接口，即提供了随机访问功能（通过元素序号快速获取元素，即所谓的快速访问）。
3.  ArrayList 实现了Cloneable接口，即覆盖了函数clone()，能被克隆。
4.  ArrayList 实现java.io.Serializable接口，这意味着ArrayList支持序列化，能通过序列化去传输。
5.  ArrayList **线程不安全**，在多线程中可以选择CopyOnWriteArrayList。

### ArrayList继承关系 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L211X3dpbmQ_size_16_color_FFFFFF_t_70]

### 1.2 ArrayList数据结构 ###

ArrayList的成员变量：

//初始化默认容量
    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;
    // 数组能申请的最大数量
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

成员变量中的elementData 和 size 是两个比较重要的参数：

1.  elementData 是"Object\[\]类型的数组"，它保存了添加到ArrayList中的元素。实际上，elementData是个动态数组，我们能通过构造函数 ArrayList(int initialCapacity)来执行它的初始容量为initialCapacity；如果通过不含参数的构造函数ArrayList()来创建ArrayList，则elementData的容量默认是10。elementData数组的大小会根据ArrayList容量的增长而动态的增长，具体的增长方式，请参考源码分析中的ensureCapacity()函数。
2.  size 则是动态数组的实际大小。

### 1.3 ArrayList构造函数 ###

ArrayList提供了三个构造函数：

// 默认构造函数
    public ArrayList()
    
    // capacity:ArrayList的默认容量大小。增加数据导致容量不足时，ArrayList会扩容，增加上一次容量大小的一半。
    public ArrayList(int capacity) {
        
    	// 当 initialCapacity > 0 时，初始化对应大小的数组
      	if (initialCapacity > 0) {
        
        	this.elementData = new Object[initialCapacity];
      	// 为 0 时，用指向EMPTY_ELEMENTDATA
      	} else if (initialCapacity == 0) {
        
        	this.elementData = EMPTY_ELEMENTDATA;
      	} else {
        
        	throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
      	}
    }
    
    // 创建一个包含collection的ArrayList
    public ArrayList(Collection<? extends E> collection) {
        
    	elementData = c.toArray();
     	if ((size = elementData.length) != 0) {
        
        // c.toArray不返回Object[]的时候，则进行数组拷贝
        	if (elementData.getClass() != Object[].class)
          		elementData = Arrays.copyOf(elementData, size, Object[].class);
      	} else {
        
        // 如果为空，则指向EMPTY_ELEMENTDATA
        	this.elementData = EMPTY_ELEMENTDATA;
      	}
    }

### 1.4 ArrayList的API ###

<table> 
 <thead> 
  <tr> 
   <th>返回值</th> 
   <th>方法</th> 
   <th>描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>boolean</td> 
   <td>add(E e)</td> 
   <td>将指定的元素添加到此列表的尾部。</td> 
  </tr> 
  <tr> 
   <td>void</td> 
   <td>add(int index, E element)</td> 
   <td>将指定的元素插入此列表中的指定位置。</td> 
  </tr> 
  <tr> 
   <td>boolean</td> 
   <td>addAll(Collection&lt;? extends E&gt; c)</td> 
   <td>按照指定 collection 的迭代器所返回的元素顺序，将该 collection 中的所有元素添加到此列表的尾部。</td> 
  </tr> 
  <tr> 
   <td>boolean</td> 
   <td>addAll(int index, Collection&lt;? extends E&gt; c)</td> 
   <td>从指定的位置开始，将指定 collection 中的所有元素插入到此列表中。</td> 
  </tr> 
  <tr> 
   <td>void</td> 
   <td>clear()</td> 
   <td>移除此列表中的所有元素。</td> 
  </tr> 
  <tr> 
   <td>Object</td> 
   <td>clone()</td> 
   <td>返回此 ArrayList 实例的浅表副本。</td> 
  </tr> 
  <tr> 
   <td>boolean</td> 
   <td>contains(Object o)</td> 
   <td>如果此列表中包含指定的元素，则返回 true。</td> 
  </tr> 
  <tr> 
   <td>void</td> 
   <td>ensureCapacity(int minCapacity)</td> 
   <td>如有必要，增加此 ArrayList 实例的容量，以确保它至少能够容纳最小容量参数所指定的元素数。</td> 
  </tr> 
  <tr> 
   <td>E</td> 
   <td>get(int index)</td> 
   <td>返回此列表中指定位置上的元素。</td> 
  </tr> 
  <tr> 
   <td>int</td> 
   <td>indexOf(Object o)</td> 
   <td>返回此列表中首次出现的指定元素的索引，或如果此列表不包含元素，则返回 -1。</td> 
  </tr> 
  <tr> 
   <td>boolean</td> 
   <td>isEmpty()</td> 
   <td>如果此列表中没有元素，则返回 true</td> 
  </tr> 
  <tr> 
   <td>int</td> 
   <td>lastIndexOf(Object o)</td> 
   <td>返回此列表中最后一次出现的指定元素的索引，或如果此列表不包含索引，则返回 -1。</td> 
  </tr> 
  <tr> 
   <td>E</td> 
   <td>remove(int index)</td> 
   <td>移除此列表中指定位置上的元素。</td> 
  </tr> 
  <tr> 
   <td>boolean</td> 
   <td>remove(Object o)</td> 
   <td>移除此列表中首次出现的指定元素（如果存在）</td> 
  </tr> 
  <tr> 
   <td>protected void</td> 
   <td>removeRange(int fromIndex, int toIndex)</td> 
   <td>移除列表中索引在 fromIndex（包括）和 toIndex（不包括）之间的所有元素。</td> 
  </tr> 
  <tr> 
   <td>E</td> 
   <td>set(int index, E element)</td> 
   <td>用指定的元素替代此列表中指定位置上的元素。</td> 
  </tr> 
  <tr> 
   <td>int</td> 
   <td>size()</td> 
   <td>返回此列表中的元素数。</td> 
  </tr> 
  <tr> 
   <td>Object[]</td> 
   <td>toArray()</td> 
   <td>按适当顺序（从第一个到最后一个元素）返回包含此列表中所有元素的数组。</td> 
  </tr> 
  <tr> 
   <td> T[]</td> 
   <td>toArray(T[] a)</td> 
   <td>按适当顺序（从第一个到最后一个元素）返回包含此列表中所有元素的数组；返回数组的运行时类型是指定数组的运行时类型。</td> 
  </tr> 
  <tr> 
   <td>void</td> 
   <td>trimToSize()</td> 
   <td>将此 ArrayList 实例的容量调整为列表的当前大小。</td> 
  </tr> 
 </tbody> 
</table>

## 2 ArrayList常用操作 ##

### 2.1 ArrayList遍历 ###

ArrayList支持三种遍历方式：迭代器遍历、随机访问遍历、增强for遍历

public static void main(String[] args) {
        
    	List<Integer> list = Arrays.asList(1, 7, 5, 3, 8, 2);
    	// 迭代器遍历
    	Iterator<Integer> it = list.iterator();
    	while (it.hasNext()) {
        
    		int value = (int) it.next();
    		System.out.println(value + " ");
    	}
    	
    	// 随机访问遍历
    	for (int i = 0; i < list.size(); i++) {
        
    		int value = list.get(i);
    		System.out.println(value + " ");
    	}
    
    	// 增强for遍历
    	for (int value : list) {
        
    		System.out.print(value + " ");
    	}
    }

### 2.2 ArrayList排序 ###

ArrayList集合排序依赖于Collections.sort()，其默认是按升序排序的，如果想要降序排列，需重写Collections.sort()方法。

public static void main(String[] args) {
        
    	List<Integer> list = Arrays.asList(1, 7, 5, 3, 8, 2);
    	
    	// 按照字典顺序排序
    	Collections.sort(list);
    	System.out.println("默认排序：" + list);
    
    	// 自定义排序
    	Collections.sort(list, new Comparator<Integer>() {
        
    		@Override
    		public int compare(Integer o1, Integer o2) {
        
    			int i = o1.compareTo(o2);
    			// int、double型，可以直接用o1 > o2做if的判断条件，String类型只能用compareTo方法
    			if (i > 0) 
    				return -1;
    			return 1;
    		}
    	});
    	System.out.println("自定义排序：" + list);
    }

运行结果：

默认排序：[1, 2, 3, 5, 7, 8]
    自定义排序：[8, 7, 5, 3, 2, 1]

### 2.3 ArrayList删除元素 ###

现在有 \[a,a,b,c,e,a,d\] 这么一个ArrayList集合，删除该集合中的所有的"a"。也许有人觉得很简单，并给出下面代码：

public static void main(String[] args) {
        
    	List<String> list = new ArrayList<>();
    	list.add("a");
    	list.add("a");
    	list.add("d");
    	list.add("c");
    	list.add("a");
    	list.add("e");
    	list.add("m");
    
    	// 错误的删除方法：
    	for (int i = 0; i < list.size(); i++) {
        
    		String value = list.get(i);
    		if (value.equals("a"))
    			list.remove(i);
    	}
    	System.out.println(list);
    }

运行结果：

[a, d, c, e, m]

可以看到，当有连续两个以上a元素时，最终会保留一个。原因是，删除元素后，ArrayList集合的索引重新排列，删除元素后面的元素索引全部向前移动一位，本例中，删除第一个a后，第二个a的索引就由1变成了0，而for循环已经运行过0了，导致第二个a未被删除。  
**正确的做法是倒序遍历删除：**

for (int i = list.size()-1; i >= 0; i--) {
        
    	String value = list.get(i);
    	if (value.equals("a"))
    		list.remove(i);
    }

## 3 ArrayList部分方法源码（基于JDK1.8） ##

### 3.1 get(int index) ###

// 先检查index范围是否正确，正确的话从数组里取出元素
    public E get(int index) {
        
      rangeCheck(index);
      return elementData(index);
    }
    
    E elementData(int index) {
        
      return (E) elementData[index];
    }
    private void rangeCheck(int index) {
        
      // 如果index 大于 存储的个数，则抛出异常
      if (index >= size)
        // outOfBoundsMsg里面就是简单的字符串拼接。
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

### 3.2 add(E e) ###

public boolean add(E e) {
        
      	// 对于刚初始化的数组，要初始化它的大小
      	// 判断数组大小是否足够，如果不够大，扩容
      	// 对于扩容要判断是否到达数组的最大数量
      	ensureCapacityInternal(size + 1);
      	//赋值，然后指针走到下一个空位
      	elementData[size++] = e;
     	return true;
    }
    
    private void ensureCapacityInternal(int minCapacity) {
        
      	// 上述情况一：初始化数组的大小
      	if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        
        	// 取minCapacity和DEFAULT_CAPACITY中较大的那个
        	minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
      	}
      	// 检查有没有扩容的必要
      	ensureExplicitCapacity(minCapacity);
    }
    
    private void ensureExplicitCapacity(int minCapacity) {
        
      	// 修改次数的计数器(在AbstractList中定义的)
      	modCount++;
      	// 如果需要的空间大小 > 当前数组的长度，则进行扩容
      	if (minCapacity - elementData.length > 0)
        	grow(minCapacity);
    }
    
    private void grow(int minCapacity) {
        
    	// 记录旧的length
      	int oldCapacity = elementData.length;
      	// 扩容1.5倍, 位运算符效率更高
      	int newCapacity = oldCapacity + (oldCapacity >> 1);
      	// 判断有没有溢出
      	if (newCapacity - minCapacity < 0)
        	newCapacity = minCapacity;
      	// 判断有没有超过最大的数组大小
      	if (newCapacity - MAX_ARRAY_SIZE > 0)
        	//计算最大的容量
        	newCapacity = hugeCapacity(minCapacity);
      	// 旧数组拷贝到新的大小数组
      	elementData = Arrays.copyOf(elementData, newCapacity);
    }
    // 最大的容量
    private static int hugeCapacity(int minCapacity) {
        
       	// 大小溢出
       	if (minCapacity < 0)
       		throw new OutOfMemoryError();
    	// 需要的最小容量 > 数组最大的长度，则取Integer的最大值，否则取数组最大长度
      	return (minCapacity > MAX_ARRAY_SIZE) ?
        	Integer.MAX_VALUE :
      	MAX_ARRAY_SIZE;
    }

### 3.3 remove(Object o) ###

public boolean remove(Object o) {
        
      	// 判断o为null，loop遍历找到为null的元素
      	if (o == null) {
        
        	for (int index = 0; index < size; index++)
          		if (elementData[index] == null) {
        
            	fastRemove(index);
            	return true;
          	}
      	// 不为null
      	} else {
        
        	for (int index = 0; index < size; index++)
          		if (o.equals(elementData[index])) {
        
            	fastRemove(index);
            	return true;
          	}
      	}
      	return false;
    }
    
    // 与上面的remove(int index) 类似
    private void fastRemove(int index) {
        
      	modCount++;
      	int numMoved = size - index - 1;
      	if (numMoved > 0)
        	System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
      	elementData[--size] = null;
    }

**set(int index, E element)**

public E set(int index, E element) {
        
      	rangeCheck(index);
      	// 记录旧的值
      	E oldValue = elementData(index);
      	//在原位置设置新的值
      	elementData[index] = element;
      	return oldValue;
    }

### 3.4 addAll(Collection<? extends E> c) ###

public boolean addAll(Collection<? extends E> c) {
        
      	Object[] a = c.toArray();
      	int numNew = a.length;
      	// 对于新的最小长度进行判断处理
      	ensureCapacityInternal(size + numNew);
      	//将a数组，从index-0开始，拷贝numNew个，到elementData的size位置
      	System.arraycopy(a, 0, elementData, size, numNew);
      	//将size增加numNew个
      	size += numNew;
      	return numNew != 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L211X3dpbmQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190713191553314.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L211X3dpbmQ=,size_16,color_FFFFFF,t_70