java集合----List

发表于 | 更新于: | 阅读次数:

一.List

java 中的 List 是一种类似于列表的集合，Java集合—-Map说过 Map 接口的实现类是不保证添加顺序的(LinkedHashMap 除外) ,但是对于 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
public interface List<E> extends Collection<E> {
    // Query Operations
    //询问操作
    int size();
    boolean isEmpty();
    boolean contains(Object o);
    Iterator<E> iterator();
    Object[] toArray();
    <T> T[] toArray(T[] a);
    
    // Modification Operations
    //修改操作
    boolean add(E e);
    boolean remove(Object o);


    // Bulk Modification Operations
    //大量修改的操作
    boolean containsAll(Collection<?> c);
    boolean addAll(Collection<? extends E> c);
    boolean addAll(int index, Collection<? extends E> c);
    boolean removeAll(Collection<?> c);
    boolean retainAll(Collection<?> c);
    default void replaceAll(UnaryOperator<E> operator) {
        Objects.requireNonNull(operator);
        final ListIterator<E> li = this.listIterator();
        while (li.hasNext()) {
            li.set(operator.apply(li.next()));
        }
    }
    /**
     *Java 8 开始支持排序操作
     * @since 1.8
     */
    @SuppressWarnings({"unchecked", "rawtypes"})
    default void sort(Comparator<? super E> c) {
        Object[] a = this.toArray();
        Arrays.sort(a, (Comparator) c);
        ListIterator<E> i = this.listIterator();
        for (Object e : a) {
            i.next();
            i.set((E) e);
        }
    }
    void clear();
    
    // Comparison and hashing
    //比较和 hash 操作
    boolean equals(Object o);
    int hashCode();
    
    
    // Positional Access Operations
    //基于位置的访问
    E get(int index);
    E set(int index, E element);
    void add(int index, E element);
    E remove(int index);
    
    
    // Search Operations
    //返回位置的操作
    int indexOf(Object o);
    int lastIndexOf(Object o);

    // List Iterators
    //迭代器，用于遍历列表
    ListIterator<E> listIterator();
    ListIterator<E> listIterator(int index);

    // View
    //list 的子视图，也就是子列表
    List<E> subList(int fromIndex, int toIndex);
     /*
     * @return a {@code Spliterator} over the elements in this list
     * @since 1.8
     */
    @Override
    default Spliterator<E> spliterator() {
        if (this instanceof RandomAccess) {
            return new AbstractList.RandomAccessSpliterator<>(this);
        } else {
            return Spliterators.spliterator(this, Spliterator.ORDERED);
        }
    }
    /**
     * Java 9 扩展的返回不可变的list 列表
     * @since 9
     */
    static <E> List<E> of() {
        return ImmutableCollections.List0.instance();
    }
    static <E> List<E> of(E e1) {
        return new ImmutableCollections.List1<>(e1);
    }
    static <E> List<E> of(E e1, E e2) {
        return new ImmutableCollections.List2<>(e1, e2);
    }
    static <E> List<E> of(E e1, E e2, E e3) {
        return new ImmutableCollections.ListN<>(e1, e2, e3);
    }
    static <E> List<E> of(E e1, E e2, E e3, E e4) {
        return new ImmutableCollections.ListN<>(e1, e2, e3, e4);
    }
    static <E> List<E> of(E e1, E e2, E e3, E e4, E e5) {
        return new ImmutableCollections.ListN<>(e1, e2, e3, e4, e5);
    }
    static <E> List<E> of(E e1, E e2, E e3, E e4, E e5, E e6) {
        return new ImmutableCollections.ListN<>(e1, e2, e3, e4, e5,
                                                e6);
    }
    static <E> List<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E e7) {
        return new ImmutableCollections.ListN<>(e1, e2, e3, e4, e5,
                                                e6, e7);
    }
   
    static <E> List<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8) {
        return new ImmutableCollections.ListN<>(e1, e2, e3, e4, e5,
                                                e6, e7, e8);
    }
    static <E> List<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9) {
        return new ImmutableCollections.ListN<>(e1, e2, e3, e4, e5,
                                                e6, e7, e8, e9);
    }
    static <E> List<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9, E e10) {
        return new ImmutableCollections.ListN<>(e1, e2, e3, e4, e5,
                                                e6, e7, e8, e9, e10);
    }
    @SafeVarargs
    @SuppressWarnings("varargs")
    static <E> List<E> of(E... elements) {
        switch (elements.length) { // implicit null check of elements
            case 0:
                return ImmutableCollections.List0.instance();
            case 1:
                return new ImmutableCollections.List1<>(elements[0]);
            case 2:
                return new ImmutableCollections.List2<>(elements[0], elements[1]);
            default:
                return new ImmutableCollections.ListN<>(elements);
        }
    }
    /**
      *Java 新增的复制集合方法，如果是不可变的集合，就直接返回，如果是可变的集*合就复制并返回一个不可变得集合。
     * @since 10
     */
    @SuppressWarnings("unchecked")
    static <E> List<E> copyOf(Collection<? extends E> coll) {
        if (coll instanceof ImmutableCollections.AbstractImmutableList) {
            return (List<E>)coll;
        } else {
            return (List<E>)List.of(coll.toArray());
        }
    }
}

二.ArrayList

1.继承关系

首先看一下 ArrayList 的继承关系

1
2
3
4
5
6
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{}
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {}

public abstract class AbstractCollection<E> implements Collection<E> {}

与 Map 相似，ArrayList 也会继承一个抽象类 AbstractList 而这个抽象类有继承自 AbstractCollection ，这两个抽象类的主要作用就是将一些通用的方法进行复用，对于具体的实现可能就会进行重写从而实现自己的特性。

除此之外，还看到 RandomAccess 这个接口

1
2
3
4
5
6
7
8
9
10
11
12
 * for typical instances of the class, this loop:
 * <pre>
 *     for (int i=0, n=list.size(); i &lt; n; i++)
 *         list.get(i);
 * </pre>
 * runs faster than this loop:
 * <pre>
 *     for (Iterator i=list.iterator(); i.hasNext(); )
 *         i.next();
 * </pre>
public interface RandomAccess {
}

这是一个 标记接口，在这个接口中的说明中有一段话 this loop: … runs faster than this loop: (如上)，这段话的意思就是说对于 实现这个接口的类来说，使用 for 循环进行遍历要比使用迭代器快得多，比如在 Collections 的查巡操作中会根据书数组还是迭代器进行选择

1
2
3
4
5
6
7
8
9
10
@SuppressWarnings("unchecked")
  public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c) {
      if (c==null)
          return binarySearch((List<? extends Comparable<? super T>>) list, key);

      if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
          return Collections.indexedBinarySearch(list, key, c);
      else
          return Collections.iteratorBinarySearch(list, key, c);
  }

至于 ArrayList 为什么要实现这个接口？ 实际上就是因为 ArrayList 的内部实现是通过数组实现的。

标记接口就是标记实现这个接口的类具有某种特性。

2.数组

1
transient Object[] elementData; // non-private to simplify nested class access

ArrayList 从名字就可以猜出这是一个基于数组的集合，内部有一个用于存储元素的集合 elementData，这里使用 transient 进行修饰，就说明这个数组不进行序列化，但是 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

   /**
    * The size of the ArrayList (the number of elements it contains).
    *
    * @serial
    */
   private int size; //说明这是数组元素的个数，不是数组的长度
   
   //重写 writeObject 
private void writeObject(java.io.ObjectOutputStream s)
       throws java.io.IOException {
       // Write out element count, and any hidden stuff
       int expectedModCount = modCount;
       s.defaultWriteObject();

       // Write out size as capacity for behavioral compatibility with clone()
       s.writeInt(size); 

       // Write out all elements in the proper order.
       for (int i=0; i<size; i++) { // 这是根据集合的元素个数，而不是数组的长度
           s.writeObject(elementData[i]);
       }

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

ArrayList 并没有去序列化整个数组，而是对数组中的元素逐个进行序列化，这样做就减少空元素的序列化，加快序列化的速度。

3.add

1
2
3
4
5
6
7
8
9
10
11
12
13
 public boolean add(E e) {
        modCount++;
        add(e, elementData, size);
        return true;
    }
    
    
private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length) //判断是否达到数组的长度
            elementData = grow(); // 如果是就进行扩容
        elementData[s] = e; //如果还没有就直接对数组进行赋值
        size = s + 1;  // 将集合元素加一
    }

对于 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
   /**
     * Default initial capacity.
     * 数组默认初始化个数 为 10 个
     */
    private static final int DEFAULT_CAPACITY = 10;
    
    //数组的极限值，-8 是因为一些 虚拟机会在在数组添加一些 头信息
    //-8 进行容错，但是最后还是最大还是创建 Integer.MAX_VALUE  。
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    
private Object[] grow() {
        return grow(size + 1);
    }

 private Object[] grow(int minCapacity) {
        System.out.println(newCapacity(minCapacity));
        return elementData = Arrays.copyOf(elementData,
                newCapacity(minCapacity));
    }
// 扩容的具体操作
private int newCapacity(int minCapacity) {
        // overflow-conscious code
        //原来的容量
        int oldCapacity = elementData.length;
        //计算新的容量
        //新的容量 = 原来的容量 + （原来的容量的一半）
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        
        //如果计算的新的容量比指定的扩容容量小，那么就使用指定的容量
        //通常比指定的小是因为 使用 addAll 添加元素
        if (newCapacity - minCapacity <= 0) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return minCapacity;
        }
        
        //如果新的容量大于MAX_ARRAY_SIZE(Integer.MAX_VALUE - 8)
        //那么就使用 hugeCapacity 进行容量分配
        //否则就是用计算出来的新容量
        return (newCapacity - MAX_ARRAY_SIZE <= 0)
                ? newCapacity
                : hugeCapacity(minCapacity);
    }

private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE)
                ? Integer.MAX_VALUE
                : MAX_ARRAY_SIZE;
    }

最后的扩容就是调用 Arrays.copyOf 进行数组的复制。

3.remove

对于 ArrayList 的各种移除操作，最后都会调用下面两种方法之一。

1
2
3
4
5
6
7
8
9
10
11
12
13
private void fastRemove(Object[] es, int i) {
        modCount++;
        final int newSize;
        if ((newSize = size - 1) > i)
            System.arraycopy(es, i + 1, es, i, newSize - i);
        es[size = newSize] = null;
    }
    
     private void shiftTailOverGap(Object[] es, int lo, int hi) {
        System.arraycopy(es, hi, es, lo, size - hi);
        for (int to = size, i = (size -= hi - lo); i < to; i++)
            es[i] = null;
    }

简单地说还是对数组进行复制，然后再将空出的位置置为 null ，等待 GC 回收。

4.subList

1
2
3
4
public List<E> subList(int fromIndex, int toIndex) {
       subListRangeCheck(fromIndex, toIndex, size);
       return new SubList<>(this, fromIndex, toIndex);
   }

subList 返回的是 ArrayList 的一个子视图，也就是子集合，实际的是 ArrayList 的一个内部类 SubList，虽然 SubList 也实现了 AbstractList 接口但是 SubList 并不是 ArrayList 的子类，== 和 instanceOf 会返回 false 。

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
private static class SubList<E> extends AbstractList<E> implements RandomAccess {
       private final ArrayList<E> root;
       private final SubList<E> parent;
       private final int offset;
       private int size;
    ...
}
/**
        * Constructs a sublist of an arbitrary ArrayList.
        */
       public SubList(ArrayList<E> root, int fromIndex, int toIndex) {
           this.root = root;
           this.parent = null;
           this.offset = fromIndex;
           this.size = toIndex - fromIndex;
           this.modCount = root.modCount;
       }

       /**
        * Constructs a sublist of another SubList.
        */
       private SubList(SubList<E> parent, int fromIndex, int toIndex) {
           this.root = parent.root;
           this.parent = parent;
           this.offset = parent.offset + fromIndex;
           this.size = toIndex - fromIndex;
           this.modCount = root.modCount;
       }
 public E set(int index, E element) {
           Objects.checkIndex(index, size);
           checkForComodification(); 
           E oldValue = root.elementData(offset + index);
           root.elementData[offset + index] = element;
           return oldValue;
       }

       public E get(int index) {
           Objects.checkIndex(index, size);
           checkForComodification();
           return root.elementData(offset + index);
       }

       public int size() {
           checkForComodification();
           return size;
       }

       public void add(int index, E element) {
           rangeCheckForAdd(index);
           checkForComodification();
           root.add(offset + index, element);
           updateSizeAndModCount(1);
       }

       public E remove(int index) {
           Objects.checkIndex(index, size);
           checkForComodification();
           E result = root.remove(offset + index);
           updateSizeAndModCount(-1);
           return result;
       }

       protected void removeRange(int fromIndex, int toIndex) {
           checkForComodification();
           root.removeRange(offset + fromIndex, offset + toIndex);
           updateSizeAndModCount(fromIndex - toIndex);
       }

SubList 里并没有数组变量但是有一个root b变量 root 变量就是原本的集合，而且从两个构造器可以看出 SubList 也可以产生它 的 SubList 。而且 对于 SubList 的各种修改操作也都是调用 root 却修改原生的 集合，换句话说也就是对 SubList 的修改也会影响到原声的 ArrayList .

删除指定范围的元素就可以使用 list.subList(from,to).clear();

特别注意的是这进行这些方法的时候都回调用这个 checkForComodification 方法进行检查 .

1
2
3
4
private void checkForComodification() {
          if (root.modCount != modCount)
              throw new ConcurrentModificationException();
      }

这个方法表示的是 如果 ArrayList 的 modCount 和 SubList 的 modCount 不一样的时候就会抛出异常，也就是说，在生成了 SubList 后，如果再对 ArrayList 进行修改则其 modCount 就会发生变化，这个时候如果又对 SubList 进行操作就会异常。

简单地说就是再生成 SubList 后，如果对 ArrayList 操作了，则不能对已生成的 SubList进行操作。

Array.asList
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
public static <T> List<T> asList(T... a) {
       return new ArrayList<>(a);
   }

   /**
    * @serial include
    */
   private static class ArrayList<E> extends AbstractList<E>
       implements RandomAccess, java.io.Serializable
   {
       private static final long serialVersionUID = -2764017481108945198L;
       private final E[] a;

       ArrayList(E[] array) {
         
       }

       @Override
       public int size() {
     
       }

       @Override
       public Object[] toArray() {
       }

       @Override
       @SuppressWarnings("unchecked")
       public <T> T[] toArray(T[] a) {
        
       }
       @Override
       public E get(int index) {
      
       }

       @Override
       public E set(int index, E element) {
        
       }

       @Override
       public int indexOf(Object o) {
          
       }

       @Override
       public boolean contains(Object o) {
          
       }

       @Override
       public Spliterator<E> spliterator() {
          
       }

       @Override
       public void forEach(Consumer<? super E> action) {
          
       }

       @Override
       public void replaceAll(UnaryOperator<E> operator) {
          
       }

       @Override
       public void sort(Comparator<? super E> c) {
         
       }

       @Override
       public Iterator<E> iterator() {
           return new ArrayItr<>(a);
       }
   }

Arrays 有一个 asList 的返回一个 ArrayList ,从上面的源码可以看出，这个实际上也是 Arrays 的一个内部类，而且这个不是现在通常说的 ArrayList ,因此两个类也没 有继承关系，但是这个内部类可以转为 ArrayList 因为 ArrayList 的 构造器参数是 Collection<? extends E> c 而且这个内部类并没有包含 ArrayList 的所有方法，比如就没有 add 方法，不具备扩展和缩小。

对于数组 Array和 ArrayList 的区别 可以包含基本类型和对象类型，ArrayList 只能包含对象类型；Array 的大小是固定的，ArrayList 的大小是动态变化的；ArrayList 提供了更多的方法和特性， addAll()、removeAll()、iterator() 等。

5.equals

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean equals(Object o) {
        if (o == this)
            return true;
        if (!(o instanceof List))
            return false;

        ListIterator<E> e1 = listIterator();
        ListIterator<?> e2 = ((List<?>) o).listIterator();
        while (e1.hasNext() && e2.hasNext()) {
            E o1 = e1.next();
            Object o2 = e2.next();
            if (!(o1==null ? o2==null : o1.equals(o2)))
                return false;
        }
        return !(e1.hasNext() || e2.hasNext());
    }

对于 ArrayList 的equals 比较，最后还是比较其中的元素数量和每个元素对应时候符合 equals 。显然对于 ArrayList 和 SubList (这里取全部元素)，就符合 equals 返回 true 。

6.线程安全

ArrayList 是不是线程安全的，一个方法是用 Collections.synchronizedList 方法把 ArrayList 变成一个线程安全的，另一个方法就是 Vector，它是ArrayList的线程安全版本，区别在于：Vector 可以指定增长因子，如果该增长因子指定了，那么扩容的时候会每次新的数组大小会在原数组的大小基础上加上增长因子；如果不指定增长因子，那么就给原数组大小*2。

ArrayList适用于查找但是不适用于增加和删除，因为内部的操作都是调用 System.arrayCopy 这种效率很低的方法进行处理，所以如果遇到了数据量略大且需要频繁插入或删除的操作效率就比较低了。

三.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
24
25
26
27
28
29
public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;

    /**
     * Pointer to first node.
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     */
    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;
        }
    }

LinkedList 的继承关系也很简单 AbstractSequentialList 用于保持有序性，除此之外还实现了 Deque ，表明这个一个 双向的链表，支持 Deque 的一些操作。对于每一个 Node 节点，包含了对上一个节点和下一个节点的引用。对于整个 LinkedList 持有头节点和尾节点的引用 。

1.基本操作

由于 LinkedList 是以链表形式存在，因此内部定义了许多对节点的基本操作

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

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

   /**
    * Inserts element e before non-null Node succ.
    * 在一个节点之前插入一个节点
    */
   void linkBefore(E e, Node<E> succ) {
       // assert succ != null;
       final Node<E> pred = succ.prev;
       final Node<E> newNode = new Node<>(pred, e, succ);
       succ.prev = newNode;
       if (pred == null)
           first = newNode;
       else
           pred.next = newNode;
       size++;
       modCount++;
   }

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

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

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

   /**
    * Returns the first element in this list.
    *
    * @return the first element in this list
    * @throws NoSuchElementException if this list is empty
    * 返回第一个头节点
    */
   public E getFirst() {
       final Node<E> f = first;
       if (f == null)
           throw new NoSuchElementException();
       return f.item;
   }

   /**
    * Returns the last element in this list.
    *
    * @return the last element in this list
    * @throws NoSuchElementException if this list is empty
    * 返回尾节点
    */
   public E getLast() {
       final Node<E> l = last;
       if (l == null)
           throw new NoSuchElementException();
       return l.item;
   }

基本上所有的增加删除都是基于上面这几个操作完成。

2.查询

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

对于 LinkedList 的查巡遍历并不是从前往后进行的，而是进行判断，如果下标小于长度的一半就从头节点开始，否则就从尾节点开始。
访问的复杂度为 O(N/2)）只有在链表两头的操作（比如 add()、addFirst()、removeLast() 或用在 iterator() 上的 remove() 操作）才不需要进行遍历寻找定位。

四.对比

  • 当插入的元素比较靠后的时候，ArrayList 效率低，因为 ArrayList 将批量 copy 大量的元素。
  • ArrayList 使用最普通的 for 循环遍历，数组元素之间没有关联，而迭代器强制将 RandomAccess 的 ArrayList 建立了前后遍历关系，且在每次遍历过程中进行了一堆判断，所以比较慢。 LinkedList 使用 foreach 循环比较快，前后元素是通过链表索引建立关联的，无法直接取到对应的下标，因此在使用普通的 index 索引下标遍历时就需要计算对应的元素在哪，二分法决定头部还是尾部遍历，然后一步步的遍历找到元素，所以在遍历中每次都要从头查找元素位置，十分低效率。而迭代器的实现就是指向下一个元素，迭代器直接通过 LinkedList 的指针进行遍历，一次遍历就能找到每个合适的元素。
  • ArrayList 是动态数组顺序表，顺序表的存储地址是连续的，所以查找比较快，但是插入和删除时由于需要把其它的元素顺序移动，所以比较耗时。LinkedList 是双向链表的数据结构，同时实现了双端队列 Deque 接口，链表节点的存储地址是不连续的，每个存储地址通过指针关联，在查找时需要进行指针遍历节点，所以查找比较慢，而在插入和删除时比较快。

五.CopyOnWriteArrayList

CopyOnWriteArrayList 是 java 并发包中 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
//锁对象
final transient Object lock = new Object();

//数组的实现 用 volatile 修饰
private transient volatile Object[] array;


final Object[] getArray() {
    return array;
}

final void setArray(Object[] a) {
    array = a;
}


// 先看添加元素的方法
public E set(int index, E element) {
// 先锁住
    synchronized (lock) {
        Object[] elements = getArray();
        E oldValue = elementAt(elements, index);

        if (oldValue != element) {
            int len = elements.length;
            //复制一个新的数组，长度在原来的基础上加一
            Object[] newElements = Arrays.copyOf(elements, len);
            newElements[index] = element;
            //将原来的引用指向新的数组。
            setArray(newElements);
        } else {
            // Not quite a no-op; ensures volatile write semantics
            setArray(elements);
        }
        return oldValue;
    }
}
//下面也是同样的原理
public boolean add(E e) {
// 先锁住
    synchronized (lock) {
    // 获取旧的数组
        Object[] elements = getArray();
        int len = elements.length;
        //复制新的数组，长度加一
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        //将元素放到最后
        newElements[len] = e;
        //改变旧的引用
        setArray(newElements);
        return true;
    }
}

从上面的实现中可以看出，CopyOnWriteArrayList 在添加元素的时候，通过加锁的方式来实现保证线程的安全，对每次添加一个元素，就是通过复制一个新的数组，然后将旧的引用指向新的数组。这就是一种写时复制的思想，因为写的时候是通过复制实现的，那么这个时候读也是没有问题的。

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
    * {@inheritDoc}
    *
    * @throws IndexOutOfBoundsException {@inheritDoc}
    */
   public E get(int index) {
       return elementAt(getArray(), index);
   }
   
    @SuppressWarnings("unchecked")
   static <E> E elementAt(Object[] a, int index) {
       return (E) a[index];
   }

对于读，这里并没有加锁，而是直接读取。因此对 CopyOnWriteArrayList 的并发读写可以分为三种情况：

  • 1·如果写操作未完成，那么直接读取原数组的数据；
  • 2·如果写操作完成，但是引用还未指向新数组，那么也是读取原数组数据；
  • 3·如果写操作完成，并且引用已经指向了新的数组，那么直接从新数组中读取数据。

这种情况下，CopyOnWriteArrayList 不能保证写一个数据后马上对读可见，但是它保证了 CopyOnWriteArrayList 最后的数据都是一致的，因为添加是加锁的。由于 CopyOnWriteArrayList 的复制机制，因此性能在数据多或者数据较大的时候都会比较低，通过这种空间的解决了读写分离。

Related Issues not found

Please contact @yishengma to initialize the comment

0%