ArrayList, LinkedList, Vector - dudu:史上最详解

ArrayList, LinkedList, Vector - dudu:史上最详解

我们来比较一下ArrayList, LinkedLIst和Vector它们之间的区别。BZ的JDK版本是1.7.0_80

经常在面试的时候,或者在大家做project的时候,都会被它们的区别产生疑惑。或者对它们的用法并不是很了解。那么我们今天就来看看他们的区别和用法。

请尊重作者劳动成果,转发请标明blog地址

https://www.cnblogs.com/hongten/p/hongten_arraylist_linkedlist_vector.html

一.ArrayList,LinkedList和Vector的区别

ArrayList, LinkedList和Vector都实现了List接口,所使用的方法也很相似,主要区别在于实现方法的不同,所有对不同的操作具有不同的效率。

1.ArrayList

ArrayList是一个可以改变大小的,线程不同步(不支持并发)的数组,内部值可以为null。 当更多的元素加入到ArrayList中时,其大小会自动增加,内部元素可以直接通过get/set方法进行访问,因为ArrayList本质上即使一个数组。

因为ArrayList是不支持并发的数组,但是如果我们在使用的过程中需要ArrayList也有同步功能,可以使用Collections.synchronziedList(new ArrayList<E e>())方法实现(在后面我们会讲到)。

2.Vector

之所以把Vector放在这里的原因是因为Vector和ArrayList是否类似,但是它是属于线程同步(支持并发)的数组,并且内部值也可以为null。如果你的程序本身是线程安全的(没有多个线程之间共享同一个集合/对象),那么请使用ArrayList吧。

3.LinkedList

LinkedList底层是基于双链表实现的,在添加和删除元素时具有比ArrayList更好的性能。但是在get/set方面要弱于ArrayList(前提是这些对比是在数据量很大或者操作很繁琐的情况下)。LinkedList内部值可以为null,但是当我们调用值为null的元素的时候会出现NullPointerException。

    LinkedList更适合于以下场景:

    I.没有大量的随机访问操作。

    II.有大量的add/remove操作。

概括起来大概是这个样子:

ArrayList和Vector它们底层实现为数组,值可为null, ArrayList不支持并发,Vector支持并发;

LinkedList底层基于双链表,因此在add/remove元素时比ArrayList要快(注意前提)。

二.详解ArrayList

先来看看ArrayList的源码

  1 public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
  2     private static final long serialVersionUID = 8683452581122892189L;
  3 
  4     //默认数组大小为10
  5     private static final int DEFAULT_CAPACITY = 10;
  6     //空数组对象
  7     private static final Object[] EMPTY_ELEMENTDATA = {};
  8     //ArrayList底层基于该数组实现
  9     private transient Object[] elementData;
 10     //ArrayList中实际数据的大小
 11     private int size;
 12 
 13     //带有初始化容量大小的构造函数
 14     public ArrayList(int initialCapacity) {
 15         super();
 16         if (initialCapacity < 0)
 17             throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
 18         //使数组初始化为指定容量大小
 19         this.elementData = new Object[initialCapacity];
 20     }
 21 
 22     //无参构造函数
 23     public ArrayList() {
 24         super();
 25         //这里是把数组设置为空数组对象
 26         this.elementData = EMPTY_ELEMENTDATA;
 27     }
 28 
 29     //创建一个包含Collection的ArrayList
 30     public ArrayList(Collection<? extends E> c) {
 31         elementData = c.toArray();
 32         size = elementData.length;
 33         if (elementData.getClass() != Object[].class)
 34             elementData = Arrays.copyOf(elementData, size, Object[].class);
 35     }
 36 
 37     //将当期容量值设置为实际元素个数
 38     public void trimToSize() {
 39         modCount++;
 40         if (size < elementData.length) {
 41             elementData = Arrays.copyOf(elementData, size);
 42         }
 43     }
 44 
 45     //确保ArrayList容量,如果    
 46     public void ensureCapacity(int minCapacity) {
 47         int minExpand = (elementData != EMPTY_ELEMENTDATA)
 48                 // any size if real element table
 49                 ? 0
 50                 // larger than default for empty table. It's already supposed to be
 51                 // at default size.
 52                 : DEFAULT_CAPACITY;
 53 
 54         if (minCapacity > minExpand) {
 55             ensureExplicitCapacity(minCapacity);
 56         }
 57     }
 58 
 59     private void ensureCapacityInternal(int minCapacity) {
 60         //初始化时候,elementData是为空数组对象EMPTY_ELEMENTDATA,所以会去设置minCapacity的值
 61         if (elementData == EMPTY_ELEMENTDATA) {
 62             //设置minCapacity值,比较minCapacity和默认容量(DEFAULT_CAPACITY=10)
 63             //把最大值赋值给minCapacity
 64             minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
 65         }
 66         //确定明确的容量大小
 67         ensureExplicitCapacity(minCapacity);
 68     }
 69 
 70     //确定明确的容量大小
 71     private void ensureExplicitCapacity(int minCapacity) {
 72         modCount++;
 73 
 74         // overflow-conscious code
 75         if (minCapacity - elementData.length > 0)
 76             grow(minCapacity);
 77     }
 78 
 79     //最大数组大小=Integer.MAX_VALUE - 8
 80     private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
 81 
 82     //扩容方法
 83     private void grow(int minCapacity) {
 84         // overflow-conscious code
 85         int oldCapacity = elementData.length;
 86         int newCapacity = oldCapacity + (oldCapacity >> 1);
 87         if (newCapacity - minCapacity < 0)
 88             newCapacity = minCapacity;
 89         if (newCapacity - MAX_ARRAY_SIZE > 0)
 90             newCapacity = hugeCapacity(minCapacity);
 91         // minCapacity is usually close to size, so this is a win:
 92         elementData = Arrays.copyOf(elementData, newCapacity);
 93     }
 94 
 95     private static int hugeCapacity(int minCapacity) {
 96         if (minCapacity < 0) // overflow
 97             throw new OutOfMemoryError();
 98         return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
 99     }
100 
101     //获取大小
102     public int size() {
103         return size;
104     }
105 
106     //判断是否为空
107     public boolean isEmpty() {
108         return size == 0;
109     }
110 
111     //是否包含某个元素/对象
112     public boolean contains(Object o) {
113         return indexOf(o) >= 0;
114     }
115 
116     //正向查询,如果找到,则返回对象的索引值
117     public int indexOf(Object o) {
118         if (o == null) {
119             for (int i = 0; i < size; i++)
120                 if (elementData[i] == null)
121                     return i;
122         } else {
123             for (int i = 0; i < size; i++)
124                 if (o.equals(elementData[i]))
125                     return i;
126         }
127         return -1;
128     }
129 
130     //反向查找,如果找到,则返回对象的索引值
131     public int lastIndexOf(Object o) {
132         if (o == null) {
133             for (int i = size - 1; i >= 0; i--)
134                 if (elementData[i] == null)
135                     return i;
136         } else {
137             for (int i = size - 1; i >= 0; i--)
138                 if (o.equals(elementData[i]))
139                     return i;
140         }
141         return -1;
142     }
143 
144     //clone
145     public Object clone() {
146         try {
147             @SuppressWarnings("unchecked")
148             ArrayList<E> v = (ArrayList<E>) super.clone();
149             v.elementData = Arrays.copyOf(elementData, size);
150             v.modCount = 0;
151             return v;
152         } catch (CloneNotSupportedException e) {
153             // this shouldn't happen, since we are Cloneable
154             throw new InternalError();
155         }
156     }
157 
158     @SuppressWarnings("unchecked")
159     E elementData(int index) {
160         return (E) elementData[index];
161     }
162 
163     //根据索引值查询对象
164     public E get(int index) {
165         rangeCheck(index);
166 
167         return elementData(index);
168     }
169 
170     //根据索引值,把element设置为该索引所对应的值
171     public E set(int index, E element) {
172         rangeCheck(index);
173 
174         E oldValue = elementData(index);
175         elementData[index] = element;
176         return oldValue;
177     }
178 
179     //向ArrayList中添加一个元素
180     public boolean add(E e) {
181         ensureCapacityInternal(size + 1); // Increments modCount!!
182         elementData[size++] = e;
183         return true;
184     }
185 
186     //根据指定的索引值添加对象
187     public void add(int index, E element) {
188         rangeCheckForAdd(index);
189 
190         ensureCapacityInternal(size + 1); // Increments modCount!!
191         System.arraycopy(elementData, index, elementData, index + 1, size - index);
192         elementData[index] = element;
193         size++;
194     }
195 
196     //删除指定索引值所在的对象,并返回所删除的对象
197     public E remove(int index) {
198         rangeCheck(index);
199 
200         modCount++;
201         E oldValue = elementData(index);
202 
203         int numMoved = size - index - 1;
204         if (numMoved > 0)
205             //所有对象向前移动
206             System.arraycopy(elementData, index + 1, elementData, index, numMoved);
207         //把数组最后一个元素置空,以便java虚拟机回收
208         elementData[--size] = null; // clear to let GC do its work
209 
210         return oldValue;
211     }
212 
213     //删除对象,并返回是否删除成功
214     public boolean remove(Object o) {
215         if (o == null) {
216             for (int index = 0; index < size; index++)
217                 if (elementData[index] == null) {
218                     fastRemove(index);
219                     return true;
220                 }
221         } else {
222             for (int index = 0; index < size; index++)
223                 if (o.equals(elementData[index])) {
224                     fastRemove(index);
225                     return true;
226                 }
227         }
228         return false;
229     }
230 
231     //直接删除掉索引指向的元素
232     private void fastRemove(int index) {
233         modCount++;
234         int numMoved = size - index - 1;
235         if (numMoved > 0)
236             //所有对象向前移动
237             System.arraycopy(elementData, index + 1, elementData, index, numMoved);
238         //把数组最后一个元素置空,以便java虚拟机回收
239         elementData[--size] = null; // clear to let GC do its work
240     }
241 
242     //把数组置空
243     public void clear() {
244         modCount++;
245 
246         // clear to let GC do its work
247         for (int i = 0; i < size; i++)
248             elementData[i] = null;
249 
250         size = 0;
251     }
252 
253     //添加包含Collection的元素对象
254     public boolean addAll(Collection<? extends E> c) {
255         Object[] a = c.toArray();
256         int numNew = a.length;
257         ensureCapacityInternal(size + numNew); // Increments modCount
258         System.arraycopy(a, 0, elementData, size, numNew);
259         size += numNew;
260         return numNew != 0;
261     }
262 
263     //在所给定的索引上,添加包含Collection的元素对象
264     public boolean addAll(int index, Collection<? extends E> c) {
265         rangeCheckForAdd(index);
266 
267         Object[] a = c.toArray();
268         int numNew = a.length;
269         ensureCapacityInternal(size + numNew); // Increments modCount
270 
271         int numMoved = size - index;
272         if (numMoved > 0)
273             System.arraycopy(elementData, index, elementData, index + numNew, numMoved);
274 
275         System.arraycopy(a, 0, elementData, index, numNew);
276         size += numNew;
277         return numNew != 0;
278     }
279 
280     //删除某一个区域对象
281     protected void removeRange(int fromIndex, int toIndex) {
282         modCount++;
283         int numMoved = size - toIndex;
284         System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved);
285 
286         // clear to let GC do its work
287         int newSize = size - (toIndex - fromIndex);
288         for (int i = newSize; i < size; i++) {
289             elementData[i] = null;
290         }
291         size = newSize;
292     }
293 
294     //如果索引值超过了数组大小,抛出IndexOutOfBoundsException异常
295     private void rangeCheck(int index) {
296         if (index >= size)
297             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
298     }
299 
300     //添加元素时,检查索引大小,如果索引值大于容量(size)大小或小于0,则抛出IndexOutOfBoundsException异常
301     private void rangeCheckForAdd(int index) {
302         if (index > size || index < 0)
303             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
304     }
305 
306     //用于迭代ArrayList
307     public ListIterator<E> listIterator() {
308         return new ListItr(0);
309     }
310 }

我们可以看到ArrayList继承了AbstractList,并且实现了List, RandomAccess, Cloneable, Serializable接口,ArrayList是一个可变大小的数组。它提供了很多方法:size, isEmpty, get, set, listIterator,add,addAll等等。

我们来分析一下下面的代码:

1 List<String> arrList = new ArrayList<String>();
2 System.out.println(arrList.size());//输出:0
3 arrList.add("hongten");
4 System.out.println(arrList.size());//输出:1

当我们创建一个ArrayList的时候,其数组大小(size)是为0,即一个空数组。当我们往数组里面添加一个元素‘hongten’后,其数组大小变为1.

这和我们之前的JDK1.5有一点区别(默认情况下,数组大小为10)。

我们new ArrayList()的时候,调用的是ArrayList的无参构造函数:

ArrayList无参构造函数

JDK1.7里面ArrayList无参构造函数,默认情况下,数组为一个空数组。

1     //无参构造函数
2     public ArrayList() {
3         super();//因为继承了AbstractList,所以调用AbstractList的构造函数
4         //这里是把数组设置为空数组对象
5         this.elementData = EMPTY_ELEMENTDATA;
6     }

JDK1.5里面ArrayList无参构造函数,默认情况下,数组大小为10.(由于本文针对JDK1.7.0_80,所以以JDK1.7为准)

1 //无参构造函数
2 public ArrayList() {
3     this(10);
4 }

到这里ArrayList数据时一个空数组。其size为0.

add()方法

调用add()方法,我们看一下add方法源码:

1     //向ArrayList中添加一个元素
2     public boolean add(E e) {
3         ensureCapacityInternal(size + 1); // Increments modCount!!
4         elementData[size++] = e;
5         return true;
6     }

首先我们把参数‘hongten’传递给add()方法,该方法做了两件事情:1.检查数组大小,看看是否需要扩容。2.把对象加入到数组里面,然后返回。

这里的size我们知道是为1的。那么size+1=0+1=1作为参数传递给ensureCapacityInternal()方法。

ensureCapacityInternal()方法

我们来看看ensureCapacityInternal()方法:

 1   //默认数组大小为10
 2     private static final int DEFAULT_CAPACITY = 10;
 3         
 4     private void ensureCapacityInternal(int minCapacity) {
 5         //初始化时候,elementData是为空数组对象EMPTY_ELEMENTDATA,所以会去设置minCapacity的值
 6         if (elementData == EMPTY_ELEMENTDATA) {
 7             //设置minCapacity值,比较minCapacity和默认容量(DEFAULT_CAPACITY=10)
 8             //把最大值赋值给minCapacity
 9             minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
10         }
11         //确定明确的容量大小
12         ensureExplicitCapacity(minCapacity);
13     }

 原来在这个方法里面用到了DEFAULT_CAPACITY=10,所以,最后的minCapacity=10,并且作为参数传递给了ensureExplicitCapacity()方法。

ensureExplicitCapacity()方法

我们接着来看看ensureExplicitCapacity()方法:

1     //确定明确的容量大小
2     private void ensureExplicitCapacity(int minCapacity) {
3         modCount++;
4 
5         // overflow-conscious code
6         if (minCapacity - elementData.length > 0)
7             grow(minCapacity);
8     }

modCount是继承自AbstractList的,主要用于Iterator()和listIterator()方法。接下来是判断minCapacity和elementData.length的大小,由于minCapacity=10,elementData现在还是空数组,所以elementData.length=0,所以是if(true)的情况。需要执行grow()方法。

grow()方法

那么grow()方法是什么样的呢?

 1     //最大数组大小=Integer.MAX_VALUE - 8
 2     private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
 3 
 4     //扩容方法
 5     private void grow(int minCapacity) {
 6         //此时因为elementData为空数组,那么oldCapacity=0
 7         int oldCapacity = elementData.length;
 8         //newCapacity = 0 + (0 >> 1) = 0 + 0 = 0
 9         int newCapacity = oldCapacity + (oldCapacity >> 1);
10         //0-10=-10<0 --> true
11         if (newCapacity - minCapacity < 0)
12             //newCapacity=10
13             newCapacity = minCapacity;
14         //10-MAX_ARRAY_SIZE = -Integer.MAX_VALUE+18<0 --> false
15         if (newCapacity - MAX_ARRAY_SIZE > 0)
16             newCapacity = hugeCapacity(minCapacity);
17         //现在才初始化数组
18         elementData = Arrays.copyOf(elementData, newCapacity);
19     }

我们发现JDK1.7.0_80和JDK1.5的区别在于此。他们初始化数组的时间不同。

JDK1.5在创建ArrayList的时候就初始化了数组,然而,JDK1.7是在这里开始初始化数组。

Arrays.copyOf()方法

那么接下来的Arrays.copyOf()方法就值得我们去研究了:

 1   public static <T> T[] copyOf(T[] original, int newLength) {
 2         //elementData此时还是空数组,newLength=10,original.getClass()-->为elementData数组类对象Object[]
 3         return (T[]) copyOf(original, newLength, original.getClass());
 4     }
 5     
 6     public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
 7         //因为newType = Object[].class -->true
 8         //所以copy= new Object[10];
 9         T[] copy = ((Object)newType == (Object)Object[].class)
10             ? (T[]) new Object[newLength]
11             : (T[]) Array.newInstance(newType.getComponentType(), newLength);
12         //original为空数组, copy是长度为10的数组
13         //将指定源数组中的数组从指定位置复制到目标数组的指定位置
14         System.arraycopy(original, 0, copy, 0,
15                          Math.min(original.length, newLength));
16         return copy;
17     }

copyOf()方法返回一个长度为10的数组,然后赋值给elementData,完成ArrayList里面数组的初始化工作。

这就完成了add()方法里面的第一步操作。

第二步操作是:

数组size++,然后把参数加入到数组里面,然后返回,完成往ArrayList里面添加元素的操作。

 那么这个时候的size也就是我们看到的输出结果1.

remove()方法

再来看看ArrayList里面的remove()删除操作  

 1     //删除指定索引值所在的对象,并返回所删除的对象
 2     public E remove(int index) {
 3         //先检查传入的索引是否合法
 4         rangeCheck(index);
 5 
 6         modCount++;
 7         //获取到指引所在对应的数组对象
 8         E oldValue = elementData(index);
 9 
10         int numMoved = size - index - 1;
11         if (numMoved > 0)
12             //所有对象向前移动
13             System.arraycopy(elementData, index + 1, elementData, index, numMoved);
14         //把数组最后一个元素置空,以便java虚拟机回收
15         elementData[--size] = null; // clear to let GC do its work
16 
17         return oldValue;
18     }

在进行删除操作的时候,需要把指引所指向的对象删除掉,并且把该对象以后的元素向前移动,最后返回被删除的元素。

三.详解Vector

 先来看看Vector的源码

  1 public class Vector<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
  2 
  3     //Vector和ArrayList一样,底层基于该数组实现
  4     protected Object[] elementData;
  5     //这个相当于ArrayList里面的size
  6     protected int elementCount;
  7     //当Vector的大小大于其容量时,Vector的容量自动增加的量。 
  8     protected int capacityIncrement;
  9 
 10     //带容量和容量自动增加量的参数的构造函数
 11     public Vector(int initialCapacity, int capacityIncrement) {
 12         super();
 13         if (initialCapacity < 0)
 14             throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
 15         this.elementData = new Object[initialCapacity];
 16         this.capacityIncrement = capacityIncrement;
 17     }
 18 
 19     //给定容量的构造函数
 20     public Vector(int initialCapacity) {
 21         this(initialCapacity, 0);
 22     }
 23 
 24     //无参构造函数
 25     public Vector() {
 26         //初始化数组,大小为10
 27         this(10);
 28     }
 29 
 30     //包含Collection对象的构造函数
 31     public Vector(Collection<? extends E> c) {
 32         elementData = c.toArray();
 33         elementCount = elementData.length;
 34         // c.toArray might (incorrectly) not return Object[] (see 6260652)
 35         if (elementData.getClass() != Object[].class)
 36             elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
 37     }
 38 
 39     //将当期容量值设置为实际元素个数
 40     public synchronized void trimToSize() {
 41         modCount++;
 42         int oldCapacity = elementData.length;
 43         if (elementCount < oldCapacity) {
 44             elementData = Arrays.copyOf(elementData, elementCount);
 45         }
 46     }
 47 
 48     //
 49     public synchronized void ensureCapacity(int minCapacity) {
 50         if (minCapacity > 0) {
 51             modCount++;
 52             ensureCapacityHelper(minCapacity);
 53         }
 54     }
 55 
 56     //维护数组大小
 57     private void ensureCapacityHelper(int minCapacity) {
 58         // overflow-conscious code
 59         if (minCapacity - elementData.length > 0)
 60             //数组扩容
 61             grow(minCapacity);
 62     }
 63 
 64     //数组最大size
 65     private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
 66 
 67     //数组扩容
 68     private void grow(int minCapacity) {
 69         // overflow-conscious code
 70         int oldCapacity = elementData.length;
 71         int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);
 72         if (newCapacity - minCapacity < 0)
 73             newCapacity = minCapacity;
 74         if (newCapacity - MAX_ARRAY_SIZE > 0)
 75             newCapacity = hugeCapacity(minCapacity);
 76         elementData = Arrays.copyOf(elementData, newCapacity);
 77     }
 78 
 79     private static int hugeCapacity(int minCapacity) {
 80         if (minCapacity < 0) // overflow
 81             throw new OutOfMemoryError();
 82         return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
 83     }
 84 
 85     //设置数组大小
 86     public synchronized void setSize(int newSize) {
 87         modCount++;
 88         if (newSize > elementCount) {
 89             ensureCapacityHelper(newSize);
 90         } else {
 91             for (int i = newSize; i < elementCount; i++) {
 92                 elementData[i] = null;
 93             }
 94         }
 95         elementCount = newSize;
 96     }
 97 
 98     //获取数组长度
 99     public synchronized int capacity() {
100         return elementData.length;
101     }
102 
103     //获取大小
104     public synchronized int size() {
105         return elementCount;
106     }
107 
108     //判断是否为空
109     public synchronized boolean isEmpty() {
110         return elementCount == 0;
111     }
112 
113     //是否包含某个元素/对象
114     public boolean contains(Object o) {
115         return indexOf(o, 0) >= 0;
116     }
117 
118     //正向查询,如果找到,则返回对象的索引值
119     public int indexOf(Object o) {
120         return indexOf(o, 0);
121     }
122 
123     //正向查询,如果找到,则返回对象的索引值
124     public synchronized int indexOf(Object o, int index) {
125         if (o == null) {
126             for (int i = index; i < elementCount; i++)
127                 if (elementData[i] == null)
128                     return i;
129         } else {
130             for (int i = index; i < elementCount; i++)
131                 if (o.equals(elementData[i]))
132                     return i;
133         }
134         return -1;
135     }
136 
137     //反向查询,如果找到,则返回对象的索引值
138     public synchronized int lastIndexOf(Object o) {
139         return lastIndexOf(o, elementCount - 1);
140     }
141 
142     //反向查询,如果找到,则返回对象的索引值
143     public synchronized int lastIndexOf(Object o, int index) {
144         if (index >= elementCount)
145             throw new IndexOutOfBoundsException(index + " >= " + elementCount);
146 
147         if (o == null) {
148             for (int i = index; i >= 0; i--)
149                 if (elementData[i] == null)
150                     return i;
151         } else {
152             for (int i = index; i >= 0; i--)
153                 if (o.equals(elementData[i]))
154                     return i;
155         }
156         return -1;
157     }
158 
159     //根据索引移除对象
160     public synchronized void removeElementAt(int index) {
161         modCount++;
162         if (index >= elementCount) {
163             throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
164         } else if (index < 0) {
165             throw new ArrayIndexOutOfBoundsException(index);
166         }
167         int j = elementCount - index - 1;
168         if (j > 0) {
169             System.arraycopy(elementData, index + 1, elementData, index, j);
170         }
171         elementCount--;
172         elementData[elementCount] = null; /* to let gc do its work */
173     }
174 
175     //在给定的索引里插入对象
176     public synchronized void insertElementAt(E obj, int index) {
177         modCount++;
178         if (index > elementCount) {
179             throw new ArrayIndexOutOfBoundsException(index + " > " + elementCount);
180         }
181         ensureCapacityHelper(elementCount + 1);
182         System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
183         elementData[index] = obj;
184         elementCount++;
185     }
186 
187     //添加元素
188     public synchronized void addElement(E obj) {
189         modCount++;
190         ensureCapacityHelper(elementCount + 1);
191         elementData[elementCount++] = obj;
192     }
193 
194     //直接删除掉索引指向的元素
195     public synchronized boolean removeElement(Object obj) {
196         modCount++;
197         int i = indexOf(obj);
198         if (i >= 0) {
199             removeElementAt(i);
200             return true;
201         }
202         return false;
203     }
204 
205     //移除所有元素
206     public synchronized void removeAllElements() {
207         modCount++;
208         // Let gc do its work
209         for (int i = 0; i < elementCount; i++)
210             elementData[i] = null;
211 
212         elementCount = 0;
213     }
214 
215     @SuppressWarnings("unchecked")
216     E elementData(int index) {
217         return (E) elementData[index];
218     }
219 
220     //根据索引值查询对象
221     public synchronized E get(int index) {
222         if (index >= elementCount)
223             throw new ArrayIndexOutOfBoundsException(index);
224 
225         return elementData(index);
226     }
227 
228     //根据索引值,把element设置为该索引所对应的值
229     public synchronized E set(int index, E element) {
230         if (index >= elementCount)
231             throw new ArrayIndexOutOfBoundsException(index);
232 
233         E oldValue = elementData(index);
234         elementData[index] = element;
235         return oldValue;
236     }
237 
238     //向Vector中添加一个元素
239     public synchronized boolean add(E e) {
240         modCount++;//继承自AbstactList
241         //维护数组大小
242         ensureCapacityHelper(elementCount + 1);
243         //把元素加入到数组中,数组大小加1.
244         elementData[elementCount++] = e;
245         return true;
246     }
247 
248     //删除对象,并返回是否删除成功
249     public boolean remove(Object o) {
250         return removeElement(o);
251     }
252 
253     //根据指定的索引值添加对象
254     public void add(int index, E element) {
255         insertElementAt(element, index);
256     }
257 
258     //删除指定索引值所在的对象,并返回所删除的对象
259     public synchronized E remove(int index) {
260         modCount++;
261         if (index >= elementCount)
262             throw new ArrayIndexOutOfBoundsException(index);
263         E oldValue = elementData(index);
264 
265         int numMoved = elementCount - index - 1;
266         if (numMoved > 0)
267             //所有对象向前移动
268             System.arraycopy(elementData, index + 1, elementData, index, numMoved);
269         //把数组最后一个元素置空,以便java虚拟机回收
270         elementData[--elementCount] = null; // Let gc do its work
271 
272         return oldValue;
273     }
274 
275     //把数组置空
276     public void clear() {
277         removeAllElements();
278     }
279 
280     // Bulk Operations
281 
282     //添加包含Collection的元素对象
283     public synchronized boolean containsAll(Collection<?> c) {
284         return super.containsAll(c);
285     }
286 
287     //添加包含Collection的元素对象
288     public synchronized boolean addAll(Collection<? extends E> c) {
289         modCount++;
290         Object[] a = c.toArray();
291         int numNew = a.length;
292         ensureCapacityHelper(elementCount + numNew);
293         System.arraycopy(a, 0, elementData, elementCount, numNew);
294         elementCount += numNew;
295         return numNew != 0;
296     }
297 
298     //获取子list对象
299     public synchronized List<E> subList(int fromIndex, int toIndex) {
300         return Collections.synchronizedList(super.subList(fromIndex, toIndex), this);
301     }
302 
303     //删除某一个区域对象
304     protected synchronized void removeRange(int fromIndex, int toIndex) {
305         modCount++;
306         int numMoved = elementCount - toIndex;
307         System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved);
308 
309         // Let gc do its work
310         int newElementCount = elementCount - (toIndex - fromIndex);
311         while (elementCount != newElementCount)
312             elementData[--elementCount] = null;
313     }
314 
315     //用于迭代Vector
316     public synchronized ListIterator<E> listIterator() {
317         return new ListItr(0);
318     }
319 
320     //用于迭代Vector
321     public synchronized Iterator<E> iterator() {
322         return new Itr();
323     }
324 }

我们可以看到Vector和ArrayList是否类似,Vector是一个可变大小的数组。它提供了很多方法:size,isEmpty, get, set, listIterator,add,addAll等等。

和ArrayList相比,不同之处在于Vector的很多方法都加了关键字synchronized,使得Vector具有了同步功能,支持并发。

我们来分析一下下面的代码:

当我们创建一个Vector的时候,其数组长度为10的数组,但是因为里面没有任何元素,所以我们看到第一次输出为0。当我们往数组里面添加一个元素‘hongten’后,其数组含有的元素个数变为1.

1        List<String> myVactor = new Vector<String>();
2         System.out.println(myVactor.size());//输出:0
3         myVactor.add("hongten");
4         System.out.println(myVactor.size());//输出:1

Vector构造函数

来看看Vector的构造函数:

 1     //Vector和ArrayList一样,底层基于该数组实现
 2     protected Object[] elementData;
 3     //这个相当于ArrayList里面的size
 4     protected int elementCount;
 5     //当Vector的大小大于其容量时,Vector的容量自动增加的量。 
 6     protected int capacityIncrement;
 7 
 8     //带容量和容量自动增加量的参数的构造函数
 9     public Vector(int initialCapacity, int capacityIncrement) {
10         super();
11         if (initialCapacity < 0)
12             throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
13         //初始化数组
14         this.elementData = new Object[initialCapacity];
15         this.capacityIncrement = capacityIncrement;
16     }
17 
18     //给定容量的构造函数
19     public Vector(int initialCapacity) {
20         this(initialCapacity, 0);
21     }
22 
23     //无参构造函数
24     public Vector() {
25         //初始化数组,大小为10
26         this(10);
27     }

我们可以看到,当我们new Vector()的时候,vector里面的数组就已经被初始化了,并且数组的长度为10.

add()方法

接下来调用add()方法:

1     //向Vector中添加一个元素
2     public synchronized boolean add(E e) {
3         modCount++;//继承自AbstactList
4         //维护数组大小
5         ensureCapacityHelper(elementCount + 1);
6         //把元素加入到数组中,数组大小加1.
7         elementData[elementCount++] = e;
8         return true;
9     }

add方法是向Vector里面添加一个元素,并且使用了关键字synchronized,支持并发。和ArrayList类似,1.维护数组大小。2.把元素添加到数组中,然后返回

ensureCapacityHelper()方法

调用ensureCapacityHelper()方法:

1     //维护数组大小
2     private void ensureCapacityHelper(int minCapacity) {
3         //minCapacity - elementData.length = 1 - 10 = -9 < 0 --> false
4         if (minCapacity - elementData.length > 0)
5             //数组扩容
6             grow(minCapacity);
7     }

可以看到这里,在默认情况下,添加一条记录进入到vector的时候,数组并不需要扩容。到这里,add方法的第一步完成。

接下来第二步:把元素添加到数组中,数组大小加1.并返回,完成添加元素操作。

grow()方法

当我们往vector数组里面一直加入数据,把默认的第10个数据都加满的时候,那么这个时候就需要调用grow()方法了

 1     //数组最大size
 2     private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
 3 
 4     //数组扩容
 5     private void grow(int minCapacity) {
 6         //此时的minCapacity值为11
 7         //oldCapacity= 10
 8         int oldCapacity = elementData.length;
 9         //因为此时capacityIncrement是为0的
10         //所以(capacityIncrement > 0) ? capacityIncrement : oldCapacity = (0>0)?0:10=0
11         //newCapacity=10+(0)=10
12         int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);
13         //10-11=-1<0 --> true
14         if (newCapacity - minCapacity < 0)
15             //newCapacity = 11
16             newCapacity = minCapacity;
17         if (newCapacity - MAX_ARRAY_SIZE > 0)
18             newCapacity = hugeCapacity(minCapacity);
19         elementData = Arrays.copyOf(elementData, newCapacity);
20     }
21 
22     private static int hugeCapacity(int minCapacity) {
23         if (minCapacity < 0) // overflow
24             throw new OutOfMemoryError();
25         return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
26     }

 remove()方法

remove()方法和Arraylist里面的方法差不多,区别在于多了关键字synchronized。

 1     //删除指定索引值所在的对象,并返回所删除的对象
 2     public synchronized E remove(int index) {
 3         modCount++;
 4         if (index >= elementCount)
 5             throw new ArrayIndexOutOfBoundsException(index);
 6         E oldValue = elementData(index);
 7 
 8         int numMoved = elementCount - index - 1;
 9         if (numMoved > 0)
10             //所有对象向前移动
11             System.arraycopy(elementData, index + 1, elementData, index, numMoved);
12         //把数组最后一个元素置空,以便java虚拟机回收
13         elementData[--elementCount] = null; // Let gc do its work
14 
15         return oldValue;
16     }

四.详解LinkedList

 先来看看LinkedList的源码

  1 public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
  2     transient int size = 0;
  3 
  4     //第一个元素的引用
  5     transient Node<E> first;
  6 
  7     //最后一个元素的引用
  8     transient Node<E> last;
  9 
 10     //无参构造函数
 11     public LinkedList() {
 12     }
 13 
 14     //包含一个Collection的构造函数
 15     public LinkedList(Collection<? extends E> c) {
 16         this();
 17         addAll(c);
 18     }
 19 
 20     //在链表头部创建链接
 21     private void linkFirst(E e) {
 22         final Node<E> f = first;
 23         final Node<E> newNode = new Node<>(null, e, f);
 24         first = newNode;
 25         if (f == null)
 26             last = newNode;
 27         else
 28             f.prev = newNode;
 29         size++;
 30         modCount++;
 31     }
 32 
 33     //在链表尾部创建链接
 34     void linkLast(E e) {
 35         final Node<E> l = last;
 36         final Node<E> newNode = new Node<>(l, e, null);
 37         last = newNode;
 38         if (l == null)
 39             first = newNode;
 40         else
 41             l.next = newNode;
 42         size++;
 43         modCount++;
 44     }
 45 
 46     /**
 47      * Inserts element e before non-null Node succ.
 48      */
 49     void linkBefore(E e, Node<E> succ) {
 50         // assert succ != null;
 51         final Node<E> pred = succ.prev;
 52         final Node<E> newNode = new Node<>(pred, e, succ);
 53         succ.prev = newNode;
 54         if (pred == null)
 55             first = newNode;
 56         else
 57             pred.next = newNode;
 58         size++;
 59         modCount++;
 60     }
 61 
 62     //删除链表中第一个链接
 63     private E unlinkFirst(Node<E> f) {
 64         // assert f == first && f != null;
 65         final E element = f.item;
 66         final Node<E> next = f.next;
 67         f.item = null;
 68         f.next = null; // help GC
 69         first = next;
 70         if (next == null)
 71             last = null;
 72         else
 73             next.prev = null;
 74         size--;
 75         modCount++;
 76         return element;
 77     }
 78 
 79     //删除链表中最后一个链接
 80     private E unlinkLast(Node<E> l) {
 81         // assert l == last && l != null;
 82         final E element = l.item;
 83         final Node<E> prev = l.prev;
 84         l.item = null;
 85         l.prev = null; // help GC
 86         last = prev;
 87         if (prev == null)
 88             first = null;
 89         else
 90             prev.next = null;
 91         size--;
 92         modCount++;
 93         return element;
 94     }
 95 
 96     //删除链表给定的元素链接
 97     E unlink(Node<E> x) {
 98         // assert x != null;
 99         final E element = x.item;
100         final Node<E> next = x.next;
101         final Node<E> prev = x.prev;
102 
103         if (prev == null) {
104             first = next;
105         } else {
106             prev.next = next;
107             x.prev = null;
108         }
109 
110         if (next == null) {
111             last = prev;
112         } else {
113             next.prev = prev;
114             x.next = null;
115         }
116 
117         x.item = null;
118         size--;
119         modCount++;
120         return element;
121     }
122 
123     //获取头部元素
124     public E getFirst() {
125         final Node<E> f = first;
126         if (f == null)
127             throw new NoSuchElementException();
128         return f.item;
129     }
130 
131     //获取尾部元素
132     public E getLast() {
133         final Node<E> l = last;
134         if (l == null)
135             throw new NoSuchElementException();
136         return l.item;
137     }
138 
139     //移除头部元素
140     public E removeFirst() {
141         final Node<E> f = first;
142         if (f == null)
143             throw new NoSuchElementException();
144         return unlinkFirst(f);
145     }
146 
147     //移除尾部元素
148     public E removeLast() {
149         final Node<E> l = last;
150         if (l == null)
151             throw new NoSuchElementException();
152         return unlinkLast(l);
153     }
154 
155     //添加一个元素在链表头部
156     public void addFirst(E e) {
157         linkFirst(e);
158     }
159 
160     //添加一个元素到链表尾部
161     public void addLast(E e) {
162         linkLast(e);
163     }
164 
165     //判断是否包含某个元素
166     public boolean contains(Object o) {
167         return indexOf(o) != -1;
168     }
169 
170     //获取链表大小
171     public int size() {
172         return size;
173     }
174 
175     //添加元素
176     public boolean add(E e) {
177         //把该元素放到链表最后面
178         linkLast(e);
179         return true;
180     }
181 
182     //移除链表中一个给定的元素对象
183     public boolean remove(Object o) {
184         if (o == null) {
185             for (Node<E> x = first; x != null; x = x.next) {
186                 if (x.item == null) {
187                     unlink(x);
188                     return true;
189                 }
190             }
191         } else {
192             for (Node<E> x = first; x != null; x = x.next) {
193                 if (o.equals(x.item)) {
194                     unlink(x);
195                     return true;
196                 }
197             }
198         }
199         return false;
200     }
201 
202     //添加一个包含Collection的元素
203     public boolean addAll(Collection<? extends E> c) {
204         return addAll(size, c);
205     }
206 
207     //在给定的索引下面添加一个包含Collection的元素
208     public boolean addAll(int index, Collection<? extends E> c) {
209         checkPositionIndex(index);
210 
211         Object[] a = c.toArray();
212         int numNew = a.length;
213         if (numNew == 0)
214             return false;
215 
216         Node<E> pred, succ;
217         if (index == size) {
218             succ = null;
219             pred = last;
220         } else {
221             succ = node(index);
222             pred = succ.prev;
223         }
224 
225         for (Object o : a) {
226             @SuppressWarnings("unchecked")
227             E e = (E) o;
228             Node<E> newNode = new Node<>(pred, e, null);
229             if (pred == null)
230                 first = newNode;
231             else
232                 pred.next = newNode;
233             pred = newNode;
234         }
235 
236         if (succ == null) {
237             last = pred;
238         } else {
239             pred.next = succ;
240             succ.prev = pred;
241         }
242 
243         size += numNew;
244         modCount++;
245         return true;
246     }
247 
248     //清除链表
249     public void clear() {
250         for (Node<E> x = first; x != null;) {
251             Node<E> next = x.next;
252             x.item = null;
253             x.next = null;
254             x.prev = null;
255             x = next;
256         }
257         first = last = null;
258         size = 0;
259         modCount++;
260     }
261 
262     // Positional Access Operations
263 
264     //根据索引获取元素
265     public E get(int index) {
266         checkElementIndex(index);
267         return node(index).item;
268     }
269 
270     //根据索引设置索引所指向的对象的值
271     public E set(int index, E element) {
272         checkElementIndex(index);
273         Node<E> x = node(index);
274         E oldVal = x.item;
275         x.item = element;
276         return oldVal;
277     }
278 
279     //根据索引添加元素
280     public void add(int index, E element) {
281         checkPositionIndex(index);
282 
283         if (index == size)
284             linkLast(element);
285         else
286             linkBefore(element, node(index));
287     }
288 
289     //根据索引移除元素
290     public E remove(int index) {
291         checkElementIndex(index);
292         return unlink(node(index));
293     }
294 
295     //判断所给索引是否合法
296     private boolean isElementIndex(int index) {
297         return index >= 0 && index < size;
298     }
299 
300     //判断所给索引是否为第一个/最后一个
301     private boolean isPositionIndex(int index) {
302         return index >= 0 && index <= size;
303     }
304 
305     private void checkElementIndex(int index) {
306         if (!isElementIndex(index))
307             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
308     }
309 
310     private void checkPositionIndex(int index) {
311         if (!isPositionIndex(index))
312             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
313     }
314 
315     Node<E> node(int index) {
316         if (index < (size >> 1)) {
317             Node<E> x = first;
318             for (int i = 0; i < index; i++)
319                 x = x.next;
320             return x;
321         } else {
322             Node<E> x = last;
323             for (int i = size - 1; i > index; i--)
324                 x = x.prev;
325             return x;
326         }
327     }
328 
329     public E poll() {
330         final Node<E> f = first;
331         return (f == null) ? null : unlinkFirst(f);
332     }
333 
334     //Queue里面offer()方法
335     public boolean offer(E e) {
336         return add(e);
337     }
338 
339     //Deque里面offerFirst()方法
340     public boolean offerFirst(E e) {
341         addFirst(e);
342         return true;
343     }
344 
345     //Deque里面offerLast()方法
346     public boolean offerLast(E e) {
347         addLast(e);
348         return true;
349     }
350 
351     public ListIterator<E> listIterator(int index) {
352         checkPositionIndex(index);
353         return new ListItr(index);
354     }
355 
356     private static class Node<E> {
357         E item;
358         Node<E> next;
359         Node<E> prev;
360 
361         Node(Node<E> prev, E element, Node<E> next) {
362             this.item = element;
363             this.next = next;
364             this.prev = prev;
365         }
366     }
367 }

我们可以看到LinkedList继承了AbstractSequentialList,并且实现了List, Deque, Cloneable, Serializable接口,LinkedList底层是基于链表实现的。

所以我们必须去了解一下链表的数据结构。

在LinkedList里面定义了一个私有静态内部类Node,可以看到Node有三个成员变量,item, next, prev.从字面上理解为本身, 下一个元素,前一个元素。

 1 private static class Node<E> {
 2         //本身
 3         E item;
 4         //下一个元素
 5         Node<E> next;
 6         //前一个元素
 7         Node<E> prev;
 8 
 9         Node(Node<E> prev, E element, Node<E> next) {
10             this.item = element;
11             this.next = next;
12             this.prev = prev;
13         }
14     }

add()方法

来看看add()方法,该方法是直接把元素放到链表尾部,然后返回。

1     //添加元素
2     public boolean add(E e) {
3         //把该元素放到链表最后面
4         linkLast(e);
5         return true;
6     }

linkLast()方法

把对象加入到链表的尾部,然后链表大小+1

 1     // 第一个元素的引用
 2     transient Node<E> first;
 3 
 4     // 最后一个元素的引用
 5     transient Node<E> last;
 6         
 7     //在链表尾部创建链接
 8     void linkLast(E e) {
 9         //获取最后一个元素
10         final Node<E> l = last;
11         //创建一个一个Node对象,参数(前,本,后)
12         //前:指向链表最后一个元素,即新加入的元素的上一个元素
13         //本:指的就是新加入元素本身
14         //后:因为新加入的元素本身就是在链表最后面加入,所以,后面没有元素,则为null
15         final Node<E> newNode = new Node<>(l, e, null);
16         //把last引用指向新创建的对象上面
17         last = newNode;
18         //如果在链表为空的情况下,first=last=null
19         if (l == null)
20             //那么第一个就是最新创建的元素
21             first = newNode;
22         else
23             //把链表最后元素的next指向创建的新元素的引用
24             l.next = newNode;
25         //链表大小+1
26         size++;
27         modCount++;
28     }

remove()方法

根据索引移除对象,首先要判断索引是否合法,如果合法,则移除索引所指对象。

1     //根据索引移除元素
2     public E remove(int index) {
3         checkElementIndex(index);
4         return unlink(node(index));
5     }

unlink()方法

unlink()方法的目的就是把即将被删除的元素从链表里面拿出来,并且维护好链表状态。

 1     //删除链表给定的元素链接
 2     E unlink(Node<E> x) {
 3         //该元素本身
 4         final E element = x.item;
 5         //该元素下一个元素
 6         final Node<E> next = x.next;
 7         //该元素上一个元素
 8         final Node<E> prev = x.prev;
 9 
10         //如果该元素本身就是第一个元素,即链表头部
11         if (prev == null) {
12             //那么就把first指向下一个元素引用
13             first = next;
14         } else {
15             //把前一个元素的next指向该元素的下一个元素,即跳过该元素
16             //因为该元素马上要被删除掉了
17             prev.next = next;
18             //把该元素前一个元素引用置空
19             x.prev = null;
20         }
21 
22         //如果该元素本身就是最后一个元素,即链表尾部
23         if (next == null) {
24             //那么把last指向前一个元素引用
25             last = prev;
26         } else {
27             //把下一个元素的prev指向该元素的上一个元素,也是跳过该元素(即将被删)
28             next.prev = prev;
29             //把该元素下一个元素引用置空
30             x.next = null;
31         }
32 
33         //把该元素本身置空
34         x.item = null;
35         //链表大小-1
36         size--;
37         modCount++;
38         //返回该元素
39         return element;
40     }

五.在并发情况下,怎样使用它们

 类部类MyThread继承了Thread类,并且重写了run()方法。在MyThread里面定义了4个static变量,这些变量是为了存放线程在运行过程中向里面添加元素的值。

  1 package com.b510.test;
  2 
  3 import java.util.ArrayList;
  4 import java.util.Collections;
  5 import java.util.LinkedList;
  6 import java.util.List;
  7 import java.util.Vector;
  8 import java.util.concurrent.ExecutorService;
  9 import java.util.concurrent.Executors;
 10 import java.util.concurrent.TimeUnit;
 11 
 12 /**
 13  * @author Hongwei
 14  * @created 28 Aug 2018
 15  */
 16 public class MyListTest {
 17 
 18     public static void main(String[] args) throws Exception {
 19         // 创建线程池
 20         ExecutorService exec = Executors.newCachedThreadPool();
 21         exec.execute(new MyThread());
 22         exec.execute(new MyThread());
 23         exec.execute(new MyThread());
 24         exec.execute(new MyThread());
 25         exec.execute(new MyThread());
 26         exec.execute(new MyThread());
 27         exec.execute(new MyThread());
 28         exec.execute(new MyThread());
 29         exec.execute(new MyThread());
 30 
 31         System.out.println("begin...");
 32         TimeUnit.SECONDS.sleep(2);
 33         exec.shutdownNow();
 34 
 35         List<Integer> myArrayList = MyThread.myArrayList;
 36         List<Integer> myLinkedList = MyThread.myLinkedList;
 37         List<Integer> myVector = MyThread.myVector;
 38         List<Integer> mySynchronziedArrayList = MyThread.mySynchronziedArrayList;
 39         if (myArrayList != null && myArrayList.size() > 0) {
 40             System.out.println("ArrayList: " + myArrayList);
 41         }
 42         if (myVector != null && myVector.size() > 0) {
 43             System.out.println("vector: " + myVector);
 44         }
 45         if (mySynchronziedArrayList != null && mySynchronziedArrayList.size() > 0) {
 46             System.out.println("SynchronziedArrayList: " + mySynchronziedArrayList);
 47         }
 48         if (myLinkedList != null && myLinkedList.size() > 0) {
 49             System.out.println("linkedList: " + myLinkedList);
 50         }
 51 
 52         System.out.println("end...");
 53 
 54     }
 55 }
 56 
 57 class MyThread extends Thread {
 58 
 59     //arrayList,不支持并发
 60     static List<Integer> myArrayList = new ArrayList<Integer>();
 61     //linkedList
 62     static List<Integer> myLinkedList = new LinkedList<Integer>();
 63     //Vector,线程安全,支持并发
 64     static List<Integer> myVector = new Vector<Integer>();
 65     //Connections.synchonizedList,线程安全,支持并发
 66     static List<Integer> mySynchronziedArrayList = Collections.synchronizedList(new ArrayList<Integer>());
 67 
 68     public void run() {
 69         for (int i = 0; i < 10; i++) {
 70             try {
 71                 TimeUnit.MILLISECONDS.sleep(2);
 72                 System.out.println(Thread.currentThread().getName() + " add value " + i);
 73                 myArrayList.add(i);
 74                 myVector.add(i);
 75                 mySynchronziedArrayList.add(i);
 76                 myLinkedList.add(i);
 77 
 78             } catch (InterruptedException e) {
 79                 e.printStackTrace();
 80             }
 81         }
 82     }
 83 }
 84 /*
 85 output:
 86     begin...
 87     pool-1-thread-1 add value 0
 88     pool-1-thread-3 add value 0
 89     pool-1-thread-8 add value 0
 90     pool-1-thread-4 add value 0
 91     pool-1-thread-7 add value 0
 92     pool-1-thread-6 add value 0
 93     pool-1-thread-2 add value 0
 94     pool-1-thread-5 add value 0
 95     pool-1-thread-9 add value 0
 96     pool-1-thread-5 add value 1
 97     pool-1-thread-4 add value 1
 98     pool-1-thread-6 add value 1
 99     pool-1-thread-8 add value 1
100     pool-1-thread-2 add value 1
101     pool-1-thread-3 add value 1
102     pool-1-thread-7 add value 1
103     pool-1-thread-1 add value 1
104     pool-1-thread-9 add value 1
105     pool-1-thread-7 add value 2
106     pool-1-thread-3 add value 2
107     pool-1-thread-5 add value 2
108     pool-1-thread-2 add value 2
109     pool-1-thread-8 add value 2
110     pool-1-thread-6 add value 2
111     pool-1-thread-4 add value 2
112     pool-1-thread-1 add value 2
113     pool-1-thread-9 add value 2
114     pool-1-thread-8 add value 3
115     pool-1-thread-1 add value 3
116     pool-1-thread-2 add value 3
117     pool-1-thread-3 add value 3
118     pool-1-thread-7 add value 3
119     pool-1-thread-5 add value 3
120     pool-1-thread-4 add value 3
121     pool-1-thread-6 add value 3
122     pool-1-thread-9 add value 3
123     pool-1-thread-3 add value 4
124     pool-1-thread-7 add value 4
125     pool-1-thread-4 add value 4
126     pool-1-thread-8 add value 4
127     pool-1-thread-2 add value 4
128     pool-1-thread-6 add value 4
129     pool-1-thread-1 add value 4
130     pool-1-thread-5 add value 4
131     pool-1-thread-9 add value 4
132     pool-1-thread-1 add value 5
133     pool-1-thread-6 add value 5
134     pool-1-thread-2 add value 5
135     pool-1-thread-3 add value 5
136     pool-1-thread-7 add value 5
137     pool-1-thread-5 add value 5
138     pool-1-thread-8 add value 5
139     pool-1-thread-4 add value 5
140     pool-1-thread-9 add value 5
141     pool-1-thread-8 add value 6
142     pool-1-thread-5 add value 6
143     pool-1-thread-6 add value 6
144     pool-1-thread-1 add value 6
145     pool-1-thread-2 add value 6
146     pool-1-thread-3 add value 6
147     pool-1-thread-7 add value 6
148     pool-1-thread-4 add value 6
149     pool-1-thread-9 add value 6
150     pool-1-thread-8 add value 7
151     pool-1-thread-3 add value 7
152     pool-1-thread-1 add value 7
153     pool-1-thread-6 add value 7
154     pool-1-thread-7 add value 7
155     pool-1-thread-2 add value 7
156     pool-1-thread-4 add value 7
157     pool-1-thread-5 add value 7
158     pool-1-thread-9 add value 7
159     pool-1-thread-1 add value 8
160     pool-1-thread-6 add value 8
161     pool-1-thread-3 add value 8
162     pool-1-thread-7 add value 8
163     pool-1-thread-2 add value 8
164     pool-1-thread-5 add value 8
165     pool-1-thread-8 add value 8
166     pool-1-thread-4 add value 8
167     pool-1-thread-9 add value 8
168     pool-1-thread-1 add value 9
169     pool-1-thread-4 add value 9
170     pool-1-thread-7 add value 9
171     pool-1-thread-3 add value 9
172     pool-1-thread-2 add value 9
173     pool-1-thread-8 add value 9
174     pool-1-thread-6 add value 9
175     pool-1-thread-5 add value 9
176     pool-1-thread-9 add value 9
177     ArrayList: [null, null, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9]
178     vector: [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9]
179     SynchronziedArrayList: [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9]
180     Exception in thread "main" java.lang.NullPointerException
181         at java.util.LinkedList$ListItr.next(LinkedList.java:891)
182         at java.util.AbstractCollection.toString(AbstractCollection.java:457)
183         at java.lang.String.valueOf(String.java:2849)
184         at java.lang.StringBuilder.append(StringBuilder.java:128)
185         at com.b510.test.MyListTest.main(MyListTest.java:49)
186 */

之后我们从结果可以看到:

ArrayList:值可以为null,线程不安全,但是我们可以使用Collections.synchronzedList()方法使得一个ArrayList支持并发。

Vector:本身支持并发。

LinkedList:值可以为null,但是当我们调用时会抛出NullPointerException异常。

========================================================

More reading,and english is important.

I'm Hongte

E | hongtenzone@foxmail.com  B | http://www.cnblogs.com/hongten

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Android知识点总结

Java容器源码攻坚战--第二战:ArrayList

1802
来自专栏架构之路

Java 集合系列03之 ArrayList详细介绍(源码解析)和使用示例

概要 上一章,我们学习了Collection的架构。这一章开始,我们对Collection的具体实现类进行讲解;首先,讲解List,而List中ArrayLis...

2924
来自专栏微信公众号:Java团长

Java集合源码剖析——ArrayList源码剖析

ArrayList是基于数组实现的,是一个动态数组,其容量能自动增长,类似于C语言中的动态申请内存,动态增长内存。

1122
来自专栏拭心的安卓进阶之路

Java 集合深入理解(12):古老的 Vector

今天刮台风,躲屋里看看 Vector ! 都说 Vector 是线程安全的 ArrayList,今天来根据源码看看是不是这么相...

2897
来自专栏专注 Java 基础分享

从源码解析TreeMap

     上篇文章我们介绍了HashMap集合,这是一个键值对集合,可以高效的按照键查找数值。但是它有一个缺陷:数据如果是无序的可以是很高效的,但是如果数据...

2108
来自专栏用户2442861的专栏

List、Set、Map、数组之间各种转换

刚学Java不久的时候,接到一个电面,然后问了一些java的知识,比如说Java的编码,Unicode等,但是最让我蛋疼的是怎么吗map转为set,那个时候对...

3312
来自专栏好好学java的技术栈

“365算法每日学计划”:06打卡-单向循环链表

单向循环链表是单链表的另一种形式,其结构特点是链表中最后一个结点的指针不再是结束标记,而是指向整个链表的第一个结点,从而使单链表形成一个环。

701
来自专栏JavaEdge

二叉树的常用算法递归2 非递归3 小结4 实战coding5序列化和反序列化判断一棵二叉树是否是平衡二叉树判断一棵树是否是搜索二叉树、判断一棵树是否是完全二叉树

5749
来自专栏积累沉淀

JDK源码分析-ArrayList分析

花了两个晚上的时间研究了一下ArrayList的源码, ArrayList 继承自AbstractList 并且实现了List, RandomAccess,...

1815
来自专栏nnngu

数据结构07 二叉树

这篇文章开始总结 树和二叉树。 什么是树呢? 1、树的定义 (1)有且仅有一个特定的称为根(root) 的节点。 (2)当 n>1 时,其余节点可分为 m(m>...

3524

扫码关注云+社区

领取腾讯云代金券