java常用集合类 List

发表于 | 分类于 | 阅读数

如果确定插入、删除的元素是在前半段，那么就使用LinkedList；如果确定你插入、删除的元素在比较靠后的位置，那么可以考虑使用ArrayList，当然1.8LinkedList有头尾指针速度是一样的。
如果你不能确定你要做的插入、删除是在哪儿呢？建议使用LinkedList，因为一来LinkedList整体插入、删除的执行效率比较稳定，没有ArrayList这种越往后越快的情况因为需要移动元素；二来插入元素的时候，元素多了ArrayList就要进行一次扩容，ArrayList数组扩容是一个既消耗时间又消耗空间的操作。

  1. ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。
  2. 对于随机访问get和set，ArrayList优于LinkedList，因为LinkedList要移动指针，除非位置离头或者尾部很近
  3. 对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据，除非操作发送在ArrayList尾部
  4. LinkedList比ArrayList更占内存，因为LinkedList的节点除了存储数据，还存储了两个引用，一个指向前一个元素，一个指向后一个元素。

时间复杂度：

ArrayList线性表

get(index) 直接读取下标索引，类似数组内存地址可以通过下标计算得出 O(1)
add(E) 加在末尾　O(1)
add(index,E) 加在指定位置后，后面元素需要向后移动　O(n)
remove(index) 直接读取下标索引查找元素O(1),然后移动后面的元素O(n) , O(n)

LinkedList 链表

get(E) 获取指定元素，遍历，需要一个for循环　　O(n)
add(E) 加到末尾 O(1)
add(index,E) 需要查找第几个元素，指针操作　　O(n)
remove(index) 从头向后遍历，直到找到第index-1个结点，这需要O(n)时间；找到以后，改变指针的指向，这需要O(1)的时间。所以这种情况下，时间复杂度为O(n)
remove(E) 删除指定节点,直接指针操作E节点　O(1)

有序性：

ArrayList、LinkedList、Vector都是有序的。 Map是无序的，LinkedHashMap是有序的，通过链表链接顺序。Set是无序的，并且set中的元素不能重复，set的底层实现其实是Map，有HashSet、TreeSet，LinkedHashSet是有序的。

代码基于JDK1.8

ArrayList

  1. 线性表，底层是object数组存数据
  2. 扩容机制：默认大小是10，扩容是扩容到之前的1.5倍大小，每次扩容是将原数组中的数据复制到新的数组中
  3. 添加:如果是添加到数组的指定位置,那么可能会挪动大量的数组元素,并且可能会触发扩容机制;如果是添加到末尾的话,那么只可能触发扩容机制.
  4. 删除:如果是删除数组指定位置的元素,那么可能会挪动大量的数组元素;如果是删除末尾元素的话,那么代价是最小的. ArrayList里面的删除元素,其实是将该元素置为null.
  5. 查询和改某个位置的元素是非常快的 O(1)

ArrayList Class

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
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    /**
     * 它使用了transient关键字来修饰，这意味着ArrayList不会被序列化
     *
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */
    transient Object[] elementData; // non-private to simplify nested class access

    /**
    * 返回值都是true
    * 确保当前数组的容量
    * 将需要添加的元素，也就是这里的e加到数组的末尾。size当前数组的大小，size++是当前数组的后一位。
    * 此方法并没有做任何同步处理.整个Arraylist里的所有方法都没有做任何同步处理。因此这些涉及数据操作的方法都不是线程安全的。
    *
    * Appends the specified element to the end of this list.
    *
    * @param e element to be appended to this list
    * @return <tt>true</tt> (as specified by {@link Collection#add})
    *

    */
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!! 
        elementData[size++] = e;
        return true;
    }

    /**
     * 要添加的目标集合如果同时进行删除可能出现元素为空少元素的情况？其实是不会的，刚刚开始执行了c.toArray();后续过程目标的长度是不会变的。执行的那个时刻数据是一致的。可以考虑定义个锁进行加锁。最终一致性可以考虑目标集合用CopyOnWriteArrayList
     * Appends all of the elements in the specified collection to the end of
     * this list, in the order that they are returned by the
     * specified collection's Iterator.  The behavior of this operation is
     * undefined if the specified collection is modified while the operation
     * is in progress.  (This implies that the behavior of this call is
     * undefined if the specified collection is this list, and this
     * list is nonempty.)
     *
     * @param c collection containing elements to be added to this list
     * @return <tt>true</tt> if this list changed as a result of the call
     * @throws NullPointerException if the specified collection is null
     */
    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;
        return numNew != 0;
    }

    /**
     * 检测传入的参数，数组的下标是否越界
     * 若通过检测，则返回对应位置的元素即可，因为数组是有序排列的
     *
     * 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) {
        rangeCheck(index);

        return elementData(index);
    }

     /**
     * 注意：null直接用两个等号判断，而非null对象，则是用equals方法判断相等
     * 遍历数组，找到相等对象，确定下标，然后删除当前数组中该下标的元素
     *
     * 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
     * <tt>i</tt> such that
     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
     * (if such an element exists).  Returns <tt>true</tt> if this list
     * contained the specified element (or equivalently, if this list
     * changed as a result of the call).
     *
     * @param o element to be removed from this list, if present
     * @return <tt>true</tt> if this list contained the specified element
     *

     */
    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;
    }

     /*
     *
     * 删除不用检查越界
     * modCount在父类中定义，结构变化数modCount加一，计算需要移动的数据元素，为当前数组大小，减去删除元素位置，再减去1，要减去1因为数组下标从0开始
     * 当前数组元素一共9个，然后假设我要删除的是第6个元素。即size＝9，index＝5（从0开始）。要删除的元素是6，需要移动的元素即为三个。
     * size-index-1=9-5-1=3
     * System类下的arraycopy这个方法的作用就是根据需要移动的元素，重新构造一个没有要删除元素的新数组。它的实现是一个native方法。
     *
     * Private remove method that skips bounds checking and does not
     * return the value removed.

     */
    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
    }
}

AbstractList

在ArrayList的所有涉及结构变化的方法中都增加modCount的值，包括：add()、remove()、addAll()、removeRange()及clear()方法。这些方法每调用一次，modCount的值就加1。

add()及addAll()方法的modCount的值是在其中调用的ensureCapacity()方法中增加的。
Itr实现了Iterator()接口，其中也定义了一个int型的属性：expectedModCount，这个属性在Itr类初始化时被赋予ArrayList对象的modCount属性的值。
在next()方法中调用了checkForComodification()方法，进行对修改的同步检查

1
2
3
final void checkForComodification()  {  
　if (modCount != expectedModCount) throw new ConcurrentModificationException(); 
}

在对一个集合对象进行跌代操作的同时，并不限制对集合对象的元素进行操作，这些操作包括一些可能引起跌代错误的add()或remove()等危险操作。在AbstractList中，使用了一个简单的机制来规避这些风险。 这就是modCount和expectedModCount的作用所在

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
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
    /**
     * The number of times this list has been <i>structurally modified</i>.
     * Structural modifications are those that change the size of the
     * list, or otherwise perturb it in such a fashion that iterations in
     * progress may yield incorrect results.
     *
     * <p>This field is used by the iterator and list iterator implementation
     * returned by the {@code iterator} and {@code listIterator} methods.
     * If the value of this field changes unexpectedly, the iterator (or list
     * iterator) will throw a {@code ConcurrentModificationException} in
     * response to the {@code next}, {@code remove}, {@code previous},
     * {@code set} or {@code add} operations.  This provides
     * <i>fail-fast</i> behavior, rather than non-deterministic behavior in
     * the face of concurrent modification during iteration.
     *
     * <p><b>Use of this field by subclasses is optional.</b> If a subclass
     * wishes to provide fail-fast iterators (and list iterators), then it
     * merely has to increment this field in its {@code add(int, E)} and
     * {@code remove(int)} methods (and any other methods that it overrides
     * that result in structural modifications to the list).  A single call to
     * {@code add(int, E)} or {@code remove(int)} must add no more than
     * one to this field, or the iterators (and list iterators) will throw
     * bogus {@code ConcurrentModificationExceptions}.  If an implementation
     * does not wish to provide fail-fast iterators, this field may be
     * ignored.
     */
    protected transient int modCount = 0;
}

从srcPos到srcPos + length – 1的元素拷贝到目标数组的destPos到destPos + length – 1的位置处

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public final class System {
   /**
     * Copies an array from the specified source array, beginning at the
     * specified position, to the specified position of the destination array.
     * ...
     * ...
     * @param      src      the source array. 源数组
     * @param      srcPos   starting position in the source array. 源数组拷贝元素的起始位置
     * @param      dest     the destination array. 目标数组
     * @param      destPos  starting position in the destination data. 目标数组接收拷贝元素的起始位置
     * @param      length   the number of array elements to be copied. 拷贝的元素的数目
     * @exception  IndexOutOfBoundsException  if copying would cause
     *               access of data outside array bounds.
     * @exception  ArrayStoreException  if an element in the <code>src</code>
     *               array could not be stored into the <code>dest</code> array
     *               because of a type mismatch.
     * @exception  NullPointerException if either <code>src</code> or
     *               <code>dest</code> is <code>null</code>.
     */
    public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);
}

Vector

线程安全的容器

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
public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    /**
     * 用了synchronized直接修饰这个方法。除此之外实现逻辑和ArrayList几乎一样。modCount代表的是这个容器的结构变化次数，
     * 就是数组中元素增加了一个，减少了一个，就是结构的变化。这里把modCount放在这里做计算，是一个和ArrayList不一样的地方，ArrayList是在check的时候来做
     * Appends the specified element to the end of this Vector.
     *
     * @param e element to be appended to this Vector
     * @return {@code true} (as specified by {@link Collection#add})
     * @since 1.2
     * 
     */
    public synchronized boolean add(E e) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = e;
        return true;
    }
    /**
     * 也是用sychronized修饰了这个方法，然后先检查是否越界，不越界则返回，但是它没有像ArrayList一样将这个check专门写一个方法
     * Returns the component at the specified index.
     *
     * <p>This method is identical in functionality to the {@link #get(int)}
     * method (which is part of the {@link List} interface).
     *
     * @param      index   an index into this vector
     * @return     the component at the specified index
     * @throws ArrayIndexOutOfBoundsException if the index is out of range
     *         ({@code index < 0 || index >= size()})
     */
    public synchronized E elementAt(int index) {
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
        }

        return elementData(index);
    }
  　/**
     * 根据下标删除元素
     * Removes the element at the specified position in this Vector.
     * Shifts any subsequent elements to the left (subtracts one from their
     * indices).  Returns the element that was removed from the Vector.
     *
     * @throws ArrayIndexOutOfBoundsException if the index is out of range
     *         ({@code index < 0 || index >= size()})
     * @param index the index of the element to be removed
     * @return element that was removed
     * @since 1.2
     */
    public synchronized E remove(int index) {
        modCount++;
        if (index >= elementCount)
            throw new ArrayIndexOutOfBoundsException(index);
        E oldValue = elementData(index);

        int numMoved = elementCount - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--elementCount] = null; // Let gc do its work

        return oldValue;
    }
    /**
     * 删除对象
     * Removes the first (lowest-indexed) occurrence of the argument
     * from this vector. If the object is found in this vector, each
     * component in the vector with an index greater or equal to the
     * object's index is shifted downward to have an index one smaller
     * than the value it had previously.
     *
     * <p>This method is identical in functionality to the
     * {@link #remove(Object)} method (which is part of the
     * {@link List} interface).
     *
     * @param   obj   the component to be removed
     * @return  {@code true} if the argument was a component of this
     *          vector; {@code false} otherwise.
     */
    public synchronized boolean removeElement(Object obj) {
        modCount++;
        int i = indexOf(obj);
        if (i >= 0) {
            removeElementAt(i);
            return true;
        }
        return false;
    }
   　/**
   　* 定位
     * Returns the index of the first occurrence of the specified element in
     * this vector, searching forwards from {@code index}, or returns -1 if
     * the element is not found.
     * More formally, returns the lowest index {@code i} such that
     * <tt>(i&nbsp;&gt;=&nbsp;index&nbsp;&amp;&amp;&nbsp;(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i))))</tt>,
     * or -1 if there is no such index.
     *
     * @param o element to search for
     * @param index index to start searching from
     * @return the index of the first occurrence of the element in
     *         this vector at position {@code index} or later in the vector;
     *         {@code -1} if the element is not found.
     * @throws IndexOutOfBoundsException if the specified index is negative
     * @see     Object#equals(Object)
     */
    public synchronized int indexOf(Object o, int index) {
        if (o == null) {
            for (int i = index ; i < elementCount ; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = index ; i < elementCount ; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }
    /**
     * 删除下标对象
     * Deletes the component at the specified index. Each component in
     * this vector with an index greater or equal to the specified
     * {@code index} is shifted downward to have an index one
     * smaller than the value it had previously. The size of this vector
     * is decreased by {@code 1}.
     *
     * <p>The index must be a value greater than or equal to {@code 0}
     * and less than the current size of the vector.
     *
     * <p>This method is identical in functionality to the {@link #remove(int)}
     * method (which is part of the {@link List} interface).  Note that the
     * {@code remove} method returns the old value that was stored at the
     * specified position.
     *
     * @param      index   the index of the object to remove
     * @throws ArrayIndexOutOfBoundsException if the index is out of range
     *         ({@code index < 0 || index >= size()})
     */
    public synchronized void removeElementAt(int index) {
        modCount++;
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " +
                                                     elementCount);
        }
        else if (index < 0) {
            throw new ArrayIndexOutOfBoundsException(index);
        }
        int j = elementCount - index - 1;
        if (j > 0) {
            System.arraycopy(elementData, index + 1, elementData, index, j);
        }
        elementCount--;
        elementData[elementCount] = null; /* to let gc do its work */
    }
}

实现原理很简单，根据要删除的对象找到它的下标i，然后根据这个下标删除第i个元素即可。除了加上了锁，以及一些代码风格的，与ArrayList没有区别。

循环删除问题

根据ArrayList循环的方式和删除元素的方式，可能会出现各种各样的问题：

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
public static void main(String[] args) {
       List<String> list = new ArrayList<>(Arrays.asList("a", "b1", "c3", "db3", "fca2", "a12cb6", "1a7", "afb8", "aa2"));

       // 正确写法
       for (Iterator<String> ite = list.iterator(); ite.hasNext(); ) {
           String str = ite.next();
           System.out.println(str);
           if (str.contains("c")) {
               ite.remove();
           }
       }

       // 正常删除，不推荐
       for (int i = 0; i < list.size(); i++) {
           String str = list.get(i);
           System.out.println(str);
           if (str.contains("c")) {
               list.remove(i);
           }
       }

       //  报错 java.util.ConcurrentModificationException
       for (String str : list) {
           System.out.println(str);
           if (str.contains("c")) {
               list.remove(str);
           }
       }

       //java.lang.IndexOutOfBoundsExceptionlist
       int size = list.size();
       for (int i = 0; i < size; i++) {
           String str = list.get(i);
           System.out.println(str);
           if (str.contains("c")) {
               list.remove(i);
               //size--;
               //i--;
           }
       }

       // java.util.ConcurrentModificationException
       for (Iterator<String> ite = list.iterator(); ite.hasNext(); ) {
           String str = ite.next();
           if (str.contains("c")) {
               list.remove(str);
           }
       }
   }

ArrayList的内部迭代器

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

    Itr() {}

    public boolean hasNext() {
        return cursor != size;
    }

    @SuppressWarnings("unchecked")
    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];
    }

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

    @Override
    @SuppressWarnings("unchecked")
    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;
        checkForComodification();
    }

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

这个迭代器在里面定义了一个 int expectedModCount = modCount; 

记录当前ArrayList对象修改的次数。而从前面remove方法的分析我们看到，在每次remove方法的调用过程中，modCount这个成员变量是会自增长的，但是remove方法里面并不会更新expectedModCount。而我们可以看待迭代器里的next方法的第一步就是调用方法checkForComodification， 去判断这两个count是否相等，不相等就抛出异常。而在remove元素之后此处的modCount已经比expectedModCount大1了，因此会抛出一个ConcurrentModificationException。

因此在使用Foreach快速遍历时，ArrayList内部创建了一个内部迭代器iterator，使用的是hasNext和next()方法来判断和取下一个元素,就可能会出现ConcurrentModificationException。如何避免这个问题呢？最好的办法就使用内部的这个迭代器进行remove操作。如果多线程操作还是会引发ConcurrentModificationException,解决Vector ConcurrentModificationException 问题,当需要使用迭代器的时候，添加锁，遍历完成后，再释放锁

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
 public static void main(String[] args) {
    Vector vector = new Vector(20);
    vector.add("a");
    vector.add("b");
    vector.add("c");
    
    ReentrantLock reentrantLock = new ReentrantLock();
    new Thread(() -> {
        try {
            if (reentrantLock.tryLock(2000, TimeUnit.SECONDS)) {
                Iterator iterator = vector.listIterator();
                Thread.sleep(1000);
                while (iterator.hasNext()) {
                    System.out.println(iterator.next()); 
                }
            }
        } catch (InterruptedException e) {
            e.printStackTrace();
        } finally {
            reentrantLock.unlock();
        }
    }).start();

    new Thread(() -> {
        try {
            if (reentrantLock.tryLock(2000, TimeUnit.SECONDS)) {
                vector.add("d");
                System.out.println(vector.size());
            }
        } catch (InterruptedException e) {
            e.printStackTrace();
        } finally {
            reentrantLock.unlock();
        }
    }).start();
}

ArrayList和LinkedList有什么区别，它们是怎么扩容的

事实上就是数组和链表作为两种最核心的数据结构的区别

  1. ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构
  2. 对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针
  3. 对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据

LinkedList不存在扩容的问题,其元素节点定义如下：

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

对于ArrayList来说，存在扩容的问题。在添加元素时我们从第一节的代码可以知道它会先确保容量是否足够，如果不够则会扩容，实现方法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* 计算新的空间大小，通过native方法Arrays.copyOf生产新数组。
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
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);
}

LinkedList

双向链表
JDK1.6使用的是一个带有头结点的双向循环链表
JDK1.7开始 LinkedList没有头节点，使用头、尾指针。在链头/尾进行插入/删除操作，first /last方式更加快捷
插入/删除操作按照位置，分为两种情况：中间 和 两头

  • 在中间插入/删除，两者都是一样，先遍历找到index，然后修改链表index处两头的指针。
  • 在两头，对于循环链表来说，由于首尾相连，还是需要处理两头的指针。而非循环链表只需要处理一边first.prev/last.next，所以理论上非循环链表更高效。恰恰两头(链头/链尾) 操作是最普遍的
    LinkedList也是是未同步的，多线程并发读写时需要同步，那么可以使用Collections.synchronizedList方法对LinkedList的实例进行一次封装，也可以改用村concurrent包下面包装类
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
/**
* LinkedList底层是双链表。
* 实现了List接口可以有队列操作
* 实现了Deque接口可以有双端队列操作
* 实现了所有可选的List操作并且允许存储任何元素，包括Null
*
*/
public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;

    /**
     * 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;

    /**
    * 私有静态内部类
    */
    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;
        }
    }

    /**
     * 返回指定位置元素
     * 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;
    }
    /**
     * size>>1 即计算size的一半是多少
     * 判断index是否比size的一半小，若是则从前往后找，若不是则从后往前找
     * 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;
        }
    }
    /**
     * 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
     * Links e as last element.
     */
    void linkLast(E e) {
        /**
	    * 获取当前链表的最后一个节点
	    */
        final Node<E> l = last;
        /**
        * 新建一个e节点，prev链接到l节点
        */
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        /**
        * 空表，首次插入
        */
        if (l == null)
            first = newNode;
        else
            l.next = newNode; //不是首次插入，则最后一个节点的后置节点地址赋值给新节点
        size++;
        modCount++;
    }
    /**
     * 删除第一个匹配的元素
     * null对象是可以存储也可以删除的，并且判断null元素用的是==，而是一般的对象元素则是用的equals方法
     * 
     * Removes the first occurrence of the specified element from this list,
     * if it is present.  If this list does not contain the element, it is
     * unchanged.  More formally, removes the element with the lowest index
     * {@code i} such that
     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
     * (if such an element exists).  Returns {@code true} if this list
     * contained the specified element (or equivalently, if this list
     * changed as a result of the call).
     *
     * @param o element to be removed from this list, if present
     * @return {@code true} if this list contained the specified 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--;
        modCount++;
        return element;
    }

    /**
     * 返回list长度
     * Returns the number of elements in this list.
     *
     * @return the number of elements in this list
     */
    public int size() {
        return size;
    }
}

Arrays.sort的排序方法是什么

JDK1.6以下：调用sort方法时，默认是使用mergeSort算法
JDK1.7后，使用TimSort算法

排序规则实现Comparator接口

Array和ArrayList有何区别？什么时候更适合用Array？

Array可以容纳基本类型和对象，而ArrayList只能容纳对象。
Array没有提供ArrayList那么多功能，比如addAll、removeAll和iterator等。尽管ArrayList明显是更好的选择，但也有些时候Array比较好用：

  • 如果列表的大小已经指定，大部分情况下是存储和遍历它们
  • 对于遍历基本数据类型，尽管Collections使用自动装箱来减轻编码任务，在指定大小的基本类型的列表上工作也会变得很慢
  • 如果你要使用多维数组，使用数组[][]比List方便

超时剔除功能

另启一个线程，判断元素是否超时，如果超时就移除。或者使用有界限循环队列。
BlockingQueue有超时机制

参考