盒子
盒子
文章目录
  1. ArrayList
    1. 参考
    2. 前言
    3. 类名
    4. 成员变量
      1. 解释
      2. 总结
    5. 时间复杂度
    6. contains(Object o)
    7. 构造方法

ArrayList

ArrayList

参考

JDKSourceCode1.8

木杉的博客

泛型通配符的概念

前言

底层是 array 实现的。很像学 C 时老师会布置的那种作业,用数组实现一个 List…

类名

1
2
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable

主要是实现 List 接口。

成员变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
* 默认容量
*/
private static final int DEFAULT_CAPACITY = 10;

/**
* 空的对象数组
*/
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
* 默认的空数组
* 无参构造函数创建的数组
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
* 存放数据的数组的缓存变量,不可序列化。
* 因为 elementData 的大小一般比 ArrayList 当前存放的数据个数要大,如果序列化的时候直接把整个 * elementData序列化了,会很浪费空间的,所以ArrayList并没有这么做,而是在writeObject和 * readObject中自定义序列化、反序列化的方法。
*/
transient Object[] elementData;

/**
* 元素数量
* @serial
*/
private int size;

解释

  • 为什么有一个 EMPTY_ELEMENTDATA 还有一个DEFAULTCAPACITY_EMPTY_ELEMENTDATA

查看构造函数,发现 public ArrayList() 使用到 DEFAULTCAPACITY_EMPTY_ELEMENTDATA ,而 public ArrayList(int initialCapacity) 使用到 EMPTY_ELEMENTDATA

这两个空数组虽然对应的都是空 ArrayList,但是具有不同的含义。

1
2
1. List<Integer> list = new ArrayList<Integer>();
2. List<Integer> list = new ArrayList<Integer>(0);

当使用 2. 这种构造方式时,就默认用户对定义的容器的大小是有预期的(虽然是 0)。

在执行 add() 方法时,会先进行对数组大小的判断,如果大小不足,会进行扩容。

1
2
3
4
5
6
7
public boolean add(E e) {
// 扩容 --不一定需要扩容嘛,有判断的过程
ensureCapacityInternal(size + 1); // Increments modCount!!
// 将e赋值给elementData的size+1的位置
elementData[size++] = e;
return true;
}

ensureCapacityInternal() 方法的内部,有一个判断与扩容的过程。在第一次执行 add() 方法时,如果使用无参构造函数,会默认用户对容器的大小没有预期,所以把容器扩展为默认的 DEFAULT_CAPACITY 大小。

否则的话,就按照一般的增长方式来增长容器大小。

1
2
3
4
5
//为了得到最小的扩容容量
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
  • transient Object[] elementData 中 transient 修饰符什么意思?

transient 表示在序列化的时候不会序列化该字段。

实现 Serializable 接口,就可以序列化,序列化是为了数据的传输。

平时使用情形:面对用户的敏感信息,银行账号等,不适合在网络上操作,就不序列化。

这里不序列化是为了优化空间使用,把序列化的操作放在了其他地方按情况操作。

总结

  • ArrayList的无参数构造函数新建的长度为0,添加第一个元素后,长度为默认长度10
  • ArrayList指定新建的长度为0,添加第一个元素后,长度为1,为正常增长结果
  • ArrayList通过数组存放数据,成员是elementData

时间复杂度

  • size,isEmpty 都由常量 size 维护,调用是常数时间
  • get,set 由于底层使用 array,调用是常数时间
  • iterator 和 listIterator 的调用是常数时间的。(为什么?因为直接返回一个 iterator 和 listIterator 对象?)

  • 插入,删除,查找的时间复杂度为O(N)。其他所有操作也都是线性时间复杂度。

很容易想象,在插入,删除,查找时都需要遍历,所以时间复杂度为 O(n),除此之外,插入和删除还会执行数组的拷贝,所以效率不高,还会造成内存浪费。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* 在ArrayList的index位置,添加元素element,会检查添加的位置和容量
*
* @param index 指定元素将被插入的索引
* @param element 要插入的元素
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
// 判断index是否越界
rangeCheckForAdd(index);
// 扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
//public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length)
//src:源数组; srcPos:源数组要复制的起始位置; dest:目的数组; destPos:目的数组放置的起始位置; length:复制的长度
// 将elementData从index位置开始,复制到elementData的index+1开始的连续空间
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 在elementData的index位置赋值element
elementData[index] = element;
// ArrayList的大小加一
size++;
}

同理,在 remove() 中也涉及到 System.arraycopy()。

contains(Object o)

用 indexOf

构造方法

《java 编程思想》

所有的 Collection 子类型都有一个接受另一个 Collection 对象的构造器,用所接受的 Collection 对象中的元素来填充新的容器.

public boolean addAll(Collection<? extends E> c) 也是接受这样的对象。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* 带参数Collection的构造方法
*
* 这个的意思就是构造时可以接受 Collection 的子类初始化
* 比如 接受 LinkedList 的实例
*
* 继承自 E 的任意类型
*
* @param c 其元素将被放入此列表中的集合
* @throws NullPointerException 如果指定的集合是空的
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {//这一段是为什么?
// c.toarray可能(错误地)不返回对象[](见JAVA BUG编号6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// 使用空数组
this.elementData = EMPTY_ELEMENTDATA;
}
}

测试达到的效果:

1
2
3
4
5
6
7
8
9
10
11
ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(1);

LinkedList<Integer> linkedList = new LinkedList<>();
linkedList.add(2);

ArrayList<Integer> arrayList1 = new ArrayList<>(arrayList);
System.out.println(arrayList1);

ArrayList<Integer> arrayList2 = new ArrayList<>(linkedList);
System.out.println(arrayList2);

输出

1
2
[1]
[2]