首页 > 编程语言 > 详细

java容器体系（二）----List（ArrayList）

时间：2020-09-06 14:41:57      阅读：74      评论：0      收藏：0      [点我收藏+]

一、List的解析

　　List是 java 中的有序列表，按照元素加入的顺序有序存储，元素可以重复，它的实现类主要包括 ArrayList、Vector 、LinkedList 等。

　　List 相关类图如下所示：

　　技术分享图片

 

 

 

　　List提供的方法声明如下图所示：

技术分享图片

 

 

 

　　List 继承自Collection 类，拥有Collection 所有的方法，如 add(E e)、size()、isEmpty()、remove(Object o)、clear()、itrator() 等，同时也有 Collection 没有的方法声明，如 List 提供了可以按照元素的索引位置增删改的方法 add(int index)、remove(int index)、set(int index,E e), List 接口除了正常的itrator()迭代器的功能，还提供了一种特殊的迭代器 ListIterator，该迭代器继承自 Iterator，故提供了Iterator 的一切功能，允许元素的插入和更换，同时允许获取从指定位置开始的迭代器。

ListIterator<E> listIterator();
ListIterator<E> listIterator(int index); // 指定位置开始

二、ArrayList的解析

　　ArrayList 是 List 的实现子类之一，是最常用的List，它的底层是使用数组实现的，因此需要一段连续的内存空间，数组的大小可以调整。　

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

　　ArrayList 继承自抽象类 AbstractList ,实现了 List、RandomAccess、Cloneable、Serializable，表明它支持随机访问、克隆及序列化操作，之所以继承AbstractList是因为它当中有部分已有方法体的函数可以供子类直接使用，如果需要的话，子类还可以重写。

 1、成员变量常量

private static final int DEFAULT_CAPACITY = 10; // 默认的数组容量，即构造方法无参数时的数组容量
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData; // 没有使用private修饰方便嵌套类的访问
private int size; // elementData 数组中已存储的元素数量，<=elementData.length
protected transient int modCount = 0; // 用于记录发生结构性修改的次数，如add、remove方法，codCount会加1

2、构造函数

　　ArrayList有三个构造函数：

public ArrayList(int initialCapacity) { // 初始化数组容量
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; // {} 空数组
    }
public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class) // 存在不为Object[].class的情况，复制的Object数组赋值给elementData
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

　　Collection 中 toArray 的声明方式为 “Object[] toArray()”，但在参数如果传入  Arrays.asList("a","b","c")  的话，elementData.getClass() 将是String[].class，因为Arrays.asList内部toArray是将内部存储的数组指向传入的数组，存储类型是取决于传入类型，而不一定是Object[]；而如ArrayList存储的Object类型的数组，toArray是以 Arrays.copyOf(elementData, size) 的方式实现的，返回类型当然是Object[]。

2、add方法

 　　ArrayList 中提供了两个 add 方法，一个是在列表的尾部添加元素；一个是在列表指定的位置添加元素，并将原当前位置的元素及其后面的元素向后移动一位。

// 最列表的末尾添加元素
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // 确保容量足够，modCount+1
    elementData[size++] = e;
    return true;
}

// 将当前位置的元素及之后的向后移动，在指定的位置添加元素
public void add(int index, E element) {
    rangeCheckForAdd(index); // 检测新添加位置是否<0或者当前已存储元素数量，是的抛出越界异常

    ensureCapacityInternal(size + 1);  // 确保elementData中的容量大于等于为size + 1!!
    System.arraycopy(elementData, index, elementData, index + 1,
                         size - index); // 先向后移动元素，（将数组中从index位置开始的元素，复制到从index+1开始额位置上，复制数据的长度）
    elementData[index] = element;
    size++;
}

　　介绍一下用到的方法：

private void ensureCapacityInternal(int minCapacity) {
     if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // elementData == {} 时，取需要的最小容量和10的较大值，即最小容量的最小值是10
          minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
     }

     ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++; // 此时将modCount+1

    // 如果需要的最小容量大于当前容量则扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

// 根据最小容量扩容
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 新容量扩充为原来的1.5倍
    if (newCapacity - minCapacity < 0) // 新容量小于最小容量时（添加一般不会发生，除非原有容量太小）
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0) // 新容量>Integer.MAX_VALUE - 8时，根据最小容量扩容
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity); // 最终扩容
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; // 最小容量大于MAX_ARRAY_SIZE时，取Integer.MAX_VALUE，否则为MAX_ARRAY_SIZE
}

private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

 3、addAll方法

　　ArrayList提供了两个添加 Collection 所有元素的方法：一个是在尾部添加，另一个是从指定位置开始添加。

public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // 确保容量足够，modCount+1
    System.arraycopy(a, 0, elementData, size, numNew); // 将a数组中从0开始的元素复制到elementData尾部开始的地方
    size += numNew; // 实际使用量增加
    return numNew != 0;
}

public boolean addAll(int index, Collection<? extends E> c) {
    rangeCheckForAdd(index); // 检查是否越界

    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount

    int numMoved = size - index;
    if (numMoved > 0)
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved); // 将原数组index位置开始的元素复制到index+numNew开始的地方

    System.arraycopy(a, 0, elementData, index, numNew); //将a中元素复制到从index开始的地方
    size += numNew;
    return numNew != 0;
}

  4、get方法

　　get方法用于获取列表具体位置的元素

public E get(int index) {
      rangeCheck(index); // 检查是否越界，index<size;index>=size时，抛出IndexOutOfBoundsException，index<0时，ArrayIndexOutOfBoundsException

      return elementData(index);
}
private void rangeCheck(int index) {
      if (index >= size)
           throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
E elementData(int index) {
    return (E) elementData[index];
}

 

  4、set方法

public E set(int index, E element) {
        rangeCheck(index); // 检查是否越界,index<size

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
}

5、remove方法

　　ArrayList 本身提供了两个 remove 方法，一个是根据具体的位置删除；另一个是根据元素删除。

public E remove(int index) {
    rangeCheck(index); // 检查是否越界index，只判断index<size

    modCount++; // modCount+1
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                        numMoved); // index之后的元素前一位
    elementData[--size] = null; // size-1，之前已使用容量的最后一位清空以使GC生效

    return oldValue;
}

// ArrayList 允许重复的元素，本 remove 方法只会删除第一个相等的元素
public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) { // 为null时，直接判断是否等于null
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) { // 调用 equals 判断是否相等
                fastRemove(index);
                return true;
            }
    }
    return false;
}

// 基本上和 remove(int index) 实现一样，因为 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; // clear to let GC do its work
}

5、clear方法

　　clear() 方法用于清空元素。

public void clear() {
    modCount++;

    // clear to let GC do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null; // 清空每一个位置的元素，是GC生效

    size = 0; // size置为0
}

6、iterator方法

　　Collection 提供了 Iterator() 方法用于返回迭代器 Iterator 对象，在 ArrayList 中它的实现方式是返回了一个它的内部类 Itr 的实例，Itr 实现了 Iterator 接口。让我们先看一下 Itr 的内部实现。

private class Itr implements Iterator<E> {
    int cursor;       // 下一个的元素位置,初始为0
    int lastRet = -1; // 当前访问元素的位置
    int expectedModCount = modCount; // 初始化expectedModCount等于外部类的modCount

    public boolean hasNext() { // 表明当前位置的后一个位置是否存在元素，一般需要cursor<size，已访问最后一个元素时，cursor=size
        return cursor != size;
    }

    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification(); // 判断expectedModCount和modCount是否还是相等的
        int i = cursor;
        if (i >= size) // 当前位置是最后一个元素时，一般存在i=size的可能性，
        //抛出NoSuchElementException，不是IndexOutOfBoundsException
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length) // i>elementData实际容量时，抛出ConcurrentModificationException异常，不过单线程情况下应该不会发生，多线程可能会
            throw new ConcurrentModificationException();
        cursor = i + 1; // 记录下一元素的位置，cursor<=size
        return (E) elementData[lastRet = i]; // 返回元素，上一个访问元素的位置更新
    }

    public void remove() {
        if (lastRet < 0) // 没有使用next()就调用remove()时会抛出异常
            throw new IllegalStateException();
        checkForComodification();

        try {
            ArrayList.this.remove(lastRet); // 调用的是外部类的remove(int index)方法，外部类的modCount，size会更新！！！！
            cursor = lastRet; // 下一元素的位置改为当前位置
            lastRet = -1; // 这里也是需要注意的点，下面会讲解！！！！！！
            expectedModCount = modCount; // 此时modCount已更新，在这里更新expectedModCount
        } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
        }
    }

    @Override
    @SuppressWarnings("unchecked")
    public void forEachRemaining(Consumer<? super E> consumer) { // todo 有机会认识认识Consumer
        Objects.requireNonNull(consumer);
        final int size = ArrayList.this.size;
        int i = cursor;
        if (i >= size) {
            return;
        }
        final Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length) {
            throw new ConcurrentModificationException();
        }
        while (i != size && modCount == expectedModCount) {
            consumer.accept((E) elementData[i++]);
        }
        // update once at end of iteration to reduce heap write traffic
        cursor = i;
        lastRet = i - 1;
        checkForComodification();
    }

    final void checkForComodification() {
        if (modCount != expectedModCount) //不相等时，抛出ConcurrentModificationException异常
            throw new ConcurrentModificationException();
    }
}

　　Itr 内部没有构造方法，使用的是默认提供的构造方法。

　　注意： 在遍历的过程中，如果调用了 Itr 的 remove() 方法后，中间如果没有使用 next() 方法 ，紧跟着又使用了 remove() 方法之后，会抛出 IllegalStateException 异常。在 next() 和 remove() 中，lastRet 都经过了修改，next() 在返回当前位置元素的时候，将lastRet 赋值为当前元素位置；而在 remove() 方法中，是将 cursor 赋值为当前元素的位置，lastRet 赋值为-1，再次调用 remove() 方法，在其第一行代码中会检验出 lastRet < 0,抛出 IllegalStateException 异常。

　　在 next() 和 remove() 实际操作之前都会调用 checkForComodification() 用于检验 Itr() 实例中的 expectedModCount 和外部类 ArrayList 的 modCount 是否相等。

7、listIterator方法

　　java提供了两个listiterator方法，一个无参数，从 elementData开始位置返回一个 ListIterator 对象；另一个有参数，从数组指定位置返回 listIterator 对象。

 

public ListIterator<E> listIterator() {
        return new ListItr(0);
}
public ListIterator<E> listIterator(int index) {
        if (index < 0 || index > size) // 允许 index = size
            throw new IndexOutOfBoundsException("Index: "+index);
        return new ListItr(index);
}

 

　　下面介绍一下ListItr：可以看到，返回的是ListItr 对象，该类也是ArrayList 的内部类，继承自 ArrayList 内部类同时实现了 ListIterator 接口：

private class ListItr extends Itr implements ListIterator<E> { }

　　既然 ListItr 继承自 Itr 类，那么 ListItr 也会存在它的三个成员变量 cursor、lastRet 和 expectedModCount，调用无参数构造初始化与 Itr 的无参数构造方法没什么区别，有参数的构造方法会将 cursor 赋值。

ListItr(int index) {
        super();
        cursor = index;
}

 　　ListIterator 不仅能够向后遍历，还能够向前遍历，介绍一下内部的方法

　　

public boolean hasPrevious() { // 判断是否有前一节点
        return cursor != 0;
    }

    public int nextIndex() { // 下一个访问节点的位置
        return cursor;
    }

    public int previousIndex() { // 前一个节点的位置
        return cursor - 1;
    }

    @SuppressWarnings("unchecked")
    public E previous() {
        checkForComodification(); // 判断exceptedModCount 是否等于 ModCount
        int i = cursor - 1;
        if (i < 0)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length) // 多线程并发可能会遇到
            throw new ConcurrentModificationException();
        cursor = i; // 向前遍历后，下一访问节点改为前一节点
        return (E) elementData[lastRet = i]; // 上一个访问节点的位置改变
    }

    public void set(E e) {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification(); // 判断exceptedModCount 是否等于 ModCount

        try {
            ArrayList.this.set(lastRet, e); // 将上一访问节点的元素设为新值
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    public void add(E e) {
        checkForComodification(); // 判断exceptedModCount 是否等于 ModCount

        try {
            int i = cursor;
            ArrayList.this.add(i, e); // 调用外部类方法
            cursor = i + 1;
            lastRet = -1; // 同样上一访问节点会置为-1，所以不能同时调用add和set或者add和remove
            expectedModCount = modCount; // expectModCount 会修改
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
}

　　ArrayList 是 fail-fast（快速失败）的，当一个线程对其进行迭代时，另一个线程对其发生结构性的改变，就会抛出ConcurrentModificationExceptiion异常。

java容器体系（二）----List（ArrayList）

原文：https://www.cnblogs.com/guaniu2750/p/13610117.html
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！