【Java集合-3】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;

// 默认构造函数
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;
  	}
}

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

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]

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]

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

// 先检查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));
}

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

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

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

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