Java集合分析2

Posted on Edited on In
表

[TOC]

表

ArrayList

简介

ArrayList实现了List的接口, 是一个顺序存储的容器, 允许放入null元素,底层通过数组实现, 线程非安全.ArrayList有一个capacity表示容量, 如果在向容器中添加元素且容量不足的时候, 容器会自增大底层数组的大小.

源码剖析

成员变量

1
2
3
4
5
6
7
8
9
10
11
12
//默认的初始化容量
private static final int DEFAULT_CAPACITY = 10;
//空表实例的默认元素
private static final Object[] EMPTY_ELEMENTDATA = {};
//空实例的默认大小空数组. 和上面的EMPTY_ELEMENTDATA甲乙区分是为了当添加第一个元素的时扩容多大.
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//存储表对象的数组
transient Object[] elementData;
//表的大小
private int size
//最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

方法分析

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
//构造函数1
    public ArrayList() {
      //将内部的数组初始化空数组.
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
//构造函数2
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
          //以initialCapacity初始化数组大小
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
          //如果传参为0 则初始化一个空数组
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
          // 非法草书抛出异常.
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
//构造函数3
//直接使用一个集合初始化一个ArrayList.
    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)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

增删改查
扩容相关函数
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
// 增大容量来容纳指定数量的元素
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
      //新的数组长度是旧数组长度的1.5倍
        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:
      //拷贝数组. 最终调用的是System.arrayCopy
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
	//大容量
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
      //if 大于最大容量 = Integer.MAX_VALUE
      //else 等于最大的数组大小.
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

	//
   private void ensureCapacityInternal(int minCapacity) {
     //如果ElementData恒等于默认的空数组.
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
          // 取最大的值作为容量.
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
				//扩容. 
        ensureExplicitCapacity(minCapacity);
    }
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++; //更改++
				
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
          //如果需求组的容量大于数组的长度, 那么要扩容.
            grow(minCapacity);
    }



增
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
    //直接增加.
		public boolean add(E e) {
      //检查容量及扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
      //提那家元素
        elementData[size++] = e;
      //添加成功返回true
        return true;
    }
//插入
//检查范围
    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
			
//
	    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自增
        size++;
    }
//将一个集合直接添加到ArrayList
    public boolean addAll(Collection<? extends E> c) {
      //转为数组
        Object[] a = c.toArray();
      //集合的长度
        int numNew = a.length;
      // 检查容量
        ensureCapacityInternal(size + numNew);  // Increments modCount
      //拷贝
        System.arraycopy(a, 0, elementData, size, numNew);
      //size增加numNew
        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);

        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }
查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//指定位置索引
    public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }
//直接索引第一个可以找到的对象
    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;
    }
删除
1
2
3
4
5
6
7
8
9
10
//直接清除
    public void clear() {
        modCount++;
				//大量的数据并且频繁操作可能引发频繁GC
        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;
    }
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
//删除指定位置元素
    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);
      //尾部的元素置null
        elementData[--size] = null; // clear to let GC do its work
//将被删除的元素返回
        return oldValue;
    }

//删除第一个能找到的指定元素
//快速移除, 不检查边界, 并且不返回被移除的对象.
    private void fastRemove(int index) {
      //修改计数+1;
        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
    }

public boolean remove(Object o) {
  //如果指定的恒等于null
        if (o == null) {
          //找到这个null元素
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                  //快速移动
                    fastRemove(index);
                    return true;
                }
        } else {
          //找到这个非null元素, 并移除
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

        protected void removeRange(int fromIndex, int toIndex) {
            if (ArrayList.this.modCount != this.modCount)
                throw new ConcurrentModificationException();
            parent.removeRange(parentOffset + fromIndex,
                               parentOffset + toIndex);
            this.modCount = parent.modCount;
            this.size -= toIndex - fromIndex;
        }

//AbstractList
/*
Overriding this method to take advantage of
     * the internals of the list implementation can <i>substantially</i>
     * improve the performance of the {@code clear} operation on this list
     * and its subLists.
     */
    protected void removeRange(int fromIndex, int toIndex) {
        ListIterator<E> it = listIterator(fromIndex);
        for (int i=0, n=toIndex-fromIndex; i<n; i++) {
            it.next();
            it.remove();
        }
    }

//implementation improve the performance
//为什么这个方法是protected 可以参考Effective Java一书中所述.
//TODO 解释为什么
//这个方法是给subList用的
    protected void removeRange(int fromIndex, int toIndex) {
        // Android-changed: Throw an IOOBE if toIndex < fromIndex as documented.
        // All the other cases (negative indices, or indices greater than the size
        // will be thrown by System#arrayCopy.
        if (toIndex < fromIndex) {
            throw new IndexOutOfBoundsException("toIndex < fromIndex");
        }

        modCount++;
        int numMoved = size - toIndex;
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                         numMoved);

        // clear to let GC do its work
        int newSize = size - (toIndex-fromIndex);
        for (int i = newSize; i < size; i++) {
            elementData[i] = null;
        }
        size = newSize;
    }


//移除所有C集合中包括的对象
    public boolean removeAll(Collection<?> c) {
      //检查非空
        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++)
                if (c.contains(elementData[r]) == complement)
                  //在这里实际上用了个双指针, 将后面的元素移动到被删除的元素上, 这样做的目的是一边删除(占位置)一边移动元素, 效率更高
                    elementData[w++] = elementData[r];
        } finally {
            // Preserve behavioral compatibility with AbstractCollection,
            // even if c.contains() throws.
          //这里可能是为了做一些防御
            if (r != size) {
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;
            }
          
            if (w != size) {
                // clear to let GC do its work
              //将w后续的元素释放
                for (int i = w; i < size; i++)
                    elementData[i] = null;
              //修改操作数
                modCount += size - w;
              //
                size = w;
                modified = true;
            }
        }
        return modified;
    }

//将不属于C中的元素移除.
    public boolean retainAll(Collection<?> c) {
        Objects.requireNonNull(c);
      //参考上述的描述, 这里complement = true, 刚好和removeAll相反.
      //这个方法设计的非常巧妙
        return batchRemove(c, true);
    }
改
1
2
3
4
5
6
7
8
9
//这个没啥说的 非常简单,直接数组赋值就行了,注意不要越界的检查.
		public E set(int index, E element) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

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

SubList以及迭代器

迭代器

先看几个方法

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
   /**
    * Returns an iterator over the elements in this list in proper sequence.
    *
    * <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
    *
    * @return an iterator over the elements in this list in proper sequence
    */
   public Iterator<E> iterator() {
     //返回了Itr实例, 看ArrayList怎么实现的
       return new Itr();
   }

/**
    * An optimized version of AbstractList.Itr
    这里说的是一个优化过的AbstractList.Itr
    */
   private class Itr implements Iterator<E> {
       // Android-changed: Add "limit" field to detect end of iteration.
       // The "limit" of this iterator. This is the size of the list at the time the
       // iterator was created. Adding & removing elements will invalidate the iteration
       // anyway (and cause next() to throw) so saving this value will guarantee that the
       // value of hasNext() remains stable and won't flap between true and false when elements
       // are added and removed from the list.
       protected int limit = ArrayList.this.size; // 迭代器的边界

       int cursor;       // index of next element to return
       int lastRet = -1; // index of last element returned; -1 if no such
       int expectedModCount = modCount; //

       public boolean hasNext() {
           return cursor < limit;
       }

       @SuppressWarnings("unchecked")
       public E next() {
           if (modCount != expectedModCount) //如果修改和期望不符, 则抛出多线程修改异常.
               throw new ConcurrentModificationException();
           int i = cursor;
           if (i >= limit) //边界检查
               throw new NoSuchElementException();
           Object[] elementData = ArrayList.this.elementData;
           if (i >= elementData.length)
               throw new ConcurrentModificationException();
           cursor = i + 1; //使用cursor增加1
           return (E) elementData[lastRet = i];
       }

       public void remove() {
           if (lastRet < 0)
               throw new IllegalStateException();
           if (modCount != expectedModCount)
               throw new ConcurrentModificationException();

           try {
               ArrayList.this.remove(lastRet);
               cursor = lastRet;
               lastRet = -1;
               expectedModCount = modCount;
               limit--;
           } catch (IndexOutOfBoundsException ex) {
               throw new ConcurrentModificationException();
           }
       }

       @Override
       @SuppressWarnings("unchecked") //foreach的实现
       public void forEachRemaining(Consumer<? super E> 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;

           if (modCount != expectedModCount)
               throw new ConcurrentModificationException();
       }
   }


  /**
    * An optimized version of AbstractList.ListItr
    	 优化过的迭代器, 能够前后移动,是一个双向的迭代器,并且支持增删改查.
    */
   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() {
           if (modCount != expectedModCount)
               throw new ConcurrentModificationException();
           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();
           if (modCount != expectedModCount)
               throw new ConcurrentModificationException();

           try {
               ArrayList.this.set(lastRet, e);
           } catch (IndexOutOfBoundsException ex) {
               throw new ConcurrentModificationException();
           }
       }

       public void add(E e) {
           if (modCount != expectedModCount)
               throw new ConcurrentModificationException();

           try {
               int i = cursor;
               ArrayList.this.add(i, e);
               cursor = i + 1;
               lastRet = -1;
               expectedModCount = modCount;
               limit++;
           } catch (IndexOutOfBoundsException ex) {
               throw new ConcurrentModificationException();
           }
       }
   }
ConcurrentModificationException

在使用迭代器的时候, 经常会遇见一个问题, 困扰大家很久.

举个栗子, 我明明没有在多个线程中修改List 为什么还会出现这个问题呢?

答案是看源码, 最好写一个demo主动报错debug就知道了

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
fun main() {
    val mList = ArrayList<Int>(10)
    (1..10).forEach { i ->
        mList.add(i) 
    }
  //modCount = 10 对list做了10次add操作
    val itr = mList.iterator()
  // modCount = expectedModCount = 10
  

    while (itr.hasNext()) {
      
      
      /**
              public E next() {
            checkForComodification();
            int i = cursor;
            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];
        }
        		//这里会检查modeCount != expectedModCount
                final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
      */
        val value = itr.next() //   
        if (value == 5)
            mList.remove(value) //此时modeCount = 11
    }
}
//或者使用foreach也可以, foreach的底层实现就是iterator

以上的代码就会报错.

分析原因可以参考注释.

主要原因就是在修改ArrayList的时候, 直接使用了ArrayList#remove这种操作, 使得modCount和expectedModCount不再相等, 解决方法就是如果使用迭代器遍历List, 那么在需要修改arrayList的时候, 也使用迭代器, 保证上述两个值始终相等.如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
fun main() {
    val mList = ArrayList<Int>(10)
    (1..10).forEach { i ->
        mList.add(i)
    }
    val itr = mList.iterator()

    while (itr.hasNext()) {
        val value = itr.next()
        if (value == 5)
            itr.remove()
    }
    print(mList)
}
SubList

子串就代表的是ArrayList的子List, 上代码.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
private class SubList extends AbstractList<E> implements RandomAccess {
    private final AbstractList<E> parent; //父List
    private final int parentOffset;  // 相对父List的偏移
    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 = ArrayList.this.modCount;
    }
//同ArrayList, 修改的是父List
    public E set(int index, E e) {
        rangeCheck(index);
        checkForComodification();
        E oldValue = ArrayList.this.elementData(offset + index);
        ArrayList.this.elementData[offset + index] = e;
        return oldValue;
    }
//同上
    public E get(int index) {
        rangeCheck(index);
        checkForComodification();
        return ArrayList.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;
    }

    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);
    }

    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();
    }

    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 = ArrayList.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 = ArrayList.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 = ArrayList.this.elementData;
                if (offset + i >= elementData.length)
                    throw new ConcurrentModificationException();
                cursor = i;
                return (E) elementData[offset + (lastRet = i)];
            }

            @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 = ArrayList.this.elementData;
                if (offset + i >= elementData.length) {
                    throw new ConcurrentModificationException();
                }
                while (i != size && modCount == expectedModCount) {
                    consumer.accept((E) elementData[offset + (i++)]);
                }
                // update once at end of iteration to reduce heap write traffic
                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 = ArrayList.this.modCount;
                } catch (IndexOutOfBoundsException ex) {
                    throw new ConcurrentModificationException();
                }
            }

            public void set(E e) {
                if (lastRet < 0)
                    throw new IllegalStateException();
                checkForComodification();

                try {
                    ArrayList.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 = ArrayList.this.modCount;
                } catch (IndexOutOfBoundsException ex) {
                    throw new ConcurrentModificationException();
                }
            }

            final void checkForComodification() {
                if (expectedModCount != ArrayList.this.modCount)
                    throw new ConcurrentModificationException();
            }
        };
    }

    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 (ArrayList.this.modCount != this.modCount)
            throw new ConcurrentModificationException();
    }

    public Spliterator<E> spliterator() {
        checkForComodification();
        return new ArrayListSpliterator<E>(ArrayList.this, offset,
                                           offset + this.size, this.modCount);
    }
}

LinkedList

链表 ,使用引用(指针)将各个节点串联起来的一种数据结构, 在内存中的存储地址是非连续的.

先看一下LinkedList实现了哪些接口.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public interface Queue<E> extends Collection<E> {
  boolean add(E e);
  boolean offer(E e);
  E remove();
  E poll(); //retrieves and remove the head of this queue
  E element();// retrieves the head but not remove, throw exception if queue is empty
  E peek();// retrieves the head but not remove. not throw exception.
}

public interface Deque<E> extends Queue<E> {
  //,,,,
}
public interface List<E> extends Collection<E> {
  
}
public abstract class AbstractSequentialList<E> extends AbstractList<E> {
}

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
    
    }

节点

1
2
3
4
5
6
7
8
9
10
11
private static class Node<E> {
    E item; //存储的元素
    Node<E> next; //前向
    Node<E> prev; //后向

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

成员变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
transient int size = 0; //size 在序列化时不进行序列化
   /**
    * Pointer to first node.
    * Invariant: (first == null && last == null) ||
    *            (first.prev == null && first.item != null)
    */
 transient Node<E> first; //第一个节点
   /**
    * Pointer to last node.
    * Invariant: (first == null && last == null) ||
    *            (last.next == null && last.item != null)
    */
 transient Node<E> last; //最后一个节点.


构造函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Constructs an empty list.
 */
public LinkedList() {
}

/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 *
 * @param  c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

方法分析

增删改查

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * Links e as first element.
 */
private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}
1
2
3
4
// 将指定的元素插入到list的开头.  
  	public void addFirst(E e) {
        linkFirst(e);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * Links e as last element.
 */
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}
1
2
3
4
5
6
7
8
9
10
/**
 * Appends the specified element to the end of this list.
 *
 * <p>This method is equivalent to {@link #add}.
 *
 * @param e the element to add
 */
public void addLast(E e) {
    linkLast(e);
}
增
1
2
3
4
5
6
7
8
9
10
11
12
/**
 * Appends the specified element to the end of this list.
 *
 * <p>This method is equivalent to {@link #addLast}.
 *
 * @param e element to be appended to this list
 * @return {@code true} (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    linkLast(e);
    return true;
}
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
public boolean addAll(Collection<? extends E> c) {
   return addAll(size, c);
}



public boolean addAll(int index, Collection<? extends E> c) {
  			//位置检查
        checkPositionIndex(index);
					//将C转换为array
        Object[] a = c.toArray();
  			//a的长度
        int numNew = a.length;
        if (numNew == 0)
            return false;
				//两个node
        Node<E> pred, succ;
        //如果刚好是到尾部, 将pred指向last
        if (index == size) {
            succ = null;
            pred = last;
        } else {
        //否则在指定的index处插入.
            succ = node(index);
            pred = succ.prev;
        }
        //将元素逐个插入到list中
        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            Node<E> newNode = new Node<>(pred, e, null);
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            pred = newNode;
        }
				//如果succ是null则, last=pred (last指向最后一个非空元素)
        if (succ == null) {
            last = pred;
        } else {
          //如果succ不为空, 那么将pred和succ连接起来.
            pred.next = succ;
            succ.prev = pred;
        }
				//size增加number
        size += numNew;
  			//modCount自增.
        modCount++;
        return true;
    }

		//位置检查.
    private void checkPositionIndex(int index) {
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
  /**
     * Tells if the argument is the index of a valid position for an
     * iterator or an add operation.
     */
    private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }
删除
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
    //移除首个元素并返回
		public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
          //注意first == null会抛出异常
            throw new NoSuchElementException();
       //详细方法
        return unlinkFirst(f);
    }


    /**
     * Unlinks non-null first node f.
     * 整个函数将移除头部, 并将头部指向头部的下一个元素.
     */
    private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null;
        final E element = f.item;
        final Node<E> next = f.next;
        f.item = null;
        f.next = null; // help GC
        first = next;
        if (next == null)
            last = null;
        else
            next.prev = null;
        size--;
        modCount++;
        return element;
    }

    /**
     * Removes and returns the last element from this list.
     *
     * @return the last element from this list
     * @throws NoSuchElementException if this list is empty
     */
    //移除末尾元素
    public E removeLast() {
        final Node<E> l = last;
        if (l == null)
            //注意last == null会抛出异常
            throw new NoSuchElementException();
        //详细方法
        return unlinkLast(l);
    }

    /**
     * Unlinks non-null last node l.
     */
    private E unlinkLast(Node<E> l) {
        // assert l == last && l != null;
        final E element = l.item;
        final Node<E> prev = l.prev;
        l.item = null;
        l.prev = null; // help GC
        last = prev;
        if (prev == null)
            first = null;
        else
            prev.next = null;
        size--;
        modCount++;
        return element;
    }

/**
* 移除函数.
*/
		public boolean remove(Object o) {
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * Unlinks non-null node x.
     */
			E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item; //当前
        final Node<E> next = x.next; // 前向节点
        final Node<E> prev = x.prev; // 后向节点

        if (prev == null) {  //边界
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }

        if (next == null) {  //边界
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }

        x.item = null; // 释放元素
        size--;  // size自减
        modCount++; //修改计数自增
        return element;
    }

    public E remove(int index) {
        checkElementIndex(index); //检查index是否在边界之内, 否则抛出数组越界异常.
        return unlink(node(index));
    }
WechatIMG23
改

改就一个接口, 直接将制定的index上的元素置为指定的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * Replaces the element at the specified position in this list with the
 * specified element.
 *
 * @param index index of the element to replace
 * @param element element to be stored at the specified position
 * @return the element previously at the specified position
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}
查
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
    /**
     * Returns the element at the specified position in this list.
     *
     * @param index index of the element to return
     * @return the element at the specified position in this list
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }
//注意这里返回是非空的
    /**
     * Returns the (non-null) Node at the specified element index.
     */
    Node<E> node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

    /**
     * Returns {@code true} if this list contains the specified element.
     * More formally, returns {@code true} if and only if this list contains
     * at least one element {@code e} such that
     * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
     *
     * @param o element whose presence in this list is to be tested
     * @return {@code true} if this list contains the specified element
     */
    public boolean contains(Object o) {
        return indexOf(o) != -1;
    }
//索引指定对象o
    public int indexOf(Object o) {
        int index = 0;
      //如果o是空的, 找到第一个null元素
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null)
                    return index;
                index++;
            }
          //否则找到和o相等的元素,并返回index.
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item))
                    return index;
                index++;
            }
        }
        return -1;
    }
一些其他特殊操作

peek 返回链表头但不删除

poll 返回链表且删除元素

offer 将指定元素添加到链表末尾

每个方法都有xxFirst xxLast

此外, 还有类似栈的操作

push添加到表头(入栈)

pop 将表头元素移除(出栈)