ArrayList是一个底层使用数组来存储对象，但不是线程安全的集合类

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

ArrayList实现了List接口，List接口中定义了一些对列表通过下标进行添加删除等方法

ArrayList实现了RandomAccess接口，这个接口是一个标记接口，接口中并没有任何的方法，ArrayList底层是用数组来存储对象，当然是能够通过下标随机访问的，实现了RandomAccess接口的类在查询时的速度会很快但是添加删除元素慢，而LinkedList是通过链表的方式实现的，它没有实现RandomAccess接口，在查询时慢但是增加删除的速度快

所以在使用集合遍历大量数据时，可以先用instanceof来判断集合是不是实现了RandomAccess

  1. public void test1() {
  2. 		List<Integer> list=new ArrayList<Integer>();
  3. 		list.add(1);
  4. 		if(list instanceof RandomAccess) {//RandomAccess实现类，使用下标访问
  5. 			for(int i=0;i<list.size();i++) {
  6. 				//todo
  7. 			}
  8. 		}else {//不是RandomAccess实现类，使用iterator遍历
  9. 			Iterator<Integer> iterator = list.iterator();
  10. 			while(iterator.hasNext()) {
  11. 				//todo
  12. 			}
  13. 		}
  14. 	}

ArrayList实现了Cloneable接口,所以可以合法调用clone方法，如果没有实现Cloneable接口，那么会抛出CloneNotSupporteddException，详见

ArrayList实现了Serializable接口，可以将对象序列化，用于传输或持久化，详见

  1. //序列化Id
  2. private static final long serialVersionUID = 8683452581122892189L;
  4. //默认初始化大小
  5. private static final int DEFAULT_CAPACITY = 10;
  7. //空数组对象，用于有参构造且初始化大小为0时
  8. private static final Object[] EMPTY_ELEMENTDATA = {};
  10. //空数组对象，用于无参构造时，这两个属性主要用来区分创建ArrayList时有没有指定容量
  11. private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
  13. //保存对象的容器，使用transient修饰即在序列化时，不进行序列化，这是因为ArrayList添加了序列化方法private void writeObject(java.io.ObjectOutputStream s)只把保存的数据序列化了，而不是把整个数组序列化，提高效率
  14. transient Object[] elementData;
  16. //保存的对象个数
  17. private int size;
  19. //最大容量2的31次方减9
  20. private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

ArrayList提供了三个构造器，一个是指定初始化大小的构造器，一个人无参默认初始化大小构造器，一个是使用集合初始化的构造器

  1. public ArrayList(int initialCapacity) {
  2.   if (initialCapacity > 0) {
  3.     //数组的大小为指定大小
  4.     this.elementData = new Object[initialCapacity];
  5.   } else if (initialCapacity == 0) {
  6.     //大小为0用一个共享的空数组赋值
  7.     this.elementData = EMPTY_ELEMENTDATA;
  8.   } else {
  9.     throw new IllegalArgumentException("Illegal Capacity: "+
  10.                                        initialCapacity);
  11.   }
  12. }
  14. public ArrayList() {
  15.   //用共享的空数组赋值，不使用EMPTY_ELEMENTDATA主要是区分是使用的哪个构造器
  16.   this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
  17. }
  19. public ArrayList(Collection<? extends E> c) {
  20.   elementData = c.toArray();
  21.   if ((size = elementData.length) != 0) {
  22.     // c.toArray might (incorrectly) not return Object[] (see 6260652)
  23.     if (elementData.getClass() != Object[].class)
  24.       elementData = Arrays.copyOf(elementData, size, Object[].class);
  25.   } else {
  26.     // 集合为空，使用空数组
  27.     this.elementData = EMPTY_ELEMENTDATA;
  28.   }
  29. }
  1. public boolean add(E e) {
  2.   ensureCapacityInternal(size + 1);  // Increments modCount!!
  3.   elementData[size++] = e;
  4.   return true;
  5. }
  7. private void ensureCapacityInternal(int minCapacity) {
  8.   ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
  9. }
  10. //计算容量
  11. private static int calculateCapacity(Object[] elementData, int minCapacity) {
  12.   if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {//通过无参构造器创建
  13.     return Math.max(DEFAULT_CAPACITY, minCapacity);
  14.   }
  15.   return minCapacity;
  16. }
  18. private void ensureExplicitCapacity(int minCapacity) {
  19.   modCount++;
  21.   // 如果最小需要的容量>数组大小
  22.   if (minCapacity - elementData.length > 0)
  23.     //进行扩容
  24.     grow(minCapacity);
  25. }
  27. private void grow(int minCapacity) {
  28.   
  29.   int oldCapacity = elementData.length;
  30.   //新容量=老容量+老容量>>1;老容量>>1即老容量无符号右移1位，即除以2，所以最后新容量是老容量的1.5倍
  31.   int newCapacity = oldCapacity + (oldCapacity >> 1);
  32.   if (newCapacity - minCapacity < 0)//新容量比最小容量小那么把最小容量赋值给新容量
  33.     newCapacity = minCapacity;
  34.   if (newCapacity - MAX_ARRAY_SIZE > 0)//如果minCapacity很大，计算得出newCapacity超出最大容量
  35.     newCapacity = hugeCapacity(minCapacity);
  36.   // 复制未扩容之前的数据
  37.   elementData = Arrays.copyOf(elementData, newCapacity);
  38. }
  40. private static int hugeCapacity(int minCapacity) {
  41.   if (minCapacity < 0) // overflow
  42.     throw new OutOfMemoryError();
  43.   //如果最小容量还超出ArrayList规定的最大值那么数组大小为Integer.MAX_VALUE否则为ArrayList规定的最大值
  44.   return (minCapacity > MAX_ARRAY_SIZE) ?
  45.     Integer.MAX_VALUE :
  46.   MAX_ARRAY_SIZE;
  47. }
  1. public void add(int index, E element) {
  2.   //检查添加元素的下标
  3.   rangeCheckForAdd(index);
  4. 	//检查容量，进行扩容
  5.   ensureCapacityInternal(size + 1);  // Increments modCount!!
  6.   
  7.   // public static native void arraycopy(src, srcPos,dest, destPos,length);
  8.   //src：源数组；srcPos：源数组起始下标；dest：目标数组；destPos：目标数组起始下标；length：拷贝长度
  9.   System.arraycopy(elementData, index, elementData, index + 1,
  10.                    size - index);
  11.   elementData[index] = element;
  12.   size++;
  13. }
  15. private void rangeCheckForAdd(int index) {
  16.   //元素的下标必须为0-size
  17.   if (index > size || index < 0)
  18.     throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
  19. }
  1. public E remove(int index) {
  2.   //检查下标
  3.   rangeCheck(index);
  5.   modCount++;
  6.   //按照下标获取元素
  7.   E oldValue = elementData(index);
  8.   //计算需要移动的数据个数
  9.   int numMoved = size - index - 1;
  10.   if (numMoved > 0)
  11.     System.arraycopy(elementData, index+1, elementData, index,
  12.                      numMoved);
  13.   //清理数组elementData[size]位置的元素
  14.   elementData[--size] = null; // clear to let GC do its work
  16.   return oldValue;
  17. }
  19. private void rangeCheck(int index) {
  20.   //下标必须在0到size-1之间
  21.   if (index >= size)
  22.     throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
  23. }
  25. E elementData(int index) {
  26.   return (E) elementData[index];
  27. }
  1. public boolean remove(Object o) {
  2.   if (o == null) {//如果移除的元素为null,依次遍历保存的元素，移除第一个为null的元素
  3.     for (int index = 0; index < size; index++)
  4.       if (elementData[index] == null) {
  5.         //移除
  6.         fastRemove(index);
  7.         return true;
  8.       }
  9.   } else {
  10.     for (int index = 0; index < size; index++)
  11.       //使用equals判断是否相等
  12.       if (o.equals(elementData[index])) {
  13.         fastRemove(index);
  14.         return true;
  15.       }
  16.   }
  17.   return false;
  18. }
  20. private void fastRemove(int index) {
  21.   modCount++;
  22.   //计算移除后需要移动的元素个数
  23.   int numMoved = size - index - 1;
  24.   if (numMoved > 0)
  25.     System.arraycopy(elementData, index+1, elementData, index,
  26.                      numMoved);
  27.   //清理数组elementData[size]位置的元素
  28.   elementData[--size] = null; // clear to let GC do its work
  29. }

ArrayList在进行add、set、remove时，都进行了modCount+1操作，这个属性与fast fail有关，当对象创建Iterator对象时会把modCount赋值给expectedModCount，当使用Iterator进行遍历时，如果发现对象的modCount与expectedModCount不相等，会直接抛出ConcurrentModificationException异常

  1. public Iterator<E> iterator() {
  2.         return new Itr();
  3.     }
  5. private class Itr implements Iterator<E> {
  6.   int cursor;       // index of next element to return
  7.   int lastRet = -1; // index of last element returned; -1 if no such
  8.   int expectedModCount = modCount;
  9.   ...
  10.     public E next() {
  11.     checkForComodification();
  12.     ...
  13.   }
  15.   final void checkForComodification() {
  16.     if (modCount != expectedModCount)//直接抛出异常
  17.       throw new ConcurrentModificationException();
  18.   }

出现情况：当Iterator遍历时，如果对象的modCount和expectedModCount不等就会抛出异常，主要有这些情况

  • 使用iterator遍历时，进行了add、remove等破坏结构的操作
  • 多线程环境下，一个线程在遍历时，另一个线程进行了add、remove等破坏结构的操作

通过源码学习，我发现set方法并没有增加modCount,为什么呢？难道一个线程在使用iterator遍历，另外一个线程改变了一个位置的元素，Iterator不用抛出异常？有知道的请赐教！

  1. public class LinkedList<E>
  2.     extends AbstractSequentialList<E>
  3.     implements List<E>, Deque<E>, Cloneable, java.io.Serializable

LinkedList继承AbstractSequentialList可以实现通过Iterator的随机访问

LinkedList实现List接口可以进行添加删除等操作

LinkedList实现了DeQue,允许在队列的两端进行入队和出队，所以可以把LinkedList当做队列或栈使用

LinkedList实现了Cloneable，可以通过clone快速克隆对象

LinkedList实现了Serializable接口，可以将LinkedList序列化，进行流操作

  1. public LinkedList() {
  2.     }
  4. //使用集合初始化链表
  5. public LinkedList(Collection<? extends E> c) {
  6.         this();
  7.         addAll(c);
  8.     }
  1. //链表的大小，transient表明在序列化的时候不进行序列化，但是LinkedList自定义的序列化方法中进行了序列化
  2. transient int size = 0;
  4. //链表的头节点
  5. transient Node<E> first;
  7. //链表的尾节点
  8. transient Node<E> last;
  1. private static class Node<E> {
  2.   E item;
  3.   //前驱
  4.   Node<E> next;
  5.   //后继
  6.   Node<E> prev;
  8.   Node(Node<E> prev, E element, Node<E> next) {
  9.     this.item = element;
  10.     this.next = next;
  11.     this.prev = prev;
  12.   }
  13. }

可以看到LinkedList是一个双向链表

Deque是一个双端链表，即链表可有当做栈和队列使用

getFirst方法,相当于Queue中的element方法,如果队空，就抛出异常

  1. public E getFirst() {
  2.   final Node<E> f = first;
  3.   if (f == null)
  4.     throw new NoSuchElementException();
  5.   return f.item;
  6. }

getLast方法

  1. public E getLast() {
  2.         final Node<E> l = last;
  3.         if (l == null)
  4.             throw new NoSuchElementException();
  5.         return l.item;
  6.     }

removeFirst方法，相当于Queue的remove方法，删除队头元素，如果队空，抛出异常

  1. public E removeFirst() {
  2.         final Node<E> f = first;
  3.         if (f == null)
  4.             throw new NoSuchElementException();
  5.         return unlinkFirst(f);
  6.     }
  8. private E unlinkFirst(Node<E> f) {
  9.   // assert f == first && f != null;
  10.   final E element = f.item;
  11.   final Node<E> next = f.next;
  12.   f.item = null;
  13.   f.next = null; // help GC
  14.   first = next;
  15.   if (next == null)
  16.     //如果原头节点的后继为空，那么把尾指针也更新为空
  17.     last = null;
  18.   else
  19.     //原头节点的后继为不空，那么需要把它的前驱更新为空
  20.     next.prev = null;
  21.   //更新链表大小
  22.   size--;
  23.   modCount++;
  24.   return element;
  25. }

removeLast方法，如果队空，抛出异常

  1. public E removeLast() {
  2.         final Node<E> l = last;
  3.         if (l == null)
  4.             throw new NoSuchElementException();
  5.         return unlinkLast(l);
  6.     }
  8. private E unlinkLast(Node<E> l) {
  9.         // assert l == last && l != null;
  10.         final E element = l.item;
  11.         final Node<E> prev = l.prev;
  12.         l.item = null;
  13.         l.prev = null; // help GC
  14.         last = prev;
  15.         if (prev == null)
  16.           //如果原尾指针的前驱为空，那么头指针指向也为空
  17.             first = null;
  18.         else
  19.           //原尾指针的前驱不为空，那么它的后继应该改为空
  20.             prev.next = null;
  21.         size--;
  22.         modCount++;
  23.         return element;
  24.     }

addFirst方法，相当于Statck中的push方法

  1. public void addFirst(E e) {
  2.   linkFirst(e);
  3. }
  5. private void linkFirst(E e) {
  6.   final Node<E> f = first;
  7.   //创建一个前驱为空，后驱为first的新节点
  8.   final Node<E> newNode = new Node<>(null, e, f);
  9.   first = newNode;
  10.   if (f == null)
  11.     //如果原头指针为空，那么把尾指针也赋值为新加节点
  12.     last = newNode;
  13.   else
  14.     //原头指正不空，把它的前驱更新为新节点
  15.     f.prev = newNode;
  16.   size++;
  17.   modCount++;
  18. }

addLast方法,相当于Queue中的add方法

  1. public void addLast(E e) {
  2.         linkLast(e);
  3.     }
  5. void linkLast(E e) {
  6.         final Node<E> l = last;
  7.         final Node<E> newNode = new Node<>(l, e, null);
  8.         last = newNode;
  9.         if (l == null)
  10.           //如果原为指针指向就为空，那么头指针也指向新节点
  11.             first = newNode;
  12.         else
  13.           //原为指针指向就不为空，那么它的后继更新为新加节点
  14.             l.next = newNode;
  15.         size++;
  16.         modCount++;
  17.     }

add方法是重写AbstractList中的方法，即往List中添加元素

  1. public boolean add(E e) {
  2.         linkLast(e);
  3.         return true;
  4.  }
  5. void linkLast(E e) {
  6.         final Node<E> l = last;
  7.         final Node<E> newNode = new Node<>(l, e, null);
  8.         last = newNode;
  9.         if (l == null)
  10.             first = newNode;
  11.         else
  12.             l.next = newNode;
  13.         size++;
  14.         modCount++;
  15.     }

remove方法移除链表中指定元素

  1. public boolean remove(Object o) {
  2.         if (o == null) {
  3.           //如果要移除的对象为null,那么取链表中找第一个null元素并移除
  4.             for (Node<E> x = first; x != null; x = x.next) {
  5.                 if (x.item == null) {
  6.                     unlink(x);
  7.                     return true;
  8.                 }
  9.             }
  10.         } else {
  11.             for (Node<E> x = first; x != null; x = x.next) {
  12.                 if (o.equals(x.item)) {//使用equals比较两个对象是否相同
  13.                     unlink(x);
  14.                     return true;
  15.                 }
  16.             }
  17.         }
  18.         return false;
  19.     }

addAll方法向链表中添加指定集合的元素

  1. public boolean addAll(Collection<? extends E> c) {
  2.         return addAll(size, c);
  3.     }
  5.  public boolean addAll(int index, Collection<? extends E> c) {
  6.         checkPositionIndex(index);
  8.         Object[] a = c.toArray();
  9.         int numNew = a.length;
  10.    //如果集合大小为0
  11.         if (numNew == 0)
  12.             return false;
  13. //什么一个前驱节点和一个后继节点
  14.         Node<E> pred, succ;
  15.         if (index == size) {
  16.           //如果添加的位置恰好是size即在链表最后添加,那么后继为null，前驱为链表尾指针
  17.             succ = null;
  18.             pred = last;
  19.         } else {
  20.             succ = node(index);
  21.             pred = succ.prev;
  22.         }
  24.         for (Object o : a) {
  25.             @SuppressWarnings("unchecked") E e = (E) o;
  26.             Node<E> newNode = new Node<>(pred, e, null);
  27.             if (pred == null)//如果没有前驱节点
  28.               //把链表头指针指向新节点
  29.                 first = newNode;
  30.             else
  31.                 pred.next = newNode;
  32.           //前驱节点赋值为当前新节点
  33.             pred = newNode;
  34.         }
  36.         if (succ == null) {//如果没有后继节点
  37.           //把尾指针指向'前驱节点'
  38.             last = pred;
  39.         } else {
  40.             pred.next = succ;
  41.             succ.prev = pred;
  42.         }
  44.         size += numNew;
  45.         modCount++;
  46.         return true;
  47.     }

clear方法清空链表，但是modCount并不会清空

  1. public void clear() {
  2.         for (Node<E> x = first; x != null; ) {
  3.             Node<E> next = x.next;
  4.           //help GC？
  5.             x.item = null;
  6.             x.next = null;
  7.             x.prev = null;
  8.             x = next;
  9.         }
  10.         first = last = null;
  11.         size = 0;
  12.         modCount++;
  13.     }

get方法获取指定下标元素，非法下标抛出异常

  1. public E get(int index) {
  2.   checkElementIndex(index);
  3.   return node(index).item;
  4. }
  5. Node<E> node(int index) {
  6.   // assert isElementIndex(index);
  7.   //通过一个二分遍历拿元素
  8.   if (index < (size >> 1)) {
  9.     Node<E> x = first;
  10.     for (int i = 0; i < index; i++)
  11.       x = x.next;
  12.     return x;
  13.   } else {
  14.     Node<E> x = last;
  15.     for (int i = size - 1; i > index; i--)
  16.       x = x.prev;
  17.     return x;
  18.   }
  19. }

set方法设置指定下标元素值，非法下标抛出异常，set方法modCount不++？why？

  1. public E set(int index, E element) {
  2.   checkElementIndex(index);
  3.   //获取元素
  4.   Node<E> x = node(index);
  5.   E oldVal = x.item;
  6.   //替换
  7.   x.item = element;
  8.   return oldVal;
  9. }

add方法，指定下标添加元素，非法下标抛出异常

  1. public void add(int index, E element) {
  2.         checkPositionIndex(index);
  4.         if (index == size)//链表尾添加元素
  5.             linkLast(element);
  6.         else
  7.           //链表中间位置添加元素
  8.             linkBefore(element, node(index));
  9.     }
  10. void linkBefore(E e, Node<E> succ) {
  11.         // assert succ != null;
  12.         final Node<E> pred = succ.prev;
  13.         final Node<E> newNode = new Node<>(pred, e, succ);
  14.         succ.prev = newNode;
  15.         if (pred == null)//添加元素位置前驱为null，即添加位置本来就是头指针位置
  16.             first = newNode;
  17.         else
  18.           //更新前驱的next为当前添加节点
  19.             pred.next = newNode;
  20.         size++;
  21.         modCount++;
  22.     }

remove方法，移除指定下标元素，非法下标抛出异常

  1. public E remove(int index) {
  2.         checkElementIndex(index);
  3.         return unlink(node(index));
  4.     }
  6. E unlink(Node<E> x) {
  7.         // assert x != null;
  8.         final E element = x.item;
  9.         final Node<E> next = x.next;
  10.         final Node<E> prev = x.prev;
  12.         if (prev == null) {//如果移除节点的前驱为null，即移除节点为头指针指向位置
  13.             first = next;
  14.         } else {
  15.             prev.next = next;
  16.           //help GC？
  17.             x.prev = null;
  18.         }
  20.         if (next == null) {//如果移除节点的后继节点为null，即移除节点是尾指针指向位置
  21.             last = prev;
  22.         } else {
  23.             next.prev = prev;
  24.           //help GC？
  25.             x.next = null;
  26.         }
  27. 		//help GC？
  28.         x.item = null;
  29.         size--;
  30.         modCount++;
  31.         return element;
  32.     }

peek方法，获取链表头节点，可为Queue/Stack方法，Queue方法即获取队手元素，Stack方法即获取栈顶元素

  1. public E peek() {
  2.   final Node<E> f = first;
  3.   return (f == null) ? null : f.item;
  4. }

element方法，获取链表头节点，与peek方法不同的是，如果队列为空，抛出异常

  1. public E element() {
  2.   return getFirst();
  3. }
  5. public E getFirst() {
  6.   final Node<E> f = first;
  7.   if (f == null)
  8.     //链表空抛出异常
  9.     throw new NoSuchElementException();
  10.   return f.item;
  11. }

poll方法移除链表头节点，链表空返回null

  1. public E poll() {
  2.         final Node<E> f = first;
  3.         return (f == null) ? null : unlinkFirst(f);
  4.     }

remove方法移除链表头节点，链表空抛出异常

  1. public E remove() {
  2.   return removeFirst();
  3. }
  4. public E removeFirst() {
  5.   final Node<E> f = first;
  6.   if (f == null)
  7.     //链表空抛出异常
  8.     throw new NoSuchElementException();
  9.   return unlinkFirst(f);
  10. }

offer方法，在链表尾添加元素

  1. public boolean offer(E e) {
  2.         return add(e);
  3.     }
  4. public boolean add(E e) {
  5.         linkLast(e);
  6.         return true;
  7.     }

offerFirst方法，在链表头添加节点，对应栈的入栈操作

  1. public boolean offerFirst(E e) {
  2.         addFirst(e);
  3.         return true;
  4.     }
  5. public void addFirst(E e) {
  6.         linkFirst(e);
  7.     }

offerLast方法，在链表尾添加元素，本质上和offer方法没有区别

  1. public boolean offerLast(E e) {
  2.         addLast(e);
  3.         return true;
  4.     }
  5. public void addLast(E e) {
  6.         linkLast(e);
  7.     }

peekFirst方法，查看链表头节点，相当于Queue和Stack的peek方法，链表空返回null

  1. public E peekFirst() {
  2.         final Node<E> f = first;
  3.         return (f == null) ? null : f.item;
  4.      }

peekLast方法，查看链表尾节点，链表空返回null

  1. public E peekLast() {
  2.         final Node<E> l = last;
  3.         return (l == null) ? null : l.item;
  4.     }

pollFirst方法，查看并删除链表头节点，链表空返回null

  1. public E pollFirst() {
  2.         final Node<E> f = first;
  3.         return (f == null) ? null : unlinkFirst(f);
  4.     }

pollLast查看并删除链表尾节点，链表空返回null

  1. public E pollLast() {
  2.         final Node<E> l = last;
  3.         return (l == null) ? null : unlinkLast(l);
  4.     }

push方法头节点位置添加，Stack的push方法

  1. public void push(E e) {
  2.         addFirst(e);
  3.     }
  4. public void addFirst(E e) {
  5.         linkFirst(e);
  6.     }

pop方法删除头节点位置元素,Stack的pop方法

  1. public E pop() {
  2.         return removeFirst();
  3.     }
  4. public E removeFirst() {
  5.         final Node<E> f = first;
  6.         if (f == null)//链表空抛异常
  7.             throw new NoSuchElementException();
  8.         return unlinkFirst(f);
  9.     }

removeFirstOccurrence方法从头结点开始查找指定元素并移除

  1. public boolean removeFirstOccurrence(Object o) {
  2.         return remove(o);
  3.     }
  4. public boolean remove(Object o) {
  5.         if (o == null) {//要移除的元素为null
  6.             for (Node<E> x = first; x != null; x = x.next) {//从头查找，移除第一个为null元素
  7.                 if (x.item == null) {
  8.                     unlink(x);
  9.                     return true;
  10.                 }
  11.             }
  12.         } else {
  13.             for (Node<E> x = first; x != null; x = x.next) {//依次遍历
  14.                 if (o.equals(x.item)) {//使用equals判断相等
  15.                     unlink(x);
  16.                     return true;
  17.                 }
  18.             }
  19.         }
  20.         return false;
  21.     }

removeLastOccurrence方法从尾节点开始查找并移除指定元素

  1. public boolean removeLastOccurrence(Object o) {
  2.         if (o == null) {//如果移除元素为null
  3.             for (Node<E> x = last; x != null; x = x.prev) {//从后往前遍历
  4.                 if (x.item == null) {
  5.                     unlink(x);
  6.                     return true;
  7.                 }
  8.             }
  9.         } else {
  10.             for (Node<E> x = last; x != null; x = x.prev) {
  11.                 if (o.equals(x.item)) {//使用equals判断相等
  12.                     unlink(x);
  13.                     return true;
  14.                 }
  15.             }
  16.         }
  17.         return false;
  18.     }

listIterator方法返回链表迭代器

  1. public ListIterator<E> listIterator(int index) {
  2.         checkPositionIndex(index);
  3.         return new ListItr(index);
  4.     }
  5. //由于LinkedList是双向链表，所以可以双向遍历
  6. private class ListItr implements ListIterator<E> {
  7.         private Node<E> lastReturned;
  8.         private Node<E> next;
  9.         private int nextIndex;
  10.   		//expectedModCount保存拿到迭代器时，LinkedList的modCount值，与快速失败有关
  11.         private int expectedModCount = modCount;
  12.   
  13.   public boolean hasNext() {
  14.             return nextIndex < size;
  15.         }
  17.         public E next() {
  18.             checkForComodification();
  19.             if (!hasNext())
  20.                 throw new NoSuchElementException();
  22.             lastReturned = next;
  23.             next = next.next;
  24.             nextIndex++;
  25.             return lastReturned.item;
  26.         }
  28.         public boolean hasPrevious() {
  29.             return nextIndex > 0;
  30.         }
  32.         public E previous() {
  33.             checkForComodification();
  34.             if (!hasPrevious())
  35.                 throw new NoSuchElementException();
  37.             lastReturned = next = (next == null) ? last : next.prev;
  38.             nextIndex--;
  39.             return lastReturned.item;
  40.         }
  41.   
  42.   final void checkForComodification() {
  43.             if (modCount != expectedModCount)//如果链表的modCount和拿到迭代器时modCount不同，说明在迭代过程中，链表进行了破坏结构的修改，那么应该直接抛出异常
  44.                 throw new ConcurrentModificationException();
  45.         }
  46. }

可以看到，Vector的类结构和ArrayList的一模一样

Vector继承AbstractList实现了List接口

Vector实现了RandomAccess接口，可以随机访问

Vector实现了Cloneable接口，可以使用克隆对象

Vector实现了Serializable接口，可以序列化

  1. //保存对象的数组
  2. protected Object[] elementData;
  4. //保存元素个数
  5. protected int elementCount;
  7. //增长因子
  8. protected int capacityIncrement;
  10. //定义的最大容量，为2的31次方-9
  11. private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
  1. public Vector(int initialCapacity, int capacityIncrement) {//指定初始容量和增长因子
  2.         super();
  3.         if (initialCapacity < 0)
  4.             throw new IllegalArgumentException("Illegal Capacity: "+
  5.                                                initialCapacity);
  6.   //直接把数组创建为初始化值大小
  7.         this.elementData = new Object[initialCapacity];
  8.         this.capacityIncrement = capacityIncrement;
  9.     }
  1. public Vector(int initialCapacity) {
  2.   //把增长因子设置为0
  3.         this(initialCapacity, 0);
  4.     }
  1. public Vector() {
  2.   //默认初始化大小为10
  3.         this(10);
  4.     }
  1. public Vector(Collection<? extends E> c) {
  2.         elementData = c.toArray();
  3.         elementCount = elementData.length;
  4.         // c.toArray might (incorrectly) not return Object[] (see 6260652)
  5.         if (elementData.getClass() != Object[].class)
  6.             elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
  7.     }

copyInto方法把元素拷贝到指定数组

  1. public synchronized void copyInto(Object[] anArray) {
  2.         System.arraycopy(elementData, 0, anArray, 0, elementCount);
  3.     }

trimToSize方法把保存元素的数组修改到保存元素个数大小

  1. public synchronized void trimToSize() {
  2.         modCount++;
  3.         int oldCapacity = elementData.length;
  4.         if (elementCount < oldCapacity) {//如果元素个数比容量小
  5.             elementData = Arrays.copyOf(elementData, elementCount);
  6.         }
  7.     }

ensureCapacity方法用于添加元素时，确保数组大小

  1. public synchronized void ensureCapacity(int minCapacity) {
  2.         if (minCapacity > 0) {
  3.             modCount++;
  4.             ensureCapacityHelper(minCapacity);
  5.         }
  6.     }
  8. private void ensureCapacityHelper(int minCapacity) {
  9.         // overflow-conscious code
  10.         if (minCapacity - elementData.length > 0)//如果需要的最小容量大于数组大小
  11.           //扩容
  12.             grow(minCapacity);
  13.     }
  15. private void grow(int minCapacity) {
  16.         // overflow-conscious code
  17.         int oldCapacity = elementData.length;
  18.   //如果指定了增长因子而且增长因子>0那么新容量就等于原容量+增长因子，否则就是原容量的二倍
  19.         int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
  20.                                          capacityIncrement : oldCapacity);
  21.         if (newCapacity - minCapacity < 0)
  22.             newCapacity = minCapacity;
  23.         if (newCapacity - MAX_ARRAY_SIZE > 0)
  24.             newCapacity = hugeCapacity(minCapacity);
  25.         elementData = Arrays.copyOf(elementData, newCapacity);
  26.     }

setSize方法设置向量的大小

  1. public synchronized void setSize(int newSize) {
  2.         modCount++;
  3.         if (newSize > elementCount) {//如果新容量比原容量大，多的元素全为null
  4.             ensureCapacityHelper(newSize);
  5.         } else {
  6.           //新容量比原容量小
  7.             for (int i = newSize ; i < elementCount ; i++) {
  8.                 elementData[i] = null;
  9.             }
  10.         }
  11.         elementCount = newSize;
  12.     }

removeElementAt移除指定位置元素

  1. public synchronized void removeElementAt(int index) {
  2.         modCount++;
  3.         if (index >= elementCount) {
  4.             throw new ArrayIndexOutOfBoundsException(index + " >= " +
  5.                                                      elementCount);
  6.         }
  7.         else if (index < 0) {
  8.             throw new ArrayIndexOutOfBoundsException(index);
  9.         }
  10.   //要移动的元素个数
  11.         int j = elementCount - index - 1;
  12.         if (j > 0) {
  13.             System.arraycopy(elementData, index + 1, elementData, index, j);
  14.         }
  15.         elementCount--;
  16.         elementData[elementCount] = null; /* to let gc do its work */
  17.     }

insertElementAt指定位置插入元素

  1. public synchronized void insertElementAt(E obj, int index) {
  2.         modCount++;
  3.         if (index > elementCount) {
  4.             throw new ArrayIndexOutOfBoundsException(index
  5.                                                      + " > " + elementCount);
  6.         }
  7.   //确保容量
  8.         ensureCapacityHelper(elementCount + 1);
  9.         System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
  10.         elementData[index] = obj;
  11.         elementCount++;
  12.     }

addElement在尾部添加元素

  1. public synchronized void addElement(E obj) {
  2.         modCount++;
  3.   //确保容量
  4.         ensureCapacityHelper(elementCount + 1);
  5.         elementData[elementCount++] = obj;
  6.     }

removeElement移除指定元素

  1. public synchronized boolean removeElement(Object obj) {
  2.         modCount++;
  3.         int i = indexOf(obj);
  4.         if (i >= 0) {
  5.             removeElementAt(i);
  6.             return true;
  7.         }
  8.         return false;
  9.     }

removeAllElements移除所有元素

  1. public synchronized void removeAllElements() {
  2.         modCount++;
  3.         // Let gc do its work
  4.         for (int i = 0; i < elementCount; i++)
  5.             elementData[i] = null;
  7.         elementCount = 0;
  8.     }

get获取指定位置元素

  1. public synchronized E get(int index) {
  2.         if (index >= elementCount)
  3.             throw new ArrayIndexOutOfBoundsException(index);
  5.         return elementData(index);
  6.     }

set替换指定位置元素

  1. public synchronized E set(int index, E element) {
  2.         if (index >= elementCount)
  3.             throw new ArrayIndexOutOfBoundsException(index);
  5.         E oldValue = elementData(index);
  6.         elementData[index] = element;
  7.         return oldValue;
  8.     }

add方法添加元素，与addElement方法的区别仅仅是返回值不同

  1. public synchronized boolean add(E e) {
  2.         modCount++;
  3.         ensureCapacityHelper(elementCount + 1);
  4.         elementData[elementCount++] = e;
  5.         return true;
  6.     }

remove移除尾元素

  1. public boolean remove(Object o) {
  2.         return removeElement(o);
  3.     }

add指定位置添加元素

  1. public void add(int index, E element) {
  2.         insertElementAt(element, index);
  3.     }

remove移除指定位置元素

  1. public synchronized E remove(int index) {
  2.         modCount++;
  3.         if (index >= elementCount)
  4.             throw new ArrayIndexOutOfBoundsException(index);
  5.         E oldValue = elementData(index);
  6. //计算要移动的元素个数
  7.         int numMoved = elementCount - index - 1;
  8.         if (numMoved > 0)
  9.             System.arraycopy(elementData, index+1, elementData, index,
  10.                              numMoved);
  11.         elementData[--elementCount] = null; // Let gc do its work
  13.         return oldValue;
  14.     }

listIterator获取向量的迭代器，可以进行向前向后遍历

  1. public synchronized ListIterator<E> listIterator() {
  2.         return new ListItr(0);
  3.     }
  4. final class ListItr extends Itr implements ListIterator<E> {
  5.         ListItr(int index) {
  6.             super();
  7.             cursor = index;
  8.         }
  10.         public boolean hasPrevious() {
  11.             return cursor != 0;
  12.         }
  14.         public int nextIndex() {
  15.             return cursor;
  16.         }
  18.         public int previousIndex() {
  19.             return cursor - 1;
  20.         }
  22.         public E previous() {
  23.             synchronized (Vector.this) {
  24.                 checkForComodification();
  25.                 int i = cursor - 1;
  26.                 if (i < 0)
  27.                     throw new NoSuchElementException();
  28.                 cursor = i;
  29.                 return elementData(lastRet = i);
  30.             }
  31.         }
  33.         public void set(E e) {
  34.             if (lastRet == -1)
  35.                 throw new IllegalStateException();
  36.             synchronized (Vector.this) {
  37.                 checkForComodification();
  38.                 Vector.this.set(lastRet, e);
  39.             }
  40.         }
  42.         public void add(E e) {
  43.             int i = cursor;
  44.             synchronized (Vector.this) {
  45.                 checkForComodification();
  46.                 Vector.this.add(i, e);
  47.                 expectedModCount = modCount;
  48.             }
  49.             cursor = i + 1;
  50.             lastRet = -1;
  51.         }
  52.     }

可以看到Vector和ArrayList的源码基本相同，只是Vector是线程安全的，还有就是Vector和ArrayList在扩容上有一点点不同，Vector如果指定了增长因子，那么新容量是原容量+增长因子，而ArrayList是直接扩大两倍原容量

版权声明：本文为moyuduo原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/moyuduo/p/12702275.html