顺序存储线性表_ArrayList
2024-10-19 03:26:58
相信大家在日常开发过程中 List 应该使用的非常非常多，今天就来简单学习一下 List 的数据结构 顺序存储线性表。
一、什么是顺序存储线性表
顺序存储线性表是最基本、最简单、也是最常用的一种数据结构。
线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储），但是把最后一个数据元素的尾指针指向了首位结点）。
顺序存储线性表的相邻元素之间存在着序偶关系。如用（a1，…，ai-1，ai，ai+1，…，an）表示一个顺序表，则表中 ai-1 领先于 ai，ai 领先于 ai+1，称 ai-1 是 ai 的直接前驱元素，ai+1 是 ai 的直接后继元素。当 i=1,2，…，n-1 时，ai 有且仅有一个直接后继，当 i=2，3，…，n 时，ai 有且仅有一个直接前驱，n 为线性表的长度，如果 n==0 时，线性表为空表。
二、顺序存储线性表的特征
绝大多数的顺序存储线性表都有一下几个特征：
①. 线性表中都会存在唯一的一个 "首元素"。
②. 线性表中都会存在唯一的一个"尾元素"。
③. 线性表除最后一个元素外都存在"后继"。
④. 线性表除第一个元素外都存在"前驱"。
⑤. 存储位置连续，可以很方便的计算出各个元素的地址。
如果每个元素占用的存储单元为 C ，那么：
Loc（An） = Loc（An-1） + C
Loc（An） = Loc（A1） + （n - 1）* C
三、JDK源码解读
在 java 中，ArrayList 是典型的顺序存储线性表，下面来解读一下JDK 1.8 中 ArrayList 源码中的方法，以及父类，接口中的一些方法。
首先，进入到 ArrayList 中，简单看了一下ArrayList 的继承关系，ArrayList 继承 AbstractList， AbstractList 继承 AbstractCollection 类，实现了 List 接口， AbstractCollection 类实现了 Collection 接口，而 List 继承了 Collection 接口， Collection 继承了 Iterable 接口，下面就依次来简单解读这些接口以及类的实现方法以及作用。
ArrayList 与它的父类接口的关系图：
①. Iterable 接口
用途：Iterable 接口是 java 中的顶级接口之一，它的作用主要可以使实现类集合使用迭代器去遍历自己的元素。
方法：
| 方法名 | 参数 | 返回值 | 描述 |
| Iterator | 无 | Iterator<T> | 返回一个内部元素为 T 的迭代器 |
| forEach | Consumer接口 | void |
Iterable 接口中的默认方法，其中可以传入一个Consumer的接口，可以去遍历内部的每一个元素，并且可以自定义方法，对每一个元素进行操作 |
| spliterator | 无 | Spliterator<T> | Iterable 接口中的默认方法，创建并返回一个分割迭代器 |
public interface Iterable<T> {
/**
* 获取一个内部为 T 的迭代器
*
* @return 返回一个迭代器.
*/
Iterator<T> iterator();
/**
* 被 default 关键字修饰，表示该方法为本接口的默认方法，迭代一个
* 集合并传入一个方法实现来对集合的每一个元素进行操作。
*/
default void forEach(Consumer<? super T> action) {
Objects.requireNonNull(action);// 判空操作，如果 action 为 null 则返回，NullPointerExcation()；
for (T t : this) {
action.accept(t);
}
}
/**
* 此方法也是该接口的默认方法，获取一个可分割迭代器。
*/
default Spliterator<T> spliterator() {
return Spliterators.spliteratorUnknownSize(iterator(), );
}
}
②. Collection 接口
用途：Collection接口是高度抽象出来的集合类接口，其中包含了大多数集合所需要的共同的方法，如增、删、改、查等。
方法：
| 方法名 | 参数 | 返回值 | 描述 |
| size | 无 | int | 获取一个集合的元素个数 |
| isEmpty | 无 | boolean | 判断该集合是否为空集合 |
| contains | Object o | boolean | 判断该集合是否包含 o 元素 |
| iterator | 无 | Iterator<E> | 返回一个内部元素为 E 的迭代器 |
| toArray | 无 | Object[] | 将该集合转换为数组 |
| toArray | T[] a | T[] | 将集合中的元素转换到指定的数组中，如果指定数组为空，则将集合中的元素放入一个全新的数组中，如果不为空则返回传入的数组，并且传入数组的长度为集合元素的个数 |
| add | E e | boolean | 将元素e加入到集合中 |
| remove | Object o | boolean | 将 o 元素从集合中移除 |
| containsAll | Collection<?> c | boolean | 判断集合 c 是否被该集合包含 |
| addAll | Collection<? extends E> c | boolean | 将集合 c 中的元素都添加到该集合中 |
| removeAll | Collection<? extends E> c | boolean | 将该集合中所有 c 集合中出现的元素移除 |
| removeIf | Predicate<? super E> filter | boolean | Collection 接口中的默认方法，可以按照一定的规则去删除集合中的元素 |
| retainAll | Collection<?> c | boolean | 保留该集合中在 c 集合中存在的元素，其他元素进行移除 |
| clear | 无 | void | 清空集合 |
| equals | Object o | boolean | 用 o 与该集合进行比较 |
| hashCode | 无 | int | 获取该集合的hashCode值 |
| spliterator | 无 | Spliterator<T> | Collection 接口中的默认方法，创建并返回一个分割迭代器 |
| stream | 无 | Stream<E> |
Collection 接口中的默认方法，将该集合转换成Stream串行流 |
| parallelStream | 无 | Stream<E> | Collection 接口中的默认方法，将该集合转换成Stream并行流 |
public interface Collection<E> extends Iterable<E> {
// Query Operations
/**
* 获取一个集合的元素个数
*/
int size();
/**
* 判断该集合是否为空集合
*/
boolean isEmpty();
/**
* 判断该集合是否包含 o 元素
*/
boolean contains(Object o);
/**
* 返回一个内部元素为 E 的迭代器
*/
Iterator<E> iterator();
/**
* 将该集合转换为数组
*/
Object[] toArray();
/**
* 将集合中的元素转换到指定的数组中，如果指定数组为空，则将集合中的元素放入一个全新的数组中，如果不为空则返回传入的数组，并且传入数组的长度为集合元素的个数
*/
<T> T[] toArray(T[] a);
/**
* 将元素e加入到集合中
*/
boolean add(E e);
/**
* 将 o 元素从集合中移除
*/
boolean remove(Object o);
/**
* 判断集合 c 是否被该集合包含
*/
boolean containsAll(Collection<?> c);
/**
* 将集合 c 中的元素都添加到该集合中
*/
boolean addAll(Collection<? extends E> c);
/**
* 将该集合中所有 c 集合中出现的元素移除
*/
boolean removeAll(Collection<?> c);
/**
* Collection 接口中的默认方法，可以按照一定的规则去删除集合中的元素
*/
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;
}
/**
* 保留该集合中在 c 集合中存在的元素，其他元素进行移除
*/
boolean retainAll(Collection<?> c);
/**
* 清空集合
*/
void clear();
/**
* 用 o 与该集合进行比较
*/
boolean equals(Object o);
/**
* 获取该集合的hashCode值
*/
int hashCode();
/**
* Collection 接口中的默认方法，创建并返回一个分割迭代器
*/
@Override
default Spliterator<E> spliterator() {
return Spliterators.spliterator(this, 0);
}
/**
* Collection 接口中的默认方法，将该集合转换成Stream串行流
*/
default Stream<E> stream() {
return StreamSupport.stream(spliterator(), false);
}
/**
* Collection 接口中的默认方法，将该集合转换成Stream并行流
*/
default Stream<E> parallelStream() {
return StreamSupport.stream(spliterator(), true);
}
}
③. List 接口
用途：List 接口是 Conllection 接口的子接口，它可以定义一个可重复的线性集合，可以在不同的位置存放相同的元素。
方法 ：其中有许多方法与 Conllection接口的方法相同，就不在此一一列出
| 方法名 | 参数 | 返回值 | 描述 |
| addAll | int index, Collection<? extends E> c | boolean | 在指定位置index处添加集合元素c |
| replaceAll | UnaryOperator<E> operator | void | List 集合中的默认方法，对集合中的元素进行操作，将执行结果存入元素的位置 |
| sort | Comparator<? super E> c | void | 按照给定的排序规则进行排序 |
| get | int index | E | 返回列表中index位置的元素。 |
| set | int index, E element | E | 将列表中 index 位置的元素替换为 element |
| add | int index, E element | void | 在列表 index 位置添加元素 element |
| remove | int index | E | 删除 index 位置的元素 |
| indexOf | Object o | int | 返回 o 元素第一次出现的位置 |
| lastIndexOf | Object o | int | 返回 o 元素最后一次出现的位置 |
| listIterator | 无 | ListIterator<E> | 返回一个 ListIterator 迭代器 |
| subList | int fromIndex, int toIndex | List<E> | 返回集合从 fromIndex 的位置到 toIndex 位置的元素的集合 |
public interface List<E> extends Collection<E> {
/**
* 在指定位置index处添加集合元素c
*/
boolean addAll(int index, Collection<? extends E> 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); //使用数组排序的sort方法进行排序
ListIterator<E> i = this.listIterator();
for (Object e : a) { //再将该集合的每个位置进行替换
i.next();
i.set((E) e);
}
}
/**
* 返回列表中 index 位置的元素。
*/
E get(int index);
/**
* 将列表中 index 位置的元素替换为 element
*/
E set(int index, E element);
/**
* 在列表 index 位置添加元素 element
*/
void add(int index, E element);
/**
* 删除 index 位置的元素
*/
E remove(int index);
/**
* 返回 o 元素第一次出现的位置
*/
int indexOf(Object o);
/**
* 返回 o 元素最后一次出现的位置
*/
int lastIndexOf(Object o);
/**
* 返回一个 ListIterator 迭代器
*/
ListIterator<E> listIterator();
/**
* 返回一个 从 index 开始的 ListIterator 迭代器
*/
ListIterator<E> listIterator(int index);
// View
/**
* 返回集合从 fromIndex 的位置到 toIndex 位置的元素的集合
*/
List<E> subList(int fromIndex, int toIndex);
}
④. AbstractCollection 抽象类
用途：这个类是个抽象类，直接实现了Collection接口的方法，其中为 list 和 set 直接或者间接提供了方法实现。
方法：
| 方法名 | 参数 | 返回值 | 描述 |
| size | 无 | int | 抽象方法，由子类实现 |
| iterator | 无 | Iterator<E> | 上层的获取迭代器的方法，在这里没有实现，由子类实现 |
| isEmpty | 无 | boolean | 判断集合是否为空 |
| contains | Object o | boolean | 判断 o 对象是否被该集合包含 |
| toArray | 无 | Object[] | 将集合转换为数组 |
| toArray | T[] a | T[] | 将集合转换到传入的数组中 |
| add | E e | boolean | 此类中的add方法，子类必须重写自己的方法，此类不支持单个添加元素 |
| remove | Object o | boolean | 删除 o 元素 |
| containsAll | Collection<?> c | boolean | 判断 c 集合中的元素是否都被该集合包含 |
| addAll | Collection<? extends E> c | boolean | 新增所有元素 |
| removeAll | Collection<?> c | boolean | 删除传入集合的每一个元素 |
| retainAll | Collection<?> c | boolean | 删除除传入集合元素以外的元素 |
| clear | 无 | void | 清空集合 |
public abstract class MyAbstractCollection<E> implements Collection<E>{
//指定集合的最大长度为 Integer.MAX_VALUE - 8
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* 无参构造器
*/
public MyAbstractCollection() {}
/**
* 上层的size方法，在这里没有实现。
*/
@Override
public abstract int size();
/**
* 上层的获取迭代器的方法，在这里没有实现
*/
@Override
public abstract Iterator<E> iterator();
/**
* 判断集合是否为空
*/
@Override
public boolean isEmpty() {
return size() == 0;
}
/**
* 判断 o 对象是否被该集合包含
*/
@Override
public boolean contains(Object o) {
Iterator<E> it = iterator(); //获取迭代器
if (o == null) { //如果 o == null 判断集合中是否有 null 元素
while (it.hasNext()) {
if (it.next() == null) {
return true;
}
}
} else {
while (it.hasNext()) {
if (it.next().equals(o)) {
return true;
}
}
}
return false;
}
/**
* 将集合转换为数组
*/
@Override
public Object[] toArray() {
Object [] r = new Object[size()];
Iterator<E> it = iterator();
for (int i = 0; i < r.length; i++) {
//如果发现迭代器中的值小于 r的长度 则进行缩容
if (!it.hasNext()) {
return Arrays.copyOf(r, i);
}
r[i] = it.next();
}
//如果发现迭代器中的值大于 r的长度 则进行扩容
return it.hasNext() ? finishToArray(r, it) : r;
}
/**
* 数组扩容
* @param r
* @param it
* @return
*/
private static <T> T[] finishToArray(T[] r, Iterator<?> it) {
int i = r.length;
while(it.hasNext()) {
int newLeng = r.length;
//当新长度与原长度相同时进行扩容
if (i == newLeng) {
//扩容原长度的一半+1
int cap = newLeng + (newLeng >> 1) + 1;
//此处要判断cap的值是否大于Integer的最大值
if (cap - MAX_ARRAY_SIZE > 0) {
cap = hugeCapacity(cap + 1);
}
r = Arrays.copyOf(r, cap);
}
r[i ++] = (T) it.next();
}
//最后判断r的实际长度与 i 是否相等， 如果不等就将后面多余的位置删除
return (r.length == i) ? r : Arrays.copyOf(r, i);
}
/**
* 如果数组长度超出最大长度的处理
* @param minCapacity
* @return
*/
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) {
throw new OutOfMemoryError("数组长度过长");
}
return minCapacity > MAX_ARRAY_SIZE ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
/**
* 将集合转换到传入的数组中
*/
@Override
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
int size = size();
//如果 a的长度大于或者等于 集合的长度则 r就等于a数组，否则就新建一个数组
T[] r = a.length >= size() ? a : (T[]) Array.newInstance(
a.getClass().getComponentType(), size);
Iterator<E> it = iterator();
for (int i = 0; i < r.length; i++) {
if (!it.hasNext()) {
if (a == r) {//如果是r与传入的数组是同一个数组 则将后面的位置 置为 null
r[i] = null;
} else if (a.length < i) { //如果传入的数组长度小于r的长度 则缩容到i的长度
return Arrays.copyOf(r, i);
} else {//如果传入的数组长度大于或等于r的长度 则将后面的位置都置为null
System.arraycopy(r, 0, a, 0, i);
if (a.length > i) {
a[i] = null;
}
}
return a;
}
r[i] = (T) it.next();
}
return it.hasNext() ? finishToArray(r, it) : r;
}
/**
* 此类中的add方法，子类必须重写自己的方法，此类不支持单个添加元素
*/
@Override
public boolean add(E e) {
throw new UnsupportedOperationException();
}
/**
* 删除 o 元素
*/
@Override
public boolean remove(Object o) {
Iterator<E> it = iterator();
if (o == null) {
while (it.hasNext()) { //如果 o 为 null 则将第一个 null元素删除
if (it.next() == null) {
it.remove();
return false;
}
}
} else {
while (it.hasNext()) { //如果 找到第一个 与o元素相同的值 删除
if (o.equals(it.next())) {
it.remove();
return false;
}
}
}
return false;
}
/**
* 判断 c 集合中的元素是否都被该集合包含
*/
@Override
public boolean containsAll(Collection<?> c) {
//判断 c 中每一个元素是否存在
for (Object o : c) {
if (!contains(o)) {
return false;
}
}
return true;
}
/**
* 新增所有元素
*/
@Override
public boolean addAll(Collection<? extends E> c) {
boolean token = false;
for (E o : c) {
if (add(o)) {
token = true;
}
}
return token;
}
/**
* 删除传入集合的每一个元素
*/
@Override
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
boolean token = false;
Iterator<E> it = iterator();
//迭代集合本身，判断每一个元素是否存在于集合 c 中，如果存在则删除
while (it.hasNext()) {
if (c.contains(it.next())) {
it.remove();
token = true;
}
}
return token;
}
/**
* 删除除传入集合元素以外的元素
*/
@Override
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
boolean token = false;
Iterator<E> it = iterator();
//迭代集合本身，判断每一个元素是否存在于集合 c 中，如果不存在则删除
while (it.hasNext()) {
if (!c.contains(it.next())) {
it.remove();
token = true;
}
}
return token;
}
/**
* 清空集合
*/
@Override
public void clear() {
Iterator<E> it = iterator();
//迭代集合删除每一个元素
while (it.hasNext()) {
it.next();
it.remove();
}
}
}
⑤. AbstractList 抽象类
作用：此类继承 AbstractCollection 抽象类，继承 List 接口 ，为 ArrayList 的父类，提供了大部分集合操作的方法。此类中还存在几个内部类 分别是 ListItr，Itr，除了这两个内部类之外，SubList和RandomAccessSubList 这两个类也在 AbstractCollection 中。 ListItr 类 为list定义独有的迭代器，而 Itr 则为 ListItr 的父类。在ListItr 类中主要的一些方法都是去判断指针的位置，去描述指针是如何去移动，如何去删除元素，删除元素后对集合的改变，以及多个迭代器之间的互相的影响。SubList 类为集合提供了截取集合中某一段的方法，但是这个方法存在一些问题，他内部的方法是直接在传入集合上直接进行操作的，也就是说不仅仅会改变截取的部分集合，还会改变传入的集合，所以要谨慎使用。在下面方法中，内部类的方法就不提供了，但是会在后面的代码展示中简单解析一下代码的含义，以及操作的意义。
方法：
| 方法名 | 参数 | 返回值 | 描述 |
| add | E e | boolean | 重新父类的add方法，返回boolean值 |
| add | int index, E element | void |
实现 List 接口中的add方法，如果直接调用这个方法会抛出异常 |
| get | int index | E | List 接口中的get方法，在这里不做实现，由子类去实现 |
| set | int index, E element | E |
List 接口中的set方法，在这里只是抛出异常，子类如果直接调用，则会抛出异常， |
| remove | int index | E |
List 接口中的remove方法，在这里只是抛出异常，子类如果直接调用，则会抛出异常， |
| addAll | int index, Collection<? extends E> c | boolean | 重写 List 接口中的addAll方法 |
| indexOf | Object o | int | List 接口中的方法， 获取第一个与 o 对象，相同的元素的位置,如果没有则返回 -1 |
| lastIndexOf | Object o | int | List 接口中的方法， 获取最后一个与 o 对象，相同的元素的位置 |
| iterator | 无 | Iterator<E> | 获取迭代器 |
| listIterator | 无 | ListIterator<E> | 获取ListIterator迭代器 |
| listIterator | int index | ListIterator<E> | 获取迭代器从index开始 |
| removeRange | int fromIndex, int toIndex | void | 删除集合fromIndex到toIndex的元素 |
public abstract class MyAbstractList<E> extends MyAbstractCollection<E> implements List<E>{
/**
* 构造函数由子类调用
*/
protected MyAbstractList() {
}
/**
* 重新父类的add方法，返回boolean值
*/
@Override
public boolean add(E e) {
add(size(), e);
return true;
}
/**
* 实现 List 接口中的add方法，如果直接调用这个方法会抛出异常
* 所以在子类中一定要重写此方法
*/
@Override
public void add(int index, E element) {
throw new UnsupportedOperationException();
}
/**
* List 接口中的get方法，在这里不做实现，由子类去实现
*/
@Override
public abstract E get(int index);
/**
* List 接口中的set方法，在这里只是抛出异常，子类如果直接调用，则会抛出异常，
* 如果要使用则需要子类去重写这个set方法
*/
@Override
public E set(int index, E element) {
throw new UnsupportedOperationException();
}
/**
* List 接口中的remove方法，在这里只是抛出异常，子类如果直接调用，则会抛出异常，
* 如果要使用则需要子类去重写这个remove方法
*/
@Override
public E remove(int index) {
throw new UnsupportedOperationException();
}
/**
* 此参数为修改的次数,他主要是和迭代器一起使用，来确保线程安全，
* 保证线程之间的修改可见性。如果出现线程不安全的情况导致这个值与迭代器中的modCount值不同时则会抛出异常。
* 在一个迭代器初始的时候会赋予它调用这个迭代器的对象的mCount，如何在迭代器遍历的过程中，
* 一旦发现这个对象的mcount和迭代器中存储的mcount不一样那就抛异常
*/
protected transient int modCount = 0;
/**
* 重写 List 接口中的addAll方法
*/
@Override
public boolean addAll(int index, Collection<? extends E> c) {
//判断数组是否越界，如果越界抛出下标越界异常
rangeCheckForAdd(index);
boolean token = false;
for (E e : c) {
add(index++, e);
token = true;
}
return token;
}
/**
* 判断传入的index是否在小于0 或者大于集合长度
* @param index
*/
private void rangeCheckForAdd(int index) {
if (index < 0 || index > size())
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* 获取下标的位置，和实际集合长度
* @param index
* @return
*/
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size();
}
/**
* List 接口中的方法， 获取第一个与 o 对象，相同的元素的位置,如果没有则返回 -1
*/
@Override
public int indexOf(Object o) {
ListIterator<E> it = listIterator();
if (o == null) {
while(it.hasNext()) {
if (it.next() == null) {
//获取目前迭代器的位置
return it.previousIndex();
}
}
} else {
while(it.hasNext()) {
if (it.next().equals(o)) {
//获取目前迭代器上一个元素的位置
return it.previousIndex();
}
}
}
return -1;
}
/**
* List 接口中的方法， 获取最后一个与 o 对象，相同的元素的位置
*/
@Override
public int lastIndexOf(Object o) {
ListIterator<E> it = listIterator(size());
if (o == null) {
//获取迭代器是否存在的上一个元素，如果存在返回true
while (it.hasPrevious()) {
//获取迭代器上一个元素，反向迭代
if (it.previous() == null) {
//返回迭代器下一个元素的位置
return it.nextIndex();
}
}
} else {
while (it.hasPrevious()) {
//获取迭代器上一个元素，反向迭代
if (o.equals(it.previous())) {
//返回迭代器下一个元素的位置
return it.nextIndex();
}
}
}
return -1;
}
/**
* 获取迭代器
*/
@Override
public Iterator<E> iterator() {
return new Itr();
}
/**
* 获取ListIterator迭代器
*/
@Override
public ListIterator<E> listIterator() {
return listIterator(0);
}
/**
* 获取迭代器从index开始
*/
@Override
public ListIterator<E> listIterator(int index) {
rangeCheckForAdd(index);
return new ListItr(index);
}
/**
* 删除集合fromIndex到toIndex的元素
* @param fromIndex
* @param toIndex
*/
protected void removeRange(int fromIndex, int toIndex) {
ListIterator<E> it = listIterator(fromIndex);
for (int i = 0; i < toIndex - fromIndex; i++) {
it.next();
it.remove();
}
}
private class Itr implements Iterator<E> {
/**
* 调用迭代器 next 方法返回的索引
*/
int cursor = 0;
/**
* 上一次调用next 方法返回的索引
*/
int lastRet = -1;
/**
* 此参数为迭代器中的结构修改的次数，初始化时会将集合中的 modCount 赋值给迭代器
*/
int expectedModCount = modCount;
/**
* 判断是否存在下一个元素
*/
@Override
public boolean hasNext() {
return cursor != size();
}
@Override
public E next() {
//确保其他线程没有操作此集合
checkForComodification();
try {
//获取下一次next的元素的下标
int i = cursor;
//获取该下标的元素
E e = get(i);
//将此下标赋值给lastRet
lastRet = cursor;
//获取下一次next的元素下标
cursor ++;
return e;
} catch (Exception e) {
checkForComodification();
throw new NoSuchElementException();
}
}
/**
* 此处还重写了Iterator接口的remove方法
*/
@Override
public void remove() {
//如果lastRet的值小于0则说明迭代器指针还处于集合最前面，则没有删除的元素，所以抛出异常
if(lastRet < 0) {
throw new IllegalStateException();
}
//确保其他线程没有操作此集合
checkForComodification();
try {
//删除上一个元素
MyAbstractList.this.remove(lastRet);
if (lastRet < cursor) {
cursor --;
}
//删除只会删除next跳过的那个元素，删除一次之后将上一个下标置为-1，保证不能多次删除
lastRet = -1;
expectedModCount = modCount;
} catch (Exception e) {
throw new ConcurrentModificationException();
}
}
/**
* 使用此方法去保证线程之间的操作可见性，如果迭代器的操作次数与集合的操作次数不一致，则会抛出异常
*/
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
private class ListItr extends Itr implements ListIterator<E> {
ListItr(int index) {
cursor = index;
}
/**
* 判断上一个元素是否存在
*/
@Override
public boolean hasPrevious() {
//如果cursor为0则表示指针在集合头部，则上一个元素不存在
return cursor != 0;
}
/**
* 获取上一个元素
*/
@Override
public E previous() {
//判断是否被其他线程修改集合结构
checkForComodification();
try {
//获取上一个元素的下标
int i = cursor - 1;
//获取上一个元素
E e = get(i);
cursor = i;
lastRet = i;
return e;
} catch (Exception e) {
checkForComodification();
throw new NoSuchElementException();
}
}
/**
* 获取下一个元素的下标
*/
@Override
public int nextIndex() {
return cursor;
}
/**
* 获取上一个元素的下标
*/
@Override
public int previousIndex() {
return cursor - 1;
}
/**
* 修改元素
*/
@Override
public void set(E e) {
//修改元素修改的为上一次跳过的元素，如果上一次的元素是-1则说明还在集合头部，
//无元素可以修改，所以抛出异常
if (lastRet < 0) {
throw new IllegalStateException();
}
checkForComodification();
try {
//使用MyAbstractList类的set方法
MyAbstractList.this.set(lastRet, e);
//将修改的次数赋值给迭代器
expectedModCount = modCount;
} catch (Exception e2) {
throw new ConcurrentModificationException();
}
}
/**
* 新增元素
*/
@Override
public void add(E e) {
checkForComodification();
try {
//获取集合下一个元素的位置
int i = cursor;
//将元素新增到下一个位置
MyAbstractList.this.add(i, e);
lastRet = -1;
cursor++;
expectedModCount = modCount;
} catch (Exception e2) {
throw new ConcurrentModificationException();
}
}
}
}
class SubList<E> extends MyAbstractList<E> {
//原始的集合
private final MyAbstractList<E> l;
//开始截取集合的起始位置
private final int offset;
//截取集合的长度
private int size;
SubList(MyAbstractList<E> list, int fromIndex, int toIndex){
//如果起始位置小于0 则抛出异常
if (fromIndex < 0) {
throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
}
//如果结束位置大于数组长度 则抛出异常
if (toIndex > list.size()) {
throw new IndexOutOfBoundsException("toIndex = " + toIndex);
}
//如果起始位置大于结束位置 则抛出异常
if (fromIndex > toIndex) {
throw new IllegalArgumentException("fromIndex(" + fromIndex +
") > toIndex(" + toIndex + ")");
}
l = list;
offset = fromIndex;
size = toIndex - fromIndex;
this.modCount = l.modCount;
}
/**
* 获取index的元素
*/
@Override
public E get(int index) {
//判断集合下标是否不在集合范围内
rangeCheck(index);
checkForComodification();
//这里为什么要加offset呢，因为此处的l为原始的list
//而offset 为截取后的开始位置，然后加上现在要获取的元素的下标位置，
//才是现在要获取的元素
return l.get(index + offset);
}
/**
* 修改index位置的元素
*/
@Override
public E set(int index, E element) {
rangeCheck(index);
checkForComodification();
return l.set(index+offset, element);
}
/**
* 判断集合结构是否被其他线程改变
*/
private void checkForComodification() {
if (this.modCount != l.modCount)
throw new ConcurrentModificationException();
}
/**
* 判断集合下标是否不在集合范围内
* @param index
*/
private void rangeCheck(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* 输出集合下标和长度
* @param index
* @return
*/
private String outOfBoundsMsg(int index) {
return "Index: " + index + ", Size: " + size;
}
/**
* 获取截取后集合的长度
*/
@Override
public int size() {
checkForComodification();
return size;
}
/**
* 在指定位置添加元素
*/
@Override
public void add(int index, E element) {
rangeCheck(index);
checkForComodification();
l.add(index + offset, element);
this.modCount = l.modCount;
size++;
}
/**
* 删除指定位置元素
*/
@Override
public E remove(int index) {
rangeCheck(index);
checkForComodification();
E e = l.remove(index + offset);
this.modCount = l.modCount;
size--;
return e;
}
/**
* 删除指定区域的元素
*/
@Override
protected void removeRange(int fromIndex, int toIndex) {
checkForComodification();
l.removeRange(fromIndex + offset, toIndex + offset);
this.modCount = l.modCount;
size -= (toIndex - fromIndex);
}
/**
* 添加c到集合中，从size开始
*/
@Override
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
/**
* 添加c到集合中，从index开始
*/
@Override
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheck(index);
int cSize = c.size();
if (c.size() == 0) {
return false;
}
checkForComodification();
l.addAll(index + offset, c);
size += cSize;
return true;
}
/**
* 获取迭代器
*/
public Iterator<E> iterator() {
return listIterator();
}
/**
* 获取ListIterator
*/
public ListIterator<E> listIterator(final int index) {
checkForComodification();
rangeCheckForAdd(index);
return new ListIterator<E>() {
private final ListIterator<E> i = l.listIterator(index+offset);
public boolean hasNext() {
return nextIndex() < size;
}
public E next() {
if (hasNext())
return i.next();
else
throw new NoSuchElementException();
}
public boolean hasPrevious() {
return previousIndex() >= 0;
}
public E previous() {
if (hasPrevious())
return i.previous();
else
throw new NoSuchElementException();
}
public int nextIndex() {
return i.nextIndex() - offset;
}
public int previousIndex() {
return i.previousIndex() - offset;
}
public void remove() {
i.remove();
SubList.this.modCount = l.modCount;
size--;
}
public void set(E e) {
i.set(e);
}
public void add(E e) {
i.add(e);
SubList.this.modCount = l.modCount;
size++;
}
};
}
private void rangeCheckForAdd(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* 截取集合
*/
@Override
public List<E> subList(int fromIndex, int toIndex) {
return new SubList<>(this, fromIndex, toIndex);
}
}
class RandomAccessSubList<E> extends SubList<E> implements RandomAccess {
RandomAccessSubList(MyAbstractList<E> list, int fromIndex, int toIndex) {
super(list, fromIndex, toIndex);
}
public List<E> subList(int fromIndex, int toIndex) {
return new RandomAccessSubList<>(this, fromIndex, toIndex);
}
}
⑥. ArrayList
作用：ArrayList，是我们在开发过程中最常使用到的线性表的结构，它的内部可以存放重复的元素，并且可以存放null元素，属于线程不安全的集合类，查询效率高。
方法：在java8中在arrayList中加入了一些方法，还加入了获取流的类，在这里我只列出A让rayList中的方法，其他一些内部类就不一一列出，但是在下面源码解读中，我会将每个方法自己的注释以注解的方式进行注释。
| 方法名 | 入参 | 出参 | 描述 |
| trimToSize | 无 | void | 去除集合中预留元素的位置 |
| ensureCapacity | int minCapacity | void | 数组扩容 |
| size | 无 | int | 获取集合长度 |
| isEmpty | 无 | boolean | 判断集合是否为空 |
| contains | Object o | boolean | 判断集合是否包含 o |
| indexOf | Object o | int | 获取o第一次出现的下标 |
| lastIndexOf | Object o | int | 获取o最后一次出现在集合的位置 |
| clone | 无 | Object | 克隆集合 |
| toArray | 无 | Object[] | 将集合转数组 |
| toArray | T[] a | T[] | 将集合转为传入的数组 |
| elementData | int index | E | 获取第 index个元素 |
| get | int index | E | 获取第index个元素 |
| rangeCheck | int index | void | 判断传入的下标是否比数组长度大 |
| outOfBoundsMsg | int index | String | 获取传入的index的长度和数组长度 |
| set | int index, E element | E | 修改index元素，将新的element放入集合index的位置，并返回oldelement |
| add | E e | boolean | 新增元素 |
| add | int index, E element | void | 在指定位置插入元素 |
| rangeCheckForAdd | int index | void | 判断index是否在集合长度范围内 |
| remove | int index | E | 删除index的元素 ，并返回 |
| remove | Object o | boolean | 删除第一个元素 o |
| fastRemove | int index | void | 删除 index 位置的元素 |
| clear | 无 | void | 清空集合 |
| addAll | Collection<? extends E> c | boolean | 将c集合添加到本集合 |
| addAll | int index, Collection<? extends E> c | boolean | 在index处，添加集合c |
| removeRange | int fromIndex, int toIndex | void | 删除fromIndex到toIndex的元素 |
| removeAll | Collection<?> c | boolean | 删除集合中包含c集合中的元素 |
| writeObject | java.io.ObjectOutputStream s | void | 用于MyArrayList序列化使用 |
| readObject | java.io.ObjectInputStream s | void | 反序列化方法 |
| listIterator | int index | ListIterator<E> | 获取从 index 开始的List迭代器 |
| listIterator | 无 | ListIterator<E> | 获取从 0 开始的List迭代器 |
| iterator | 无 | Iterator<E> | 获取迭代器 |
| subList | int fromIndex, int toIndex | List<E> | 截取集合 从fromIndex 到 toIndex |
| forEach | Consumer<? super E> action | void | 遍历集合，其中每个元素执行action中的方法 |
| spliterator | 无 | Spliterator<E> | 获取Spliterator迭代器 java8提供 |
| removeIf | Predicate<? super E> filter | boolean | 如果集合中元素在一定条件内就删除，条件由开发者传入 |
| replaceAll | UnaryOperator<E> operator | void | 按照一定的规则对集合进行操作，规则由开发者传入 |
| sort | Comparator<? super E> c | void | java8中新加入的方法，按照一定的规则进行排序 |
public class MyArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable { private static final long serialVersionUID = 2572016039206533046L; /**
* 创建集合时的初始 长度
*/
private static final int DEFAULT_CAPACITY = 10; /**
* 当创建集合时传入的长度为0时默认使用下面的数组
*/
private static final Object[] EMPTY_ELEMENTDATA = {}; /**
* 当创建集合时不传入参数时默认使用下面的数组
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; /**
* 集合最大长度
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; /**
* 这个为集合默认使用的数组，使用 transient 修饰，将并不会被序列化到指定位置
*/
transient Object[] elementData; /**
* elementData 数组长度
*/
private int size; /**
* 记录数组结构变化次数，保证多线程对数组结构改变时线程安全
*/
protected transient int modCount = 0; /**
* 无参构造器
*/
public MyArrayList() {
//直接使用默认的数组
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
} /**
* 第一个有参构造器，传入集合长度
* @param initialCapacity 创建集合的长度
*/
public MyArrayList(int initialCapacity) {
if (initialCapacity > 0) {
//如果长度大于 0 则创建对应长度的数组，并且赋值给elementData
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
//如果长度等于 0 则直接使用默认数组 EMPTY_ELEMENTDATA
this.elementData = EMPTY_ELEMENTDATA;
} else {
//如果小于 0 则抛出异常
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
} } /**
* 第二个有参构造器，传入一个集合
* @param c
*/
public MyArrayList(Collection<? extends E> c) {
//将 传入的集合转为数组
elementData = c.toArray();
//获取集合长度
size = elementData.length;
if (size != 0) {
//如果传入的集合转数组之后不是Object的数组，则copy 到Object 数组中
if (elementData.getClass() != Object[].class) {
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
} else {
//如果传入的集合长度为 0 则使用默认的数组 EMPTY_ELEMENTDATA
elementData = EMPTY_ELEMENTDATA;
}
} /**
* 去除集合中预留元素的位置
*/
public void trimToSize() {
modCount ++;
if (size < elementData.length) {
//如果size与数组长度不相等，则判断size是否为0 如果为0 则使用默认数组
//如果size不为0则将elementDta中size长度之后的预留元素的位置删除
elementData = (size == 0) ?
EMPTY_ELEMENTDATA :
Arrays.copyOf(elementData, size);
}
} /**
* 数组扩容
* @param minCapacity 扩容的长度
*/
public void ensureCapacity(int minCapacity) {
//判断elementData 是否为默认的数组，如果是最小长度为 0 否则 最小长度为默认的10
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
? 0 : DEFAULT_CAPACITY;
//判断扩容的长度是否比最小长度大，如果大继续扩容，否则不扩容
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
} private void ensureCapacityInternal(int minCapacity) {
/**
* 判断elementData 是否为默认数组，如果是则 minCapacity 与
* 默认长度做比较，取较大的那个数扩容
*/
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
//否则按照传入值进行扩容
ensureExplicitCapacity(minCapacity);
} private void ensureExplicitCapacity(int minCapacity) {
modCount++; // 传入值与现在数组长度做比较，如果传入值大于目前数组长度继续扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
} private void grow(int minCapacity) {
// 获取数组原长度
int oldCapacity = elementData.length;
// 数组新长度为原长度+原长度的一半
int newCapacity = oldCapacity + (oldCapacity >> 1);
//如果新长度小于传入的minCapacity 则新长度 = minCapacity
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//如果新长度大于集合最大长度则执行hugeCapacity 获取扩容的长度
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 进行扩容
elementData = Arrays.copyOf(elementData, newCapacity);
} private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
//如果新长度大于集合最大长度则返回 int的最大值，否则返回集合最大值
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
} /**
* 获取集合长度
*/
@Override
public int size() {
return size;
} /**
* 判断集合是否为空
*/
@Override
public boolean isEmpty() {
return size == 0;
} /**
* 判断集合是否包含 o
*/
@Override
public boolean contains(Object o) {
//如果集合中可以获取到o的下标，则说明o存在于集合中
return indexOf(o) >= 0;
} /**
* 获取o第一次出现的下标
*/
@Override
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
} /**
* 获取o最后一次出现在集合的位置
*/
@Override
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
} /**
* 克隆集合
*/
@Override
public Object clone() {
try {
MyArrayList<?> v = (MyArrayList<?>) super.clone();
//copy原集合，并将结构改变次数置为0
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
throw new InternalError(e);
}
} /**
* 将集合转数组
*/
@Override
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
} /**
* 将集合转为传入的数组
*/
@Override
public <T> T[] toArray(T[] a) {
if (a.length < size)
// 如果传入的数组长度小于集合的长度，则需要先扩容再copy
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
} /**
* 获取第 index个元素
* @param index
* @return
*/
E elementData(int index) {
return (E) elementData[index];
} /**
* 获取第index个元素
*/
@Override
public E get(int index) {
rangeCheck(index);
return elementData(index);
} /**
* 判断传入的下标是否比数组长度大
* @param index
*/
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
} /**
* 获取传入的index的长度和数组长度
* @param index
* @return
*/
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size;
} /**
* 修改index元素，将新的element放入集合index的位置，并返回oldelement
*/
@Override
public E set(int index, E element) {
rangeCheck(index); E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
} /**
* 新增元素
*/
@Override
public boolean add(E e) {
//数组扩容，在内部会判断数组是否需要扩容，如果长度不足则扩容，否则不扩容
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
} /**
* 在指定位置插入元素
*/
@Override
public void add(int index, E element) {
//判断index是否在集合长度范围内
rangeCheckForAdd(index);
//判断是否需要扩容
ensureCapacityInternal(size + 1);
//将index以及后面的元素向后移动一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//简化element 放在 index的位置上
elementData[index] = element;
size++;
} /**
* 判断index是否在集合长度范围内
* @param index
*/
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
} /**
* 删除index的元素 ，并返回
*/
@Override
public E remove(int index) {
rangeCheck(index); modCount++;
E oldValue = elementData(index); //index 位置后面元素的个数
int numMoved = size - index - 1;
//如果index 后面存在元素，则向前移动一位
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//将最后一位置为null
elementData[--size] = null; return oldValue;
} /**
* 删除第一个元素 o
*/
@Override
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
//删除第一个 o元素
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
} /**
* 删除 index 位置的元素
* @param index
*/
private void fastRemove(int index) {
modCount++;
//index 位置后面元素的个数
int numMoved = size - index - 1;
//如果index 后面存在元素，则向前移动一位
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//将最后一位置为null
elementData[--size] = null;
} /**
* 清空集合
*/
@Override
public void clear() {
modCount++; // 将每一个元素置null
for (int i = 0; i < size; i++)
elementData[i] = null; size = 0;
} /**
* 将c集合添加到本集合
*/
@Override
public boolean addAll(Collection<? extends E> c) {
//转数组
Object[] a = c.toArray();
int numNew = a.length;
//扩容
ensureCapacityInternal(size + numNew);
//copy数组，将a数组从0开始copy到 elementData，从size开始，copy numNew个元素
System.arraycopy(a, 0, elementData, size, numNew);
//修改长度
size += numNew;
return numNew != 0;
} /**
* 在index处，添加集合c
*/
@Override
public boolean addAll(int index, Collection<? extends E> c) {
//判断index是否超出集合范围
rangeCheckForAdd(index); Object[] a = c.toArray();
int numNew = a.length;
//数组扩容
ensureCapacityInternal(size + numNew); int numMoved = size - index;
if (numMoved > 0)
//将index后面的元素向后移动 c 集合中元素个数个长度
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
//将a集合中的元素从0开始复制到elementData的index位置
System.arraycopy(a, 0, elementData, index, numNew);
//修改长度
size += numNew;
return numNew != 0;
} /**
* 删除fromIndex到toIndex的元素
*/
@Override
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
int numMoved = size - toIndex;
//将elementData 从 toIndex开始的元素 移动到fromIndex的位置，移动 numMoved个元素
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved); int newSize = size - (toIndex-fromIndex);
//将后面移动的元素的位置置为null
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
size = newSize;
} /**
* 删除集合中包含c集合中的元素
*/
@Override
public boolean removeAll(Collection<?> c) {
//判断c是否为null
Objects.requireNonNull(c);
return batchRemove(c, false);
} private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
//w为下一个不重复元素的下标，r为目前遍历的元素下标，将不重复的元素放到w位置
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
//如果上面的循环没有结束，则将没有遍历完的元素向前移动
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
//将w后面的元素全部置为null
if (w != size) {
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
//长度修改为w
size = w;
modified = true;
}
}
return modified;
} /**
* 用于MyArrayList序列化使用
* @param s
* @throws java.io.IOException
*/
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// 首先先将非 transient 的进行序列化
int expectedModCount = modCount;
s.defaultWriteObject(); // 再将集合的长度序列化
s.writeInt(size); // 最后将，集合中非 null的进行序列化。我们知道集合初始化有10个长度，也许只用用几个，
//那么这时序列化全部的话就会把后面没有使用的地址的null也序列化进去，这里序列化时，
//调用此方法就会只序列化有值的区域，从而增加序列化效率，剪小序列化后的文件
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
//如何在序列化过程中集合结构被其他线程修改，则序列化失败
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
} /**
* 反序列化方法
* @param s
* @throws java.io.IOException
* @throws ClassNotFoundException
*/
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA; // 首先将非transient 修饰的进行反序列化
s.defaultReadObject();
s.readInt(); if (size > 0) {
// 数组扩容
ensureCapacityInternal(size); Object[] a = elementData;
// 解析size个 元素进行反序列化
for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
}
} /**
* 获取从 index 开始的List迭代器
*/
public ListIterator<E> listIterator(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: "+index);
return new ListItr(index);
} /**
* 获取从 0 开始的List迭代器
*/
public ListIterator<E> listIterator() {
return new ListItr(0);
} /**
* 获取迭代器
*/
public Iterator<E> iterator() {
return new Itr();
} private class Itr implements Iterator<E> { int cursor; // 迭代器指针指向的下一个元素的下标
int lastRet = -1; // 迭代器指针跳过的上一个元素的下标，-1表示没有
int expectedModCount = modCount; @Override
public boolean hasNext() {
return cursor != size;
} @Override
public E next() {
//判断集合结构修改次数是否与迭代器修改次数相同
checkForComodification();
int i = cursor;
if (i > size) {
throw new NoSuchElementException();
}
Object [] elementData = MyArrayList.this.elementData;
if (i > elementData.length) {
throw new ConcurrentModificationException();
}
return null;
} /**
* 删除指针跳过的元素
*/
public void remove() {
if (lastRet < 0) {
throw new IllegalStateException();
}
checkForComodification();
try {
//使用arrayList的删除方法
MyArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException e) {
throw new ConcurrentModificationException();
}
} /**
* java8新加入的方法，迭代集合，并自定义方法执行,但是这里需要注意的是，迭代的集合是从指针的下一个元素开始
* 并不一定是从集合的开始执行，所以请谨慎使用
*/
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
//判断传入的方法是否为null
Objects.requireNonNull(consumer);
final int size = MyArrayList.this.size;
int i = cursor;
//指针在最后的位置
if (i > size) {
return;
}
final Object [] elementData = MyArrayList.this.elementData;
if (i >= elementData.length) {
throw new ConcurrentModificationException();
}
while(i != size && modCount == expectedModCount) {
consumer.accept((E)elementData[i++]);
}
cursor = i;
lastRet = i - 1;
checkForComodification();
} /**
* 判断集合结构修改次数是否与迭代器修改次数相同
*/
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
} } /**
* list 的迭代器
*
*/
private class ListItr extends Itr implements ListIterator<E> { ListItr(int index) {
super();
cursor = index;
} /**
* 是否存在上一个元素
*/
public boolean hasPrevious() {
return cursor != 0;
} /**
* 获取下一个元素的下标
*/
public int nextIndex() {
return cursor;
} /**
* 获取上一个元素的下标
*/
public int previousIndex() {
return cursor - 1;
} /**
* 获取上一个元素
*/
@SuppressWarnings("unchecked")
public E previous() {
checkForComodification();
int i = cursor - 1;
//如果上一个元素下标小于0，说明不存在上一个元素
if (i < 0)
throw new NoSuchElementException();
Object[] elementData = MyArrayList.this.elementData;
//如果上一个元素下标大于数组的长度，则抛出异常
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;
return (E) elementData[lastRet = i];
} /**
* 修改指针刚跳过的元素
*/
public void set(E e) {
//如果lastRet小于0 则说明没有跳过任何一个元素
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification(); try {
MyArrayList.this.set(lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
} /**
* 在指针后加入元素
*/
public void add(E e) {
checkForComodification();
try {
int i = cursor;
MyArrayList.this.add(i, e);
cursor = i + 1;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
} /**
* 截取集合 从fromIndex 到 toIndex
*/
public List<E> subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size);
return new SubList(this, 0, fromIndex, toIndex);
} /**
* 判断截取集合的位置是否正确
* @param fromIndex
* @param toIndex
* @param size
*/
static void subListRangeCheck(int fromIndex, int toIndex, int size) {
if (fromIndex < 0)
throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
if (toIndex > size)
throw new IndexOutOfBoundsException("toIndex = " + toIndex);
if (fromIndex > toIndex)
throw new IllegalArgumentException("fromIndex(" + fromIndex +
") > toIndex(" + toIndex + ")");
} private class SubList extends AbstractList<E> implements RandomAccess {
private final AbstractList<E> parent; //原集合
private final int parentOffset; //开始位置
private final int offset; //结束位置
int size; //需要截取的元素的个数 SubList(AbstractList<E> parent,
int offset, int fromIndex, int toIndex) {
this.parent = parent;
this.parentOffset = fromIndex;
this.offset = offset + fromIndex;
this.size = toIndex - fromIndex;
this.modCount = MyArrayList.this.modCount;
} /**
* 修改index元素
*/
public E set(int index, E e) {
//判断index是否不在集合范围内
rangeCheck(index);
checkForComodification();
//获取原来index位置的元素
E oldValue = MyArrayList.this.elementData(offset + index);
//使用e 替代原来位置的元素
MyArrayList.this.elementData[offset + index] = e;
return oldValue;
} /**
* index位置的元素
*/
public E get(int index) {
rangeCheck(index);
checkForComodification();
return MyArrayList.this.elementData(offset + index);
} /**
* 获取截取后元素的长度
*/
public int size() {
checkForComodification();
return this.size;
} /**
* 截取后集合中新增元素，因为是在截取前的集合中直接操作，所以谨慎使用
*/
public void add(int index, E e) {
rangeCheckForAdd(index);
checkForComodification();
parent.add(parentOffset + index, e);
this.modCount = parent.modCount;
this.size++;
} /**
* 删除元素
*/
public E remove(int index) {
rangeCheck(index);
checkForComodification();
E result = parent.remove(parentOffset + index);
this.modCount = parent.modCount;
this.size--;
return result;
} /**
* 删除从fromIndex开始到toIndex位置的元素
*/
protected void removeRange(int fromIndex, int toIndex) {
checkForComodification();
parent.removeRange(parentOffset + fromIndex,
parentOffset + toIndex);
this.modCount = parent.modCount;
this.size -= toIndex - fromIndex;
} /**
* 新增传入集合的所有元素
*/
public boolean addAll(Collection<? extends E> c) {
return addAll(this.size, c);
} /**
* 在index位置后加入集合c中所有元素
*/
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
int cSize = c.size();
if (cSize==0)
return false; checkForComodification();
parent.addAll(parentOffset + index, c);
this.modCount = parent.modCount;
this.size += cSize;
return true;
} /**
* 获取迭代器
*/
public Iterator<E> iterator() {
return listIterator();
} /**
* 获取ListIterator迭代器
*/
public ListIterator<E> listIterator(final int index) {
checkForComodification();
rangeCheckForAdd(index);
final int offset = this.offset; return new ListIterator<E>() {
int cursor = index;
int lastRet = -1;
int expectedModCount = MyArrayList.this.modCount; /**
* 判断是否存在下一个元素
*/
public boolean hasNext() {
return cursor != SubList.this.size;
} /**
* 获取下一个元素
*/
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= SubList.this.size)
throw new NoSuchElementException();
Object[] elementData = MyArrayList.this.elementData;
if (offset + i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[offset + (lastRet = i)];
} /**
* 判断是否存在上一个元素
*/
public boolean hasPrevious() {
return cursor != 0;
} /**
* 获取上一个元素
*/
@SuppressWarnings("unchecked")
public E previous() {
checkForComodification();
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
Object[] elementData = MyArrayList.this.elementData;
if (offset + i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;
return (E) elementData[offset + (lastRet = i)];
} /**
* 循环遍历指针后面的元素，并执行consumer的方法
*/
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
Objects.requireNonNull(consumer);
final int size = SubList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = MyArrayList.this.elementData;
if (offset + i >= elementData.length) {
throw new ConcurrentModificationException();
}
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[offset + (i++)]);
}
lastRet = cursor = i;
checkForComodification();
} /**
* 获取下一个元素
*/
public int nextIndex() {
return cursor;
} /**
* 获取上一个元素
*/
public int previousIndex() {
return cursor - 1;
} /**
* 删除元素
*/
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification(); try {
SubList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = MyArrayList.this.modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
} /**
* 修改元素
*/
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification(); try {
MyArrayList.this.set(offset + lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
} /**
* 新增元素
*/
public void add(E e) {
checkForComodification(); try {
int i = cursor;
SubList.this.add(i, e);
cursor = i + 1;
lastRet = -1;
expectedModCount = MyArrayList.this.modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
} final void checkForComodification() {
if (expectedModCount != MyArrayList.this.modCount)
throw new ConcurrentModificationException();
}
};
} /**
* 截取集合从fromIndex到toIndex
*/
public List<E> subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size);
return new SubList(this, offset, fromIndex, toIndex);
} private void rangeCheck(int index) {
if (index < 0 || index >= this.size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
} private void rangeCheckForAdd(int index) {
if (index < 0 || index > this.size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
} private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+this.size;
} private void checkForComodification() {
if (MyArrayList.this.modCount != this.modCount)
throw new ConcurrentModificationException();
} public Spliterator<E> spliterator() {
checkForComodification();
return new ArrayListSpliterator<E>(MyArrayList.this, offset,
offset + this.size, this.modCount);
}
} /**
* 遍历集合，其中每个元素执行action中的方法
*/
@Override
public void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
final int expectedModCount = modCount;
@SuppressWarnings("unchecked")
final E[] elementData = (E[]) this.elementData;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
action.accept(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
} /**
* 获取Spliterator迭代器 java8提供
*/
@Override
public Spliterator<E> spliterator() {
return new ArrayListSpliterator<>(this, 0, -1, 0);
} static final class ArrayListSpliterator<E> implements Spliterator<E> { private final MyArrayList<E> list; //集合
private int index; //起始位置
private int fence; //结束位置 -1表示最后
private int expectedModCount; //结构改变次数 ArrayListSpliterator(MyArrayList<E> list, int origin, int fence,
int expectedModCount) {
this.list = list;
this.index = origin;
this.fence = fence;
this.expectedModCount = expectedModCount;
} /**
* 获取结束位置
* @return
*/
private int getFence() {
int hi;
MyArrayList<E> lst;
//如果fence = -1则说明已经到达最后位置
if ((hi = fence) < 0) {
//如果集合为null则最后位置为0
if ((lst = list) == null)
hi = fence = 0;
else {
//否则返回集合长度
expectedModCount = lst.modCount;
hi = fence = lst.size;
}
}
return hi;
} /**
* 分割迭代器，每调用一次，将原来的迭代器等分为两份，并返回索引靠前的那一个子迭代器。
*/
public ArrayListSpliterator<E> trySplit() {
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
return (lo >= mid) ? null :
new ArrayListSpliterator<E>(list, lo, index = mid,
expectedModCount);
} /**
* 获取下一个元素并执行action方法
*/
public boolean tryAdvance(Consumer<? super E> action) {
if (action == null)
throw new NullPointerException();
int hi = getFence(), i = index;
//如果开始位置小于结束
if (i < hi) {
index = i + 1;
//则获取下一个元素
@SuppressWarnings("unchecked") E e = (E)list.elementData[i];
//执行action的方法
action.accept(e);
if (list.modCount != expectedModCount)
throw new ConcurrentModificationException();
return true;
}
return false;
} /**
* 循环执行action方法
*/
public void forEachRemaining(Consumer<? super E> action) {
int i, hi, mc;
MyArrayList<E> lst; Object[] a;
if (action == null)
throw new NullPointerException();
if ((lst = list) != null && (a = lst.elementData) != null) {
if ((hi = fence) < 0) {
mc = lst.modCount;
hi = lst.size;
}
else
mc = expectedModCount;
if ((i = index) >= 0 && (index = hi) <= a.length) {
for (; i < hi; ++i) {
@SuppressWarnings("unchecked") E e = (E) a[i];
action.accept(e);
}
if (lst.modCount == mc)
return;
}
}
throw new ConcurrentModificationException();
} public long estimateSize() {
return (long) (getFence() - index);
} public int characteristics() {
return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
}
} /**
* 如果集合中元素在一定条件内就删除，条件由开发者传入
*/
@Override
public boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
int removeCount = 0;
//创建一个size长度的BitSet
final BitSet removeSet = new BitSet(size);
final int expectedModCount = modCount;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
@SuppressWarnings("unchecked")
final E element = (E) elementData[i];
if (filter.test(element)) {
//将removeSet的 i 位置 设置为true
removeSet.set(i);
removeCount++;
}
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
//判读是否有元素需要被删除
final boolean anyToRemove = removeCount > 0;
if (anyToRemove) {
//获取删除元素后 数组的长度
final int newSize = size - removeCount;
for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
//获取removeSet中i后面第一个为false的元素下标，
i = removeSet.nextClearBit(i);
elementData[j] = elementData[i];
}
//将删除结束后，新数组长度后面的元素全部置为null、
for (int k=newSize; k < size; k++) {
elementData[k] = null;
}
this.size = newSize;
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
} return anyToRemove;
} /**
* 按照一定的规则对集合进行操作，规则由开发者传入
*/
@Override
@SuppressWarnings("unchecked")
public void replaceAll(UnaryOperator<E> operator) {
Objects.requireNonNull(operator);
final int expectedModCount = modCount;
final int size = this.size;
//循环遍历每一个元素，并执行规则
for (int i=0; modCount == expectedModCount && i < size; i++) {
elementData[i] = operator.apply((E) elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
} /**
* java8中新加入的方法，按照一定的规则进行排序
*/
@Override
@SuppressWarnings("unchecked")
public void sort(Comparator<? super E> c) {
final int expectedModCount = modCount;
//调用arrays的方法传入数组，从0开始size个元素，按照c的规则进行排序
Arrays.sort((E[]) elementData, 0, size, c);
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
} }
以上就是我在学习线性表时的一些感悟以及对ArrayList以及相关的一些接口，父类的源码的解读，其中代码中的注释均是我自己在读源码过程中的理解。如过有地方理解的和大家理解的不一样，还请提出来一起探讨。
-------------------- END ---------------------
最后附上作者的微信公众号地址和博客地址
公众号：wuyouxin_gzh
Herrt灬凌夜：https://www.cnblogs.com/wuyx/
版权说明：欢迎以任何方式进行转载，但请在转载后注明出处！
最新文章
- 常look的Git命令
- 将IList转换为List
- virtualbox无法安装VBoxLinuxAdditions.run
- SQLServer语句大使
- FTP文件夹打开错误，Windows无法访问此文件夹
- postfix部署多个Content Filter的方法
- ASP.NET 5简介
- IntelliJ IDEA 2017.3下载与安装
- antd Tree组件中，自定义右键菜单
- C#引用C++的DLL方案(C#调用非托管动态链接库)
- 【PS技巧】常用概念和功能操作
- swiper嵌套小demo(移动端触摸滑动插件)
- linux中时间命令详解
- Python：每日一题001
- linux第四次读书笔记
- pandas学习（创建数据，基本操作）
- 【docker】docker部署spring boot服务 选择配置文件启动
- Echarts 新认知 地图的label到底怎么居中？
- 2018/03/19 每日一个Linux命令 之 touch
- [模板] KMP字符串匹配标准代码
热门文章
- [译]Quartz.Net 框架 教程（中文版）2.2.x 之第三课 更多关于Jobs和JobDetails
- 【POJ】3233 Matrix Power Series
- Use JPath but not recursively loop a JObject to modify the values.
- JSON.parse()——json字符串转JS
- OGG生成数据定义文件的参数NOEXTATTR
- xv6/sh.c
- Mac Sublime Vim模式 方向键无法长按
- elk系列8之logstash+redis+es的架构来收集apache的日志【转】
- [转载]理解Tomcat的Classpath-常见问题以及如何解决
- java并发编程实战笔记---（第三章）对象的共享