Java ArrayList小记
1.基本用法
ArrayList是一个泛型容器，新建ArrayList需要实例化泛型参数，比如:
ArrayList<String> StrList = new ArrayList<>();
ArrayList<Integer> intList = new ArrayList<>();
ArrayList的主要方法有：
// 添加元素到末尾
public boolean add(E e)
// 判断是否为空
public boolean isEmpty()
// 获取大小
public int size()
// 获取指定位置（索引）的元素
public E get(int index)
// 查找指定元素，若找到，返回索引位置，否则返回-1
public int indexOf(Object o)
// 从后往前找
public int lastIndexOf(Object o)
// 判断是否包含指定元素，根据equals方法的返回值
public boolean contains(Object o)
// 删除指定位置的元素，返回值为被删除的元素对象
public E remove(int index)
// 删除指定元素，只删除第一个相同的元素，若o为null,则删除值为null的元素
public boolean remove(Object o)
// 清空元素
public void clear()
// 在指定位置插入元素，index为0表示插入最前面，index为ArrayList的长度表示插到最后面
public void add(int index, E element)
// 修改指定位置的元素内容
public E set(int index, E element)
简单示例：
ArrayList<String> strList = new ArrayList<>();
strList.add("我爱");
strList.add("编程");
for (int i = 0; i < strList.size(); i++) {
System.out.println(strList.get(i));
}
2.基本原理
ArrayList是基于数组实现的，内部有一个数组elementData，还有一个整数size记录实际的元素个数（基于Java 8），如下所示：
transient Object[] elementData;
private int size;
先来看下add和remove方法的实现。add方法的主要代码为：
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
首先调用ensureCapacityInternal确保数组容量是够的，ensureCapacityInternal的代码为：
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
首先calculateCapacity方法判断数组是否为空，若为空，则首次至少分配的大小为DEFAULT_CAPACITY（默认为10）。然后调用ensureExplicitCapacity方法，modCount表示内部的修改次数，如果需要的长度大于当前数组的长度，则调用grow方法，其主要代码为：
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// 右移一位相当于除以2，所以，newCapacity相当于oldCapacity的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果扩展1.5倍还是小于minCapacity，就扩展为minCapacity
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 确保newCapacity不超过VM允许的最大值
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
再来看看remove方法的代码：
public E remove(int index) {
// 检查给定索引是否在范围内，若不在抛出运行时异常。
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
// 计算要移动的元素个数，index后面的都要移动
int numMoved = size - index - 1;
if (numMoved > 0)
// 通过数组copy来移动元素
System.arraycopy(elementData, index+1, elementData, index, numMoved);
// 数组最后一位，置为null,完成删除
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
使用modCount记录修改次数。使用数组拷贝来移动元素，最后将“移动”到末尾的元素设置为null，完成删除。
3.迭代
来看下迭代操作的例子，循环打印ArrayList中的每个元素，ArrayList支持foreach语法：
ArrayList<Integer> list = new ArrayList<>();
list.addAll(Arrays.asList(9, 5, 6, 7));
for (Integer i : list) {
System.out.print(i + " ");
}
System.out.println(" ");
// 或者
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i) + " ");
}
使用foreach看上去更为简洁，具体选择使用哪种要根据具体情况，如若需要使用索引就不方便使用foreach了。那么这种foreach语法背后是怎么实现的呢？其实，编译器会将它转换为如下代码：
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next() + " ");
}
ArrayList实现了Iterable接口，Iterable表示可迭代，Java 8中迭代器接口：
public interface Iterable<T> {
Iterator<T> iterator();
default void forEach(Consumer<? super T> action) {
Objects.requireNonNull(action);
for (T t : this) {
action.accept(t);
}
}
default Spliterator<T> spliterator() {
return Spliterators.spliteratorUnknownSize(iterator(), 0);
}
}
一个抽象方法和两个默认方法，默认方法是java 8新增的，具体使用方式参考API文档 。来看下iterator方法，它返回一个实现了Iterator接口的对象，Java 8中Iterator接口的定义为：
public interface Iterator<E> {
boolean hasNext();
E next();
default void remove() {
throw new UnsupportedOperationException("remove");
}
default void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (hasNext())
action.accept(next());
}
}
hasNext()判断是否还有下一个元素，next()返回下一个元素，remove()删除最后返回的元素，只读访问的基本模式类似于：
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next() + " ");
}
只要对象实现了Iterable接口，就可以使用foreach语法，编译器会转换为调用Iterable和Iterator接口的方法。下面来区分下这两个接口：
1. Iterable表示对象可以被迭代，它有一个iterator方法，返回Iterator对象，实际通过Iterator接口的方法进行遍历；
2. 如果对象实现了Iterable接口，就可以使用foreach语法；
3. 类可以不实现Iterable，也可以创建Iterator对象。
除了iterator()，ArrayList还提供了两个返回Iterator接口的方法：
public ListIterator<E> listIterator()
public ListIterator<E> listIterator(int index)
ListIterator扩展了Iterator接口，增加了一些方法，向前遍历，添加元素，修改元素，返回索引位置等，添加的方法有：
public interface ListIterator<E> extends Iterator<E> {
boolean hasPrevious();
E previous();
int nextIndex();
int previousIndex();
void set(E e);
void add(E e);
}
listIterator()方法返回的迭代器从0开始，而listIterator(int index)方法返回的迭代器从指定位置的index开始。比如反向遍历：
public static void reverseTraverse(List<Integer> list) {
ListIterator<Integer> it = list.listIterator(list.size());
while (it.hasPrevious()) {
System.out.println(it.previous() + " ");
}
}
关于迭代器，有一种常见的错误使用，就是在迭代的中间调用容器的删除方法。比如如下代码：
public static void wrongUsage(List<Integer> list) {
for (Integer x : list) {
if (x < 20) {
list.remove(x);
}
}
/**
* java.util.ConcurrentModificationException
*/
}
运行时会抛出上面注释中异常，发生了并发修改异常。由于迭代器内部会维护一些索引位置相关的数据，要求在迭代过程中，容器不能发生结构性变化，否则这些索引位置就失效了。结构性变化指的是添加、插入和删除元素，只是修改元素内容不算结构性变化。那么如何避免异常呢？可以使用迭代器的remove方法：
public static void remove(ArrayList<Integer> list) {
Iterator<Integer> it = list.iterator();
while (it.hasNext()) {
if (it.next() < 20) {
it.remove();
}
}
}
为什么使用迭代器自己的remove方法不抛出异常呢？来看下ArrayList中iterator方法的实现：
public Iterator<E> iterator() {
return new Itr();
}
新建了一个Itr对象，Itr是一个成员内部类，实现了Iterabtor接口，声明为：
private class Itr implements Iterator<E> {
// 下一个要返回的元素位置
int cursor = 0;
// 最后一个返回的索引位置，如果没有，为-1
int lastRet = -1;
// 期望的修改次数
int expectedModCount = modCount;
public boolean hasNext() {
return cursor != size();
}
public E next() {
checkForComodification();
try {
int i = cursor;
E next = get(i);
lastRet = i;
cursor = i + 1;
return next;
} catch (IndexOutOfBoundsException e) {
checkForComodification();
throw new NoSuchElementException();
}
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
// 迭代器的删除调用了外部类的remove,同时又更新了cursor、lastRet和expectedModCountde值，所以它可以正确的删除
AbstractList.this.remove(lastRet);
if (lastRet < cursor)
cursor--;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException e) {
throw new ConcurrentModificationException();
}
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
modCount是外部类中当前修改次数，成员内类可以直接访问外部类的实例变量。每次发生结构变化的时候modCount都会增加1，而每次迭代器操作的时候都会检查expectedModCount是否与modCount相等，这样就能检测出结构变化了。在使用迭代器的remove时有一点需要注意，在调用remove之前必须先调用next，否则会抛出java.lang.IllegalStateException 异常，因为直接调用lastRet参数默认为-1，还没被赋值。
迭代器表示的是一种关注点分离的思想，将数据的实际组织方式与数据的迭代遍历相分离，是一种常见的设计模式。定义如下：
它提供一种方法访问一个容器对象中各个元素， 而又不需暴露该对象的内部细节。--迭代器模式
4. ArrayList实现的接口
Java的各种容器类有一些共性的操作，这些共性以接口的方式体现，例如Iterable，此外AarrayList还实现了三个主要的接口：Collection、List和RandomAccess接口。
1. Collection
Conllection表示一个数据的集合，位置间没有位置或顺序的概念，Java 8中定义的接口为：
public interface Collection<E> extends Iterable<E> {
// 集合大小
int size();
// 判断集合是否为空
boolean isEmpty();
// 判断集合是否包含指定元素
boolean contains(Object o);
// 迭代器
Iterator<E> iterator();
// 转换为数组
Object[] toArray();
// 转换为数组并制定返回类型
<T> T[] toArray(T[] a);
// 添加元素
boolean add(E e);
// 删除指定元素
boolean remove(Object o);
// 判断给定集合是否包含在当前集合
boolean containsAll(Collection<?> c);
// 将给定集合添加到当前集合中
boolean addAll(Collection<? extends E> c);
// 将给定集合的内容从当前集合中移除
boolean removeAll(Collection<?> c);
default boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
boolean removed = false;
final Iterator<E> each = iterator();
while (each.hasNext()) {
if (filter.test(each.next())) {
each.remove();
removed = true;
}
}
return removed;
}
// 判断当前集合中是否包含给定的集合
boolean retainAll(Collection<?> c);
// 清空集合
void clear();
boolean equals(Object o);
int hashCode();
@Override
default Spliterator<E> spliterator() {
return Spliterators.spliterator(this, 0);
}
default Stream<E> stream() {
return StreamSupport.stream(spliterator(), false);
}
default Stream<E> parallelStream() {
return StreamSupport.stream(spliterator(), true);
}
}
默认方法略过，可查看API学习。抽象类AbstractCollection对这些方法都提供了默认实现，ArrayList继承了AbstactList，而AbstractList又继承了AbstractCollection，ArrayList对其中的一些方法进行了重写，以提供更高的效率。
2. List
List表示有顺序并且可重复的数据集合，它扩展了Collection接口（java 8）：
public interface List<E> extends Collection<E> {
int size();
boolean isEmpty();
boolean contains(Object o);
Iterator<E> iterator();
<T> T[] toArray(T[] a);
boolean add(E e);
boolean remove(Object o);
boolean containsAll(Collection<?> c);
boolean addAll(Collection<? extends E> c);
boolean addAll(int index, Collection<? extends E> c);
boolean removeAll(Collection<?> c);
boolean retainAll(Collection<?> c);
default void replaceAll(UnaryOperator<E> operator) {
Objects.requireNonNull(operator);
final ListIterator<E> li = this.listIterator();
while (li.hasNext()) {
li.set(operator.apply(li.next()));
}
}
@SuppressWarnings({"unchecked", "rawtypes"})
default void sort(Comparator<? super E> c) {
Object[] a = this.toArray();
Arrays.sort(a, (Comparator) c);
ListIterator<E> i = this.listIterator();
for (Object e : a) {
i.next();
i.set((E) e);
}
}
void clear();
boolean equals(Object o);
int hashCode();
E get(int index);
E set(int index, E element);
void add(int index, E element);
E remove(int index);
int indexOf(Object o);
int lastIndexOf(Object o);
ListIterator<E> listIterator();
ListIterator<E> listIterator(int index);
List<E> subList(int fromIndex, int toIndex);
@Override
default Spliterator<E> spliterator() {
return Spliterators.spliterator(this, Spliterator.ORDERED);
}
}
默认方法先混个脸熟，其它扩展的几个方法都和位置有关，可根据API文档学习。
3. RandomAccess
RandomAccess接口定义如下：
public interface RandomAccess {
}
这是一个标记接口，用于声明类的一种属性。实现该接口的类表示可以随机访问，就是具备类似数组那样的特性，数据在内存中是连续存放的，根据索引值就可以直接定位到具体的元素，访问效率很高。根据这个声明，在一些算法代码中可以选择效率更高的实现。比如Collections类中的binarySearch方法：
public static <T>
int binarySearch(List<? extends Comparable<? super T>> list, T key) {
// 这里就根据是否实现了RandomAccess接口选择效率更高的算法
if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
return Collections.indexedBinarySearch(list, key);
else
return Collections.iteratorBinarySearch(list, key);
}
5. ArrayList特点总结
ArrayList内部是采用动态数组实现的：
1. 可以随机访问（实现了RandomAccess接口），按照索引位置进行访问效率很高效率为O（1），简单来说就是一步到位。
2. 在数组未排序的情况下，查找元素效率比较低，具体是O（N），N为数组内容长度，性能与数组长度成正比。
3. 添加元素的效率还可以，但是被重新分配和复制数组的开销被均摊了，添加N个元素的效率为O(N)。
4. 插入和删除元素的效率比较低，因为需要复制、移动元素，具体为O(N)。
---------- I love three things in this world. Sun, moon and you. Sun for morning, moon for night , and you forever .
最新文章
- 【知识积累】DES算法之C#加密&Java解密
- php中的ip2long和long2ip的理解
- swagger editor使用
- Java编程思想学习(十三) java I/O
- MySql5.6 Window超详细安装教程
- Swift基本语法以及与OC的比较
- 异常-JAVA
- adb shell am pm 用法
- Angular.js VS. Ember.js：谁将成为Web开发的新宠？
- [Codecademy] HTML&CSS 第三课：HTML Basic II
- ADO.NET（一）
- oracle在imp订单具体解释
- 关于ASCII,Unicode和UTF-8
- Java系统属性与Preferences API的简单介绍
- Log4j – Log4j 2 API
- [android] smartimageview&常见的开源代码
- CDRAF之Service mesh
- jdk各种包安装方式
- 代码统计工具-cloc
- html5 meta标签的认知储备
热门文章
- CF487E Tourists + 圆方树学习笔记（圆方树+树剖+线段树+multiset)
- 小白自制Linux开发板 五. Debian文件系统制作,以及WIFI配置、交换分区配置
- linux性能优化基础——iommu相关配置
- python json中的 dumps loads函数
- Convolutional Neural Network-week2编程题1（Keras tutorial - 笑脸识别）
- 北航OO第三单元总结
- Noip模拟13 2021.7.13：再刚题，就剁手&&生日祭
- DMA实现采样数据的直接搬运存储
- Maven还停留在导jar包？快来探索Nexus私服的新世界
- SprinMvc快速入门