A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 不二晨 金牌黑马   /  2018-12-14 09:34  /  530 人查看  /  2 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

1.List 简述(来自ArrayList注释)

List 接口的大小可变数组的实现。实现了所有可选列表操作,并允许包括 null 在内的所有元素。除了实现 List 接口外,此类还提供一些方法来操作内部用来存储列表的数组的大小。(此类大致上等同于 Vector 类,除了此类是不同步的。)

size、isEmpty、get、set、iterator 和 listIterator 操作都以固定时间运行。add 操作以分摊的固定时间 运行,也就是说,添加 n 个元素需要 O(n) 时间。其他所有操作都以线性时间运行(大体上讲)。与用于 LinkedList 实现的常数因子相比,此实现的常数因子较低。

每个 ArrayList 实例都有一个容量。该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向 ArrayList 中不断添加元素,其容量也自动增长。并未指定增长策略的细节,因为这不只是添加元素会带来分摊固定时间开销那样简单。

在添加大量元素前,应用程序可以使用 ensureCapacity 操作来增加 ArrayList 实例的容量。这可以减少递增式再分配的数量。

**注意,此实现不是同步的。**如果多个线程同时访问一个 ArrayList 实例,而其中至少一个线程从结构上修改了列表,那么它必须 保持外部同步。(结构上的修改是指任何添加或删除一个或多个元素的操作,或者显式调整底层数组的大小;仅仅设置元素的值不是结构上的修改。)这一般通过对自然封装该列表的对象进行同步操作来完成。如果不存在这样的对象,则应该使用 Collections.synchronizedList 方法将该列表“包装”起来。这最好在创建时完成,以防止意外对列表进行不同步的访问:

List list = Collections.synchronizedList(new ArrayList(...));
1
此类的 iterator 和 listIterator 方法返回的迭代器是快速失败的:在创建迭代器之后,除非通过迭代器自身的 remove 或 add 方法从结构上对列表进行修改,否则在任何时间以任何方式对列表进行修改,迭代器都会抛出 ConcurrentModificationException。因此,面对并发的修改,迭代器很快就会完全失败,而不是冒着在将来某个不确定时间发生任意不确定行为的风险。

注意,迭代器的快速失败行为无法得到保证,因为一般来说,不可能对是否出现不同步并发修改做出任何硬性保证。快速失败迭代器会尽最大努力抛出 ConcurrentModificationException。因此,为提高这类迭代器的正确性而编写一个依赖于此异常的程序是错误的做法:迭代器的快速失败行为应该仅用于检测 bug。

类图



ArrayList 源码实现基于 jdk 1.8

源代码来源于 jdk 1.8
2.构造方法

ArrayList 字段说明

private static final int DEFAULT_CAPACITY = 10;        // 初始默认容量为10
transient Object[] elementData;                                        // 存放元素的数组
private int size;                // 这个值是实际数组包含元素的数量, 注意这个值不是数组的大小
private static final Object[] EMPTY_ELEMENTDATA = {};        // 空数组
1
2
3
4
无参的构造方法
源码注释: Constructs an empty list with an initial capacity of ten.(构造初始容量为10的列表);

源码分析,:DEFAULTCAPACITY_EMPTY_ELEMENTDATA是个 {}, 即空数组, 为什么初始容量为10? 下面看 add 方法时再解析

    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
1
2
3
创建初始容量的构造方法
源码注释:Constructs an empty list with the specified initial capacity.(构造指定容量的列表);

源码分析:如果参数 initcap > 0,则创建指定容量的里边,
如果 == 0,则创建空的数组,参数为0的情况效果和无参构造方法一样,因为 EMPTY_ELEMENTDATA = {}, DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {},
如果 < 0; 则抛出异常 IllegalArgumentException(合法或不正确的参数);

   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);
       }
   }
1
2
3
4
5
6
7
8
9
10
创建指定集合的列表
源码注释:Constructs a list containing the elements of the specified collection, in the order they are returned by the collection’s iterator.(构造一个指定的collection集合的列表, 安装collection 迭代器返回的顺序);

源码分析:参数 c 调用toArray()方法转换为数组赋给列表的属性elementData ,
如果集合 c 元素为0, 则创建默认容量为空的列表;
如果c > 0, 则判断类型, 再复制数组,此处具有填充的效果

    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            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
3.List 方法

1) 添加元素 add(E e)
源码注释: Appends the specified element to the end of this list.(添加一个元素到列表末尾)

源码分析:

添加元素前准备.:
a:数组初始化 ensureCapacityInternal()
b: 计数器 +1 ensureExplicitCapacity()
c: 数组是否已满,是否需要扩容        grow()
d: 把元素添加到数组里: elementData[size++] = e;

protected transient int modCount = 0;                //  这是在AbstractList里的一个瞬时变量用于控制list并发操作的计数器
1
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

/*
* a. 添加元素前的准备, 调用方法ensureCapacityInternal(size + 1) ,
* 判断 elementData是否为 {}空的未初始化的列表,如果 == {}, 则 返回默认的大小
* 如果 elementData != {}, 则调用方法ensureExplicitCapacity(minCapacity)
*/
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

/*
* b.
* 判断当前列表元素数量 + 1是否超过了elementData.length 的大小,
* 计算器 modCount++ 加1;
* 如果 >,则调用 grow(minCapacity)方法进行扩容;
*/
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

/*
* c. 扩容:
* 数组elementData 的容量扩大为原来的 1.5倍, 然后复制元素到新数组,
* 有源码可知, ArrayList运许创建的列表容量最大值为, Integer.MAX_VALUE = (2^32 - 1)
*/
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    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);
}
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
2. 获取元素 get(index)

源码注释: Returns the element at the specified position in this list.(获取指定位置上的元素)

源码分析: 传入数组的索引获取元素前要检查索引是否越界,
如果越界,则抛出异常 IndexOutOfBoundsException,最后调用 elementData(int index) 方法直接返回元素 E;

public E get(int index) {
    rangeCheck(index);
    return elementData(index);
}

private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

@SuppressWarnings("unchecked")
E elementData(int index) {
    return (E) elementData[index];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
3.删除指定位置的一个元素 remove(int index)

源码注释: Removes the element at the specified position in this list. Shifts any subsequent elements to the left (subtracts one from their indices).(删除指定索引的元素, 并且所有元素左移)

源码分析: 删除指定位置的元素,先检查下标再获取此元素; 最后调用 System 类中的arraycopy()方法把除去index位置的元素的其他元素全部左移,最后一个元素 elementData[–size] = null;最终数组的大小不变只是末尾的一个元素置为null
最终结果就像这样

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
[0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 14]
[0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, null]
关于 System.arraycopy() 方法实现这里不做探讨

    public static native void arraycopy(Object src,  int  srcPos,  dest, int destPos, length);
1
public E remove(int index) {
    rangeCheck(index);
    modCount++;
    E oldValue = elementData(index);
    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
    return oldValue;
}
1
2
3
4
5
6
7
8
9
10
4.删除指定元素,首次出现的元素 remove(object)

源码注释: Removes the first occurrence of the specified element from this list, if it is present. If the list does not contain the element, it is unchanged. More formally, removes the element with the lowest index i such that (o==null ? get(i)==null : o.equals(get(i))) (if such an element exists). Returns true if this list contained the specified element (or equivalently, if this list changed as a result of the call).
条件: (o == null ? get(i) == null : o.equals(get(i))), 移除首次出现的指定元素,

源码解析: 移除首次出现的指定元素, 循环size长度的数组, 如果 o == null , 则判断(elementData[index] == null), 如果 o != null , 则 o.equals(elementData[index]),
最后调用 fastremove(index) 从新拷贝元素;

public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

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
}
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
5.修改元素 set(index, element)

源码注释: Replaces the element at the specified position in this list with the specified element.(替换指定位置的元素)

源码解析: 修改指定位置的元素, 首先检查index 是否越界, 然后把index 位置的元素替换位当前元素

public E set(int index, E element) {
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}
1
2
3
4
5
6
7
以上5个操作是基本的crud操作, 下面要探讨List的其他操作
6.添加元素到指定位置 add(index, element)
源码注释: Inserts the specified element at the specified position in this list. Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).(添加元素到指定索引, 如果不是添加到最后的位置, 则右边的元素全部右移)

源码解析: 添加元素到指定位置时, 先检查下标是否越界, 再判断当前数组是否已满,
最后复制数组,把指定元素替换到数组里

public void add(int index, E element) {
    rangeCheckForAdd(index);
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    elementData[index] = element;
    size++;
}
1
2
3
4
5
6
7
7.获取列表元素的数量 size()

源码分析: 直接返回列表的 size 属性;

public int size() {
    return size;
}
1
2
3
8.判断列表是否为空 isEmpty()

源码分析: 如果列表的长度为 0, 则列表为空表; 这里所指的空是列表元素为0, 而不是 list 对象为 null

public boolean isEmpty() {
    return size == 0;
}
1
2
3
9.搜索元素 indexOf(object)

源码注释: Returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element. More formally, returns the lowest index i such that (o==null ? get(i)==null : o.equals(get(i))), or -1 if there is no such index.
(返回第一次出现此元素的索引, 如果没有找到此元素, 返回 -1)

**源码分析:**这里的算法和 remove(object) 方法一样,

public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData))
                return i;
    }
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
10.搜索最后出现此元素的索引 lastIndexOf(object)

源码注释: Returns the index of the last occurrence of the specified element in this list, or -1 if this list does not contain the element. More formally, returns the highest index i such that (o==null ? get(i)==null : o.equals(get(i))), or -1 if there is no such index.
(返回最后一次出现此元素的索引, 如果列表不包含此元素, 返回 -1)

源码解析: 此处是从后往前遍历的循环, 逻辑是 indexOf() 方法的对立;

public int lastIndexOf(Object o) {
    if (o == null) {
        for (int i = size-1; i >= 0; i--)
            if (elementData==null)
                return i;
    } else {
        for (int i = size-1; i >= 0; i--)
            if (o.equals(elementData))
                return i;
    }
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
11.判断是否包含指定元素 contains(object)

源码注释: Returns true if this list contains the specified element. More formally, returns true if and only if this list contains at least one element e such that (o == null ? e==null : o.equals(e)).(如果列表包含此元素, 则返回 true 否则 false)

源码分析: 从源码看, 此方法是 indexOf()的扩展.

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}
1
2
3
12. 清空列表 clear()

**源码注释:**Removes all of the elements from this list. The list will be empty after this call returns.(从此列表中删除所有元素。 此调用返回后,列表将为空)

源码分析: for循环把数组所有引用置空, size = 0

public void clear() {
    modCount++;
    // clear to let GC do its work
    for (int i = 0; i < size; i++)
        elementData = null;
    size = 0;
}
1
2
3
4
5
6
7
13.list 转数组 toArray()

源码注释: Returns an array containing all of the elements in this list in proper sequence (from first to last element).
The returned array will be “safe” in that no references to it are maintained by this list. (In other words, this method must allocate a new array). The caller is thus free to modify the returned array.
This method acts as bridge between array-based and collection-based APIs.
(返回一个包含列表所有元素的新的数组)

源码分析: 此方法返回一个 Object[] 类型的数组, 无法返回目标泛型的数组, 无法强制转换为目标数组, 比如 (String[])list.toArray() 会抛出异常 ClassCastException, 一般不推荐使用

public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}
1
2
3
14.list 转 toArray(T[] a)

源码注释: Returns an array containing all of the elements in this list in proper sequence (from first to last element); the runtime type of the returned array is that of the specified array. If the list fits in the specified array, it is returned therein. Otherwise, a new array is allocated with the runtime type of the specified array and the size of this list.

If the list fits in the specified array with room to spare (i.e., the array has more elements than the list), the element in the array immediately following the end of the collection is set to null. (This is useful in determining the length of the list only if the caller knows that the list does not contain any null elements.)
(把列表所有元素复制到给的数组中, 如果给定的数组大于列表长度, 多出的部分分配null)

源码分析: 从源码看, 如果 传入的数组a 小于列表的元素的数量,则调用 Arrays.copyOf()方法;否则 调用 System.arraycopy() 方法, 最后多出的部分,分配null;
推荐使用此转换方法:

                String[] ss = {};
                System.out.println(list.toArray(ss));
               
                输出为: [Ljava.lang.String;@3ffc5af1
1
2
3
4
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
    if (a.length < size)
        // Make a new array of a's runtime type, but my contents:
        return (T[]) Arrays.copyOf(elementData, size, a.getClass());
    System.arraycopy(elementData, 0, a, 0, size);
    if (a.length > size)
        a[size] = null;
    return a;
}
1
2
3
4
5
6
7
8
9
10
4.迭代器 Iterator

返回迭代器的方法有三个,iterator只支持向前遍历, listIterator 支持向前向后遍历

iterator()
listIterator()
listIterator(int index)
1) 获取迭代器对象iterator()

    public Iterator<E> iterator() {
        return new Itr();
    }
1
2
3
2) 获取列表迭代器 listIterator()

    public ListIterator<E> listIterator() {
        return new ListItr(0);
    }
1
2
3
3) 获取从指定位置开始的列表迭代器 listIterator(index)

    public ListIterator<E> listIterator(int index) {
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException("Index: "+index);
        return new ListItr(index);
    }
1
2
3
4
5
ArrayList 里有两个内部类 Itr 和 ListItr

关系图:


4) Itr 实现 Iterator 源码分析

    private class Itr implements Iterator<E> {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;
        .......... 忽略下面代码
    }
1
2
3
4
5
6
字段说明:
int cursor; //下一元素的索引, 当迭代时, 执行一次 next()方法 cursor++,
        当 cursor == size 和列表长度相等时即没有下一个元素;

int lastRet = -1;        //最后一个元素的索引, 调用 next()方法时被重新赋值  lastRet = i;

int expectedModCount = modCount;  
        // 因为ArrayList 是非线程安全的, 如果在迭代时列表被修改过,
        即 expectedModCount != modCount; 马上抛出异常 ConcurrentModificationException
1
2
3
4
5
6
7
8
9
是否有下一个元素hasNext():

源码分析: 下一元素索引小于列表的长度返回true

        public boolean hasNext() {
            return cursor != size;
        }
1
2
3
获取下一个元素 next()

源码分析: 获取元素前检查列表是否被修改过, 然后cursor +1, lastRet = cursor,最后返回元素

    public E next() {
        checkForComodification();
        int i = cursor; // 初始化为1, i = 1,
        // 如果没有调用 hasNext()方法直接调用next()方法获取元素有可能导致索引越界的异常
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }
    // 检查列表是否被修改过, add、set、remove 等操作都会导致modCount的值发生改变
        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
移除上一次调用next()方法返回的元素 remove()

源码注释: Removes from the underlying collection the last element returned by this iterator (optional operation). This method can be called only once per call to next. The behavior of an iterator is unspecified if the underlying collection is modified while the iteration is in progress in any way other than by calling this method.
(在每次调用next()方法是, 只能调用一次此方法)

源码解析: 在执行一次 next()方法后, 方可执行 remove(), 否则抛出异常IllegalStateException,
执行一次后, cursor 被修改, lastRet 重新赋 -1, expectedModCount = modCount;
所以在迭代列表时,只能使用迭代器的 remove()对列表删除元素

    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();
        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
5) ListItr 源码实现

ListItr 继承了 Itr 实现 ListIterator, 并且有一个带参数的构造方法;

ListIterator 源码注释: 系列表迭代器,允许程序员按任一方向遍历列表、迭代期间修改列表,并获得迭代器在列表中的当前位置。ListIterator 没有当前元素;它的光标位置 始终位于调用 previous() 所返回的元素和调用 next() 所返回的元素之间。长度为 n 的列表的迭代器有 n+1 个可能的指针位置,如下面的插入符举例说明:

                  Element(0)   Element(1)   Element(2)   ... Element(n-1)
                cursor positions:  ^            ^            ^            ^                  ^
1
2
注意,remove() 和 set(Object) 方法不是 根据光标位置定义的;它们是根据对调用 next() 或 previous() 所返回的最后一个元素的操作定义的。

private class ListItr extends Itr implements ListIterator<E> {
        ListItr(int index) {
            super();
            cursor = index;
        }
       ......忽略
}
1
2
3
4
5
6
7
这里只分析ListIterator 特有的方法

这里 cursor 直接继承自 Itr的属性, 作用是列表的索引;

        // 判断是否有前一个元素
        public boolean hasPrevious() {
            return cursor != 0;
        }
       
                // 获取下一个索引
        public int nextIndex() {
            return cursor;
        }

                // 获取前一个元素索引
        public int previousIndex() {
            return cursor - 1;
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
获取前一个元素 previous()

源码分析: 在使用时获取前一个元素,必须先执行hasPrevious() 方法判断是否有下一个元素;
在调用previous() 方法时,先查列表是否被修改过, 然后索引cursor - 1,
最终索引值被 -1, 元素被取出

        public E previous() {
            checkForComodification();
            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];
        }
1
2
3
4
5
6
7
8
9
10
11
修改了列表指定索引的元素 set(E e)

源码分析: 从代码逻辑看, 此处修改的值为最后一次调用previous()获取的那个值,
此处的操作直接改变列表指定的值

        public void set(E e) {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();
            try {
                ArrayList.this.set(lastRet, e);
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
1
2
3
4
5
6
7
8
9
10
往列表添加一个元素 add(E e)

源码分析: 从源码的逻辑看, 此处添加的元素到列表指定索引处的位置, 这个索引处就是最后一次调用 previous() 方法后返回的元素的索引位置的左边

        public void add(E e) {
            checkForComodification();
            try {
                int i = cursor;
                ArrayList.this.add(i, e);
                cursor = i + 1;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
---------------------
【转载】仅作分享,侵删
作者:呆小陈
原文:https://blog.csdn.net/weixin_39554102/article/details/84950999


2 个回复

倒序浏览
奈斯
回复 使用道具 举报
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马