List集合

List 接口

概述

• 有序的collection，可以对列表中的每个元素的插入位置进行精确的控制。用户可以根据元素的整数索引（在列表中的位置）访问元素，并搜索列表中的元素。

• 有序(存储和取出的元素一致)，允许重复的元素。

  // 创建集合对象
  List list = new ArrayList();
  
  // 存储元素
  list.add("hello");
  list.add("world");
  list.add("java");
  list.add("javaee");
  list.add("android");
  list.add("javaee");
  list.add("android");
  
  // 遍历集合
  Iterator it = list.iterator();
  while (it.hasNext()) {
  	String s = (String) it.next();
  	System.out.println(s);
  }
  结果：
  	hello
  	world
  	java
  	javaee
  	android
  	javaee
  	android

• List存储自定义对象并遍历

  // 创建集合对象
  List list = new ArrayList();
  
  //创建学生对象
  Student s1 = new Student("苏伯陵",27);
  Student s2 = new Student("东方瑾",26);
  Student s3 = new Student("夜子宸",28);
  
  //把学生对象添加到集合中
  list.add(s1);
  list.add(s2);
  list.add(s3);
  
  //遍历集合
  Iterator it = list.terator();
  while(it.hasNex()){
  	Student s = (Student)it.next();
  	System.out.println(s.getName + "---" + s.getAge());
  }

成员方法

方法名	描述
void add(int index,E element)	在指定位置添加元素
E get(int index)	获取指定位置的元素
E remove(int index)	根据索引删除元素,返回被删除的元素
E set(int index,E element)	根据索引修改元素，返回被修饰的元素
ListIterator listIterator()	List集合特有的迭代器

ArrayList

ArrayList特点

• 【支持类型】：只能装入引用对象（基本类型要转换为封装类）

• 【线程是否安全】：线程不安全

• 【底层数据结构】：底层由数组实现（顺序表），因为由顺序表实现，所以会具备顺序表的特点，如：需要声明长度、超出长度时需要进行扩容、不适合频繁的移动删除元素、检索元素快；

• 【存储数据】：有序容器，即存放元素的顺序与添加顺序相同，允许添加相同元素，包括 null

• 以数组实现。节约空间，但数组有容量限制。超出限制时会增加50%容量，用System.arraycopy()复制到新的数组，因此最好能给出数组大小的预估值。默认第一次插入元素时创建大小为10的数组。

• 按数组下标访问元素—get(i)/set(i,e) 的性能很高，这是数组的基本优势。直接在数组末尾加入元素—add(e)的性能也高，但如果按下标插入、删除元素—add(i,e), remove(i), remove(e)，则要用System.arraycopy()来移动部分受影响的元素，性能就变差了，这是基本劣势。

• 类的定义:ArrayList 是支持快速访问，可克隆，可序列化的。

  public class ArrayList<E> extends AbstractList<E>
          implements List<E>, RandomAccess, Cloneable, java.io.Serializable

构造方法

• 构造函数有两个，一般情况下很少使用到用户指定容量的那个方法。

  /**
   * 空数组（用于空实例）。
   */
  private static final Object[] EMPTY_ELEMENTDATA = {};
  
   //用于默认大小空实例的共享空数组实例。
    //我们把它从EMPTY_ELEMENTDATA数组中区分出来，以知道在添加第一个元素时容量需要增加多少。
  private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
  
  /**
   * 保存ArrayList数据的数组
   */
  transient Object[] elementData; // non-private to simplify nested class access
  
  /**
   * 带初始容量参数的构造函数。（用户自己指定容量）
   */
  public ArrayList(int initialCapacity) {
      if (initialCapacity > 0) {
          //创建initialCapacity大小的数组
          this.elementData = new Object[initialCapacity];
      } else if (initialCapacity == 0) {
          //创建空数组
          this.elementData = EMPTY_ELEMENTDATA;
      } else {
          throw new IllegalArgumentException("Illegal Capacity: "+
                                             initialCapacity);
      }
  }
  
  /**
   *默认构造函数，其默认初始容量为10
   */
  public ArrayList() {
      this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
  }

add(E e)方法

• 看源码可知，其操作是将指定的元素追加到此列表的末尾。

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

• 可以看到它的实现其实最核心的内容就是ensureCapacityInternal。这个函数其实就是自动扩容机制的核心。依次来看一下他的具体实现。

  private void ensureCapacityInternal(int minCapacity) {
      if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
          minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
      }
      ensureExplicitCapacity(minCapacity);
  }
  private void ensureExplicitCapacity(int minCapacity) {
      modCount++;
      // overflow-conscious code
      if (minCapacity - elementData.length > 0)
          grow(minCapacity);
  }
  private void grow(int minCapacity) {
      // overflow-conscious code
      int oldCapacity = elementData.length;
      // 扩展为原来的1.5倍
      int newCapacity = oldCapacity + (oldCapacity >> 1);
      // 如果扩为1.5倍还不满足需求，直接扩为需求值
      if (newCapacity - minCapacity < 0)
          newCapacity = minCapacity;
      if (newCapacity - MAX_ARRAY_SIZE > 0)
          newCapacity = hugeCapacity(minCapacity);
      // minCapacity is usually close to size, so this is a win:
      elementData = Arrays.copyOf(elementData, newCapacity);
  }

• 当增加数据的时候，如果ArrayList的大小已经不满足需求时，那么就将数组变为原长度的1.5倍，之后的操作就是把老的数组拷到新的数组里面。例如，默认的数组大小是10，也就是说当我们add10个元素之后，再进行一次add时，就会发生自动扩容，数组长度由10变为了15

add(int index, E element)

• 在指定索引处添加一个元素，先对index进行界限检查，；然后调用 ensureCapacityInternal 方法保证capacity足够大，再将从index开始之后的所有成员后移一个位置；将element插入index位置；最后size加1。

• 可以看出它比add(index)方法还要多一个System.arraycopy。arraycopy()这个实现数组之间复制的方法一定要看一下，下面就用到了arraycopy()方法实现数组自己复制自己

  public void add(int index, E element) {
      if (index > size || index < 0)
          throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
  
      ensureCapacityInternal(size + 1);  // Increments modCount!!
      System.arraycopy(elementData, index, elementData, index + 1,
                       size - index);
      elementData[index] = element;
      size++;
  }

set(int index, E element)

• 先做index检查，用指定的元素替换此列表中指定位置的元素。

  public E set(int index, E element) {
      if (index >= size)
          throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
  
      E oldValue = (E) elementData[index];
      elementData[index] = element;
      return oldValue;
  }

get(int index)

• 先做index检查，然后返回指定索引处的元素。

  public E get(int index) {
      if (index >= size)
          throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
  
      return (E) elementData[index];
  }

remove(Object o)

• 需要调用 System.arraycopy() 将 index+1 后面的元素都复制到 index 位置上，该操作的时间复杂度为 O(N)，可以看出 ArrayList 删除元素的代价是非常高的。

  /**
   * 删除该列表中指定位置的元素。 将任何后续元素移动到左侧（从其索引中减去一个元素）。
   */
  public E remove(int index) {
      rangeCheck(index);
  
      modCount++;
      E oldValue = elementData(index);
  
      int numMoved = size - index - 1;
      if (numMoved > 0)
          System.arraycopy(elementData, index+1, elementData, index,
                           numMoved);
      elementData[--size] = null; // clear to let GC do its work
    //从列表中删除的元素
      return oldValue;
  }
  
  /**
   * 从列表中删除指定元素的第一个出现（如果存在）。 如果列表不包含该元素，则它不会更改。
   *返回true，如果此列表包含指定的元素
   */
  public boolean remove(Object o) {
      if (o == null) {
          for (int index = 0; index < size; index++)
              if (elementData[index] == null) {
                  fastRemove(index);
                  return true;
              }
      } else {
          for (int index = 0; index < size; index++)
              if (o.equals(elementData[index])) {
                  fastRemove(index);
                  return true;
              }
      }
      return false;
  }

contains(Object o)

• 可以看到，先判断查找的o对象是否为空，然后再去遍历所有的元素，然后返回此列表中指定元素的首次出现的索引，如果此列表不包含此元素，则为-1。最后判断如果此列表包含指定的元素，则返回true，否则返回false。

  /**
   * 如果此列表包含指定的元素，则返回true 。
   */
  public boolean contains(Object o) {
      //indexOf()方法：返回此列表中指定元素的首次出现的索引，如果此列表不包含此元素，则为-1
      return indexOf(o) >= 0;
  }
  
  /**
   *返回此列表中指定元素的首次出现的索引，如果此列表不包含此元素，则为-1
   */
  public int indexOf(Object o) {
      if (o == null) {
          for (int i = 0; i < size; i++)
              if (elementData[i]==null)
                  return i;
      } else {
          for (int i = 0; i < size; i++)
              //equals()方法比较
              if (o.equals(elementData[i]))
                  return i;
      }
      return -1;
  }

ArrayList扩容消耗

• 由于ArrayList使用elementData = Arrays.copyOf(elementData, newCapacity);进行扩容，而每次都会重新创建一个newLength长度的数组，所以扩容的空间复杂度为O(n),时间复杂度为O(n)。

  public boolean add(E e) {
      ensureCapacityInternal(size + 1);  // Increments modCount!!
      elementData[size++] = e;
      return true;
  }
  
  private void ensureCapacityInternal(int minCapacity) {
      if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
          minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
      }
      ensureExplicitCapacity(minCapacity);
  }
  
  private void ensureExplicitCapacity(int minCapacity) {
      modCount++;
      // overflow-conscious code
      if (minCapacity - elementData.length > 0)
          grow(minCapacity);
  }
  
  private void grow(int minCapacity) {
      // overflow-conscious code
      int oldCapacity = elementData.length;
      int newCapacity = oldCapacity + (oldCapacity >> 1);
      if (newCapacity - minCapacity < 0)
          newCapacity = minCapacity;
      if (newCapacity - MAX_ARRAY_SIZE > 0)
          newCapacity = hugeCapacity(minCapacity);
      // minCapacity is usually close to size, so this is a win:
      elementData = Arrays.copyOf(elementData, newCapacity);
  }

• 然后在看看Arrays.copyOf(elementData, newCapacity)的源码

  @SuppressWarnings("unchecked")
  public static <T> T[] copyOf(T[] original, int newLength) {
      return (T[]) copyOf(original, newLength, original.getClass());
  }
  
  public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
      T[] copy = ((Object)newType == (Object)Object[].class)
          ? (T[]) new Object[newLength]
          : (T[]) Array.newInstance(newType.getComponentType(), newLength);
      System.arraycopy(original, 0, copy, 0,
                       Math.min(original.length, newLength));
      return copy;
  }

System.arraycopy()和Arrays.copyOf()

• add(int index, E element)方法就很巧妙的用到了arraycopy()方法让数组自己复制自己实现让index开始之后的所有成员后移一个位置:

  /**
  * 在此列表中的指定位置插入指定的元素。
  * 先调用 rangeCheckForAdd 对index进行界限检查；然后调用
  	ensureCapacityInternal 方法保证capacity足够大；
  * 再将从index开始之后的所有成员后移一个位置；将element插入index位置；最后size加1。
  */
  public void add(int index, E element) {
    rangeCheckForAdd(index);
    ensureCapacityInternal(size + 1);
    //arraycopy()方法实现数组自己复制自己
    //elementData:源数组;index:源数组中的起始位置;elementData：目标数组；index +1：目标数组中的起始位置； size - index：要复制的数组元素的数量；
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    elementData[index] = element;
    size++;
  }

• 如toArray()方法中用到了copyOf()方法。

  /**
   *以正确的顺序（从第一个到最后一个元素）返回一个包含此列表中所有元素的数组。
   *返回的数组将是“安全的”，因为该列表不保留对它的引用。
  （换句话说，这个方法必须分配一个新的数组）。
   *因此，调用者可以自由地修改返回的数组。
  此方法充当基于阵列和基于集合的API之间的桥梁。
   */
  public Object[] toArray() {
    //elementData：要复制的数组；size：要复制的长度
    return Arrays.copyOf(elementData, size);
  }

• 两者联系与区别

  • 看了上面的两者源代码可以发现copyOf()内部调用了System.arraycopy()方法

  • 区别：

    • arraycopy()需要目标数组，将原数组拷贝到你自己定义的数组里，而且可以选择拷贝的起点和长度以及放入新数组中的位置

    • copyOf()是系统自动在内部新建一个数组，并返回该数组。

两个copy的区别

• 使用System.arraycopy()方法

  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int[] a = new int[10];
    a[0] = 0;
    a[1] = 1;
    a[2] = 2;
    a[3] = 3;
    System.arraycopy(a, 2, a, 3, 3);
    a[2]=99;
    for (int i = 0; i < a.length; i++) {
      System.out.println(a[i]);
    }
  }
  
  //结果：
  //0 1 2  3 0 0 0 0 0 0
  //将index=2之后三个数复制到index=3的位置：空出idex=2
  //0 1 2  2 3 0 0 0 0 0
  //修改index=2后
  //0 1 99 2 3 0 0 0 0 0

• 使用Arrays.copyOf()方法

  public static void main(String[] args) {
    int[] a = new int[3];
    a[0] = 0;
    a[1] = 1;
    a[2] = 2;
    int[] b = Arrays.copyOf(a, 10);
    System.out.println("b.length"+b.length);
    //结果：
    //10
  }

• 得出结论

  • arraycopy()
    需要目标数组，将原数组拷贝到你自己定义的数组里或者原数组，而且可以选择拷贝的起点和长度以及放入新数组中的位置
  • copyOf() 是系统自动在内部新建一个数组，并返回该数组。

ArrayList核心源代码

• 如下所示，可能对某些方法理解有偏差，如果有，欢迎提出，谢谢

  public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
      private static final long serialVersionUID = 8683452581122892189L;
  
      /**
       * 默认初始容量大小
       */
      private static final int DEFAULT_CAPACITY = 10;
  
      /**
       * 空数组（用于空实例）。
       */
      private static final Object[] EMPTY_ELEMENTDATA = {};
  
       //用于默认大小空实例的共享空数组实例。
        //我们把它从EMPTY_ELEMENTDATA数组中区分出来，以知道在添加第一个元素时容量需要增加多少。
      private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
  
      /**
       * 保存ArrayList数据的数组
       */
      transient Object[] elementData; // non-private to simplify nested class access
  
      /**
       * ArrayList 所包含的元素个数
       */
      private int size;
  
      /**
       * 带初始容量参数的构造函数。（用户自己指定容量）
       */
      public ArrayList(int initialCapacity) {
          if (initialCapacity > 0) {
              //创建initialCapacity大小的数组
              this.elementData = new Object[initialCapacity];
          } else if (initialCapacity == 0) {
              //创建空数组
              this.elementData = EMPTY_ELEMENTDATA;
          } else {
              throw new IllegalArgumentException("Illegal Capacity: "+
                                                 initialCapacity);
          }
      }
  
      /**
       *默认构造函数，其默认初始容量为10
       */
      public ArrayList() {
          this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
      }
  
      /**
       * 构造一个包含指定集合的元素的列表，按照它们由集合的迭代器返回的顺序。
       */
      public ArrayList(Collection<? extends E> c) {
          //
          elementData = c.toArray();
          //如果指定集合元素个数不为0
          if ((size = elementData.length) != 0) {
              // c.toArray 可能返回的不是Object类型的数组所以加上下面的语句用于判断，
              //这里用到了反射里面的getClass()方法
              if (elementData.getClass() != Object[].class)
                  elementData = Arrays.copyOf(elementData, size, Object[].class);
          } else {
              // 用空数组代替
              this.elementData = EMPTY_ELEMENTDATA;
          }
      }
  
      /**
       * 修改这个ArrayList实例的容量是列表的当前大小。 应用程序可以使用此操作来最小化ArrayList实例的存储。
       */
      public void trimToSize() {
          modCount++;
          if (size < elementData.length) {
              elementData = (size == 0)
                ? EMPTY_ELEMENTDATA
                : Arrays.copyOf(elementData, size);
          }
      }
  
      //下面是ArrayList的扩容机制
      //ArrayList的扩容机制提高了性能，如果每次只扩充一个，
      //那么频繁的插入会导致频繁的拷贝，降低性能，而ArrayList的扩容机制避免了这种情况。
      /**
       * 如有必要，增加此ArrayList实例的容量，以确保它至少能容纳元素的数量
       * @param   minCapacity   所需的最小容量
       */
      public void ensureCapacity(int minCapacity) {
          int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
              // any size if not default element table
              ? 0
              // larger than default for default empty table. It's already
              // supposed to be at default size.
              : DEFAULT_CAPACITY;
  
          if (minCapacity > minExpand) {
              ensureExplicitCapacity(minCapacity);
          }
      }
     //得到最小扩容量
      private void ensureCapacityInternal(int minCapacity) {
          if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
                // 获取默认的容量和传入参数的较大值
              minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
          }
  
          ensureExplicitCapacity(minCapacity);
      }
    //判断是否需要扩容
      private void ensureExplicitCapacity(int minCapacity) {
          modCount++;
  
          // overflow-conscious code
          if (minCapacity - elementData.length > 0)
              //调用grow方法进行扩容，调用此方法代表已经开始扩容了
              grow(minCapacity);
      }
  
      /**
       * 要分配的最大数组大小
       */
      private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
  
      /**
       * ArrayList扩容的核心方法。
       */
      private void grow(int minCapacity) {
          // oldCapacity为旧容量，newCapacity为新容量
          int oldCapacity = elementData.length;
          //将oldCapacity 右移一位，其效果相当于oldCapacity /2，
          //我们知道位运算的速度远远快于整除运算，整句运算式的结果就是将新容量更新为旧容量的1.5倍，
          int newCapacity = oldCapacity + (oldCapacity >> 1);
          //然后检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数组的新容量，
          if (newCapacity - minCapacity < 0)
              newCapacity = minCapacity;
          //再检查新容量是否超出了ArrayList所定义的最大容量，
          //若超出了，则调用hugeCapacity()来比较minCapacity和 MAX_ARRAY_SIZE，
          //如果minCapacity大于最大容量，则新容量则为ArrayList定义的最大容量，否则，新容量大小则为 minCapacity。
          if (newCapacity - MAX_ARRAY_SIZE > 0)
              newCapacity = hugeCapacity(minCapacity);
          // minCapacity is usually close to size, so this is a win:
          elementData = Arrays.copyOf(elementData, newCapacity);
      }
  
      //比较minCapacity和 MAX_ARRAY_SIZE
      private static int hugeCapacity(int minCapacity) {
          if (minCapacity < 0) // overflow
              throw new OutOfMemoryError();
          return (minCapacity > MAX_ARRAY_SIZE) ?
              Integer.MAX_VALUE :
              MAX_ARRAY_SIZE;
      }
    
      /**
       *返回此列表中的元素数。
       */
      public int size() {
          return size;
      }
    
      /**
       * 如果此列表不包含元素，则返回 true 。
       */
      public boolean isEmpty() {
          //注意=和==的区别
          return size == 0;
      }
    
      /**
       * 如果此列表包含指定的元素，则返回true 。
       */
      public boolean contains(Object o) {
          //indexOf()方法：返回此列表中指定元素的首次出现的索引，如果此列表不包含此元素，则为-1
          return indexOf(o) >= 0;
      }
    
      /**
       *返回此列表中指定元素的首次出现的索引，如果此列表不包含此元素，则为-1
       */
      public int indexOf(Object o) {
          if (o == null) {
              for (int i = 0; i < size; i++)
                  if (elementData[i]==null)
                      return i;
          } else {
              for (int i = 0; i < size; i++)
                  //equals()方法比较
                  if (o.equals(elementData[i]))
                      return i;
          }
          return -1;
      }
    
      /**
       * 返回此列表中指定元素的最后一次出现的索引，如果此列表不包含元素，则返回-1。.
       */
      public int lastIndexOf(Object o) {
          if (o == null) {
              for (int i = size-1; i >= 0; i--)
                  if (elementData[i]==null)
                      return i;
          } else {
              for (int i = size-1; i >= 0; i--)
                  if (o.equals(elementData[i]))
                      return i;
          }
          return -1;
      }
    
      /**
       * 返回此ArrayList实例的浅拷贝。 （元素本身不被复制。）
       */
      public Object clone() {
          try {
              ArrayList<?> v = (ArrayList<?>) super.clone();
              //Arrays.copyOf功能是实现数组的复制，返回复制后的数组。参数是被复制的数组和复制的长度
              v.elementData = Arrays.copyOf(elementData, size);
              v.modCount = 0;
              return v;
          } catch (CloneNotSupportedException e) {
              // 这不应该发生，因为我们是可以克隆的
              throw new InternalError(e);
          }
      }
    
      /**
       *以正确的顺序（从第一个到最后一个元素）返回一个包含此列表中所有元素的数组。
       *返回的数组将是“安全的”，因为该列表不保留对它的引用。 （换句话说，这个方法必须分配一个新的数组）。
       *因此，调用者可以自由地修改返回的数组。 此方法充当基于阵列和基于集合的API之间的桥梁。
       */
      public Object[] toArray() {
          return Arrays.copyOf(elementData, size);
      }
    
      /**
       * 以正确的顺序返回一个包含此列表中所有元素的数组（从第一个到最后一个元素）;
       *返回的数组的运行时类型是指定数组的运行时类型。 如果列表适合指定的数组，则返回其中。
       *否则，将为指定数组的运行时类型和此列表的大小分配一个新数组。
       *如果列表适用于指定的数组，其余空间（即数组的列表数量多于此元素），则紧跟在集合结束后的数组中的元素设置为null 。
       *（这仅在调用者知道列表不包含任何空元素的情况下才能确定列表的长度。）
       */
      @SuppressWarnings("unchecked")
      public <T> T[] toArray(T[] a) {
          if (a.length < size)
              // 新建一个运行时类型的数组，但是ArrayList数组的内容
              return (T[]) Arrays.copyOf(elementData, size, a.getClass());
              //调用System提供的arraycopy()方法实现数组之间的复制
          System.arraycopy(elementData, 0, a, 0, size);
          if (a.length > size)
              a[size] = null;
          return a;
      }
    
      // Positional Access Operations
    
      @SuppressWarnings("unchecked")
      E elementData(int index) {
          return (E) elementData[index];
      }
    
      /**
       * 返回此列表中指定位置的元素。
       */
      public E get(int index) {
          rangeCheck(index);
    
          return elementData(index);
      }
    
      /**
       * 用指定的元素替换此列表中指定位置的元素。
       */
      public E set(int index, E element) {
          //对index进行界限检查
          rangeCheck(index);
    
          E oldValue = elementData(index);
          elementData[index] = element;
          //返回原来在这个位置的元素
          return oldValue;
      }
    
      /**
       * 将指定的元素追加到此列表的末尾。
       */
      public boolean add(E e) {
          ensureCapacityInternal(size + 1);  // Increments modCount!!
          //这里看到ArrayList添加元素的实质就相当于为数组赋值
          elementData[size++] = e;
          return true;
      }
    
      /**
       * 在此列表中的指定位置插入指定的元素。
       *先调用 rangeCheckForAdd 对index进行界限检查；然后调用 ensureCapacityInternal 方法保证capacity足够大；
       *再将从index开始之后的所有成员后移一个位置；将element插入index位置；最后size加1。
       */
      public void add(int index, E element) {
          rangeCheckForAdd(index);
    
          ensureCapacityInternal(size + 1);  // Increments modCount!!
          //arraycopy()这个实现数组之间复制的方法一定要看一下，下面就用到了arraycopy()方法实现数组自己复制自己
          System.arraycopy(elementData, index, elementData, index + 1,
                           size - index);
          elementData[index] = element;
          size++;
      }
    
      /**
       * 删除该列表中指定位置的元素。 将任何后续元素移动到左侧（从其索引中减去一个元素）。
       */
      public E remove(int index) {
          rangeCheck(index);
    
          modCount++;
          E oldValue = elementData(index);
    
          int numMoved = size - index - 1;
          if (numMoved > 0)
              System.arraycopy(elementData, index+1, elementData, index,
                               numMoved);
          elementData[--size] = null; // clear to let GC do its work
        //从列表中删除的元素
          return oldValue;
      }
    
      /**
       * 从列表中删除指定元素的第一个出现（如果存在）。 如果列表不包含该元素，则它不会更改。
       *返回true，如果此列表包含指定的元素
       */
      public boolean remove(Object o) {
          if (o == null) {
              for (int index = 0; index < size; index++)
                  if (elementData[index] == null) {
                      fastRemove(index);
                      return true;
                  }
          } else {
              for (int index = 0; index < size; index++)
                  if (o.equals(elementData[index])) {
                      fastRemove(index);
                      return true;
                  }
          }
          return false;
      }
    
      /*
       * Private remove method that skips bounds checking and does not
       * return the value removed.
       */
      private void fastRemove(int index) {
          modCount++;
          int numMoved = size - index - 1;
          if (numMoved > 0)
              System.arraycopy(elementData, index+1, elementData, index,
                               numMoved);
          elementData[--size] = null; // clear to let GC do its work
      }
    
      /**
       * 从列表中删除所有元素。
       */
      public void clear() {
          modCount++;
          // 把数组中所有的元素的值设为null
          for (int i = 0; i < size; i++)
              elementData[i] = null;
    
          size = 0;
      }
    
      /**
       * 按指定集合的Iterator返回的顺序将指定集合中的所有元素追加到此列表的末尾。
       */
      public boolean addAll(Collection<? extends E> c) {
          Object[] a = c.toArray();
          int numNew = a.length;
          ensureCapacityInternal(size + numNew);  // Increments modCount
          System.arraycopy(a, 0, elementData, size, numNew);
          size += numNew;
          return numNew != 0;
      }
    
      /**
       * 将指定集合中的所有元素插入到此列表中，从指定的位置开始。
       */
      public boolean addAll(int index, Collection<? extends E> c) {
          rangeCheckForAdd(index);
    
          Object[] a = c.toArray();
          int numNew = a.length;
          ensureCapacityInternal(size + numNew);  // Increments modCount
    
          int numMoved = size - index;
          if (numMoved > 0)
              System.arraycopy(elementData, index, elementData, index + numNew,
                               numMoved);
    
          System.arraycopy(a, 0, elementData, index, numNew);
          size += numNew;
          return numNew != 0;
      }
    
      /**
       * 从此列表中删除所有索引为fromIndex （含）和toIndex之间的元素。
       *将任何后续元素移动到左侧（减少其索引）。
       */
      protected void removeRange(int fromIndex, int toIndex) {
          modCount++;
          int numMoved = size - toIndex;
          System.arraycopy(elementData, toIndex, elementData, fromIndex,
                           numMoved);
    
          // clear to let GC do its work
          int newSize = size - (toIndex-fromIndex);
          for (int i = newSize; i < size; i++) {
              elementData[i] = null;
          }
          size = newSize;
      }
    
      /**
       * 检查给定的索引是否在范围内。
       */
      private void rangeCheck(int index) {
          if (index >= size)
              throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
      }
    
      /**
       * add和addAll使用的rangeCheck的一个版本
       */
      private void rangeCheckForAdd(int index) {
          if (index > size || index < 0)
              throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
      }
    
      /**
       * 返回IndexOutOfBoundsException细节信息
       */
      private String outOfBoundsMsg(int index) {
          return "Index: "+index+", Size: "+size;
      }
    
      /**
       * 从此列表中删除指定集合中包含的所有元素。
       */
      public boolean removeAll(Collection<?> c) {
          Objects.requireNonNull(c);
          //如果此列表被修改则返回true
          return batchRemove(c, false);
      }
    
      /**
       * 仅保留此列表中包含在指定集合中的元素。
       *换句话说，从此列表中删除其中不包含在指定集合中的所有元素。
       */
      public boolean retainAll(Collection<?> c) {
          Objects.requireNonNull(c);
          return batchRemove(c, true);
      }
  
      /**
       * 从列表中的指定位置开始，返回列表中的元素（按正确顺序）的列表迭代器。
       *指定的索引表示初始调用将返回的第一个元素为next 。 初始调用previous将返回指定索引减1的元素。
       *返回的列表迭代器是fail-fast 。
       */
      public ListIterator<E> listIterator(int index) {
          if (index < 0 || index > size)
              throw new IndexOutOfBoundsException("Index: "+index);
          return new ListItr(index);
      }
    
      /**
       *返回列表中的列表迭代器（按适当的顺序）。
       *返回的列表迭代器是fail-fast 。
       */
      public ListIterator<E> listIterator() {
          return new ListItr(0);
      }
    
      /**
       *以正确的顺序返回该列表中的元素的迭代器。
       *返回的迭代器是fail-fast 。
       */
      public Iterator<E> iterator() {
          return new Itr();
      }
  }

ArrayList的序列化

• ArrayList
  基于数组实现，并且具有动态扩容特性，因此保存元素的数组不一定都会被使用，那么就没必要全部进行序列化。

• 保存元素的数组 elementData 使用 transient修饰，该关键字声明数组默认不会被序列化。

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

• ArrayList 实现了 writeObject() 和 readObject()来控制只序列化数组中有元素填充那部分内容。

  private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    elementData = EMPTY_ELEMENTDATA;
    s.defaultReadObject();
    s.readInt(); // ignored
    if (size \> 0) {
      ensureCapacityInternal(size);
      Object[] a = elementData;
      for (int i=0; i\<size; i++) {
        a[i] = s.readObject();
      }
    }
  }
  
  private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException{
    int expectedModCount = modCount;
    s.defaultWriteObject();
    s.writeInt(size);
    for (int i=0; i\<size; i++) {
      s.writeObject(elementData[i]);
    }
    if (modCount != expectedModCount) {
      throw new ConcurrentModificationException();
    }
  }

• 序列化时需要使用 ObjectOutputStream 的 writeObject()将对象转换为字节流并输出。

  • 而 writeObject() 方法在传入的对象存在writeObject() 的时候会去反射调用该对象的 writeObject()来实现序列化。

  • 反序列化使用的是 ObjectInputStream 的 readObject()方法，原理类似。

    ArrayList<Student> list = new ArrayList();
    ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream(file));
    oos.writeObject(list);

ArrayList的Fail-Fast

• Java集合的快速失败机制 “fail-fast”

• java集合的一种错误检测机制，当多个线程对集合进行结构上的改变的操作时，有可能会产生fail-fast 机制。

  • 例如：假设存在两个线程（线程1、线程2），线程1通过Iterator在遍历集合A中的元素，在某个时候线程2修改了集合A的结构（是结构上面的修改，而不是简单的修改集合元素的内容），那么这个时候程序就会抛出ConcurrentModificationException 异常，从而产生fail-fast机制。

• 原因：

  • 迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个modCount变量。集合在被遍历期间如果内容发生变化，就会改变modCount的值。
  • 每当迭代器使用hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍历；否则抛出异常，终止遍历。

• 解决办法：

  • 1.在遍历过程中，所有涉及到改变modCount值得地方全部加上synchronized。
  • 2.使用CopyOnWriteArrayList来替换ArrayList

• modCount 用来记录 ArrayList结构发生变化的次数。结构发生变化是指添加或者删除至少一个元素的所有操作，或者是调整内部数组的大小，仅仅只是设置元素的值不算结构发生变化。

• 在进行序列化或者迭代等操作时，需要比较操作前后 modCount是否改变，如果改变了需要抛出 ConcurrentModificationException。

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

增删改查示例

• add操作可以理解为直接将数组的内容置位，remove操作可以理解为删除index为0的节点，并将后面元素移到0处。

• 代码如下：

  //创建list对象
  List list = new ArrayList();
  
  //添加元素
  list.add("hello");
  list.add("world");
  list.add("java");
  
  ----指定位置添加元素---------------------------------------
  list.add(1,"android");
  System.out.println("list:" + list);			//list:[hello, android, world, java]
  	list.add(4, "javaee");					//有问题 IndexOutOfBoundsException
  	list.add(3, "javaee"); 					//没有问题,在最后添加list:[hello, world, java, javaee]
  
  ----获取指定位置的元素--------------------------------------
  System.out.println("get:" + list.get(1));	//get:world
  System.out.println("list:" + list);			//list:[hello, world, java]
  System.out.println("get:" + list.get(3));	//IndexOutOfBoundsException
  ----索引删除元素，返回被删除的元素--------------------------------------
  System.out.println("remove:" + list.remove(1));		//remove:world
  System.out.println("list:" + list);					//list:[hello, java]
  System.out.println("remove:" + list.remove(3));		// IndexOutOfBoundsException
  
  ----索引修改元素，返回被修饰的元素--------------------------------------
  System.out.println("set:" + list.set(1, "javaee"));	//set:world
  System.out.println("list:" + list);					//list:[hello, javaee, java]

ArrayList 的遍历

普通for，只能是List

• 通过遍历数组，size()和get()结合

  // 创建集合对象
  List list = new ArrayList();
  
  //创建学生对象
  Student s1 = new Student("苏伯陵",27);
  Student s2 = new Student("东方瑾",26);
  Student s3 = new Student("夜子宸",28);
  
  //把学生对象添加到集合中
  list.add(s1);
  list.add(s2);
  list.add(s3);
  
  //遍历集合
  for(int i =0; i<list.size();i++){
  	Student s = (Student)list.ger(i);
  	System.out.println(s.getName + "---" + s.getAge());
  }

增强for 集合都能用

• 代码如下

  for(String s : list) {
  	System.out.println(s);
  }

集合的forEach方法

• list.forEach(Consumer接口)

• list.forEach(System.out::println):方法的引用

  list.forEach(new Consumer<String>() {
  	//t 集合元素
  	@Override
  	public void accept(String t) {
  		System.out.println(t);
  	}
  });
  
  list.forEach(t->System.out.println(t));//lambda
  
  list.forEach(System.out::println);//方法的引用

列表迭代器

• ListIterator listIterator()：List集合特有的迭代器

  • 该迭代器继承了Iterator迭代器，所以，就可以直接使用hasNext()和next()方法。

  • forEachRemaining(Consumer接口);

    Iterator<String> i = list.iterator();
    i.forEachRemaining(System.out::println);

• 特有功能：

  • Object previous():获取上一个元素
  • boolean hasPrevious():判断是否有元素
  • void add();将指定的元素插入到列表中（可选操作）。
  • void remove();删除最近一次next()的元素
  • void set(E e);取代过去的元素返回 next()或 previous()与指定的元素

  //next 遍历后可以向上遍历
  ListIterator<String > i = list.listIterator();
  while(i.hasPrevious()){
  	System.out.println(i.previous());
  }
  
  //修改,添加,删除.没有并发异常
  while(iterator.hasNext()){
  	String next = iterator.next();
  	if("aa".equals(next)){
  		iterator.set("123");
  		iterator.remove();
  		iterator.add("456");
  	}
  }

迭代器遍历数组

• 代码如下

  // 创建List集合对象
  List list = new ArrayList();
  list.add("hello");
  list.add("world");
  list.add("java");
  
  // 集合的遍历
  // 创建迭代器
  ListIteartor lit = list.listIterator();	// 子类对象
  
  while (lit.hasNext()) {
  	String s = (String) lit.next();
  	System.out.println(s);
  }
  
  System.out.println("-----------------");
  
  while (lit.hasPrevious()) {
  	String s = (String) lit.previous();
  	System.out.println(s);
  }
  
  结果：
  	hello
  	world
  	java
  	-----------------
  	java
  	world
  	hello

集合的流遍历

• list.stream().forEach(System.out::println);

ConcurrentModificationException

修改集合的内容

• 我有一个集合，如下，请问，我想判断里面有没有”world”这个元素，如果有，我就添加一个”javaee”元素，请写代码实现。

  List list = new ArrayList();
  // 添加元素
  list.add("hello");
  list.add("world");
  list.add("java");
  
  ListIterator lit  = list.listIterator();
  while(lit.hasNext()){
  	if(lit.next().equals("world")){
  		list.add("javaEE");
  	}
  }

• 当方法检测到对象的并发修改，但不允许这种修改时，抛出此异常。

• 迭代器依赖集合而存在，在判断成功后，集合中的新添加了元素，而迭代器却不知道，这个错叫并发修改异常。

• 其实这个问题描述的是：迭代器遍历元素的时候，通过集合是不能修改元素的。

解决办法

1. 迭代器迭代元素，迭代器修改元素

   • Iterator迭代器却没有添加功能，所以我们使用其子接口ListIterator:

   • 代码如下：

     List list = new ArrayList();
     // 添加元素
     list.add("hello");
     list.add("world");
     list.add("java");
      
     //迭代器遍历修改
     ListIterator lit =list.listIterator();
     while(lit.hasNext()){
     	String s = （String)lit.next();
     	if(s.equals("world")){
     		lit.add("javaee");
     	}
     }

2. 集合遍历元素，集合修改元素(普通for)

   • 代码如下：

     List list = new ArrayList();
     // 添加元素
     list.add("hello");
     list.add("world");
     list.add("java");
     
     //集合遍历修改
     for(int i =0;i<list.size()；i++){
     	String s = （String)list.get(i);
     	if（"world".equals(s)）{
     		list.add("javaee");
     	}
     }

Vector

Vectot集合特点

• 【支持类型】：只能装入引用对象（基本类型要转换为封装类）

• 【线程是否安全】：Vector通过synchronized方法保证线程安全；

• 【底层数据结构】：底层由动态数组实现，特点和ArrayList一样，是一样而不是类似。查询快 , 增删慢

• 特有功能,推荐使用后面的方法替代

  • public void addElement(E obj) – add() 添加元素
  • public E elementAt(int index) – get() 根据索引获取元素
  • public Enumeration elements() – Iterator iterator() 使用类似于迭代器 , 作用: 用来遍历Vector集合
  • boolean hasMoreElements() – hasNext()
  • Object nextElement() – next()

• 遍历

  Enumeration enumeration = vector.elements() ;
  // boolean hasMoreElements(): 判断集合中是否存在下一个元素
  // E nextElement(): 获取下一个元素
  while(enumeration.hasMoreElements()) {
      System.out.println(enumeration.nextElement());
  }

LinkedList

LinkedList集合特点

• 【支持类型】：只能装入引用对象（基本类型要转换为封装类）

• 【线程是否安全】：线程不安全

• 【底层数据结构】：底层实现为链表，具备链表的特点，如：不用声明长度、检索性能较差，但是插入移动删除较快。链表通过Node对象实现

• LinkedList 同时实现了 List 接口和 Deque 接口，所以既可以将 LinkedList 当做一个有序容器，也可以将之看作一个队列（Queue），同时又可以看作一个栈（Stack）。

• 虽然 LinkedList 和 ArrayList 一样都实现了 List 接口，但其底层是通过双向链表来实现的，所以 LinkedList 插入和删除元素的效率都要比 ArrayList 高，因此随机访问的效率也要比 ArrayList 低。

• 如果想使LinkedList变成线程安全的

  • 可以调用静态类

    List list =Collections.synchronizedList(new LinkedList(...));

LinkedList内部结构分析

看完了图之后，我们再看LinkedList类中的一个内部私有类Node就很好理解了

内部私有类Node

• 这个类就代表双端链表的节点Node。这个类有三个属性，分别是前驱节点，本节点的值，后继结点。

  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类声明

• 先看一下代码

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

• 从其实现的几个接口可以看出来

  • LinkedList 是支持快速访问，可克隆，可序列化的，而且可以将之看成一个支持有序访问的 队列/栈
  • 上面说过，LinkedList内部是通过双向链表的数据结构来实现的，对于链表中的结点来说，除了首尾两个结点外，其余每个结点除了存储本结点的数据元素外，还分别有两个指针用于指向其上下两个相邻结点，这个结点类就是 LinkedList 中的静态类 Node。

LinkedList构造方法

• 空构造方法：

  public LinkedList() {
  }

• 用已有的集合创建链表的构造方法：

  public LinkedList(Collection<? extends E> c) {
      this();
      addAll(c);
  }

• 不同于 ArrayList

  • 因为 LinkedList 使用的是链表结构，所以 LinkedList 不需要去请求一片连续的内存空间来存储数据，而是在每次有新的元素需要添加进来时，再来动态请求内存空间。因此 LinkedList 的两个构造函数要简单得多。

LinkedList成员变量

• 包含的成员变量

   //双向链表包含的结点总数
  transient int size = 0;
  
  //双向链表的头结点
  transient Node<E> first;
  
  //双向链表的尾结点
  transient Node<E> last;
  
  //序列化ID
  private static final long serialVersionUID = 876323262645176354L;

• 当中的成员变量 first 和 last 分别用于指向链表的头部和尾部结点，因此 LinkedList 的数据结构图是类似于这样的

  • 

LinkedList常用方法

add方法

• add(E e) 方法：将元素添加到链表尾部

  • add(E e) 方法用于向链表的尾部添加结点，因为有 last 指向链表的尾结点，因此向尾部添加新元素只需要修改几个引用即可，效率较高。

  public boolean add(E e) {
      linkLast(e);//这里就只调用了这一个方法
      return true;
  }
  
  /**
   * 链接使e作为最后一个元素。
   */
  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++;
  }

• **add(int index,E e)**：在指定位置添加元素

  • add(int index, E element) 方法用于向指定索引处添加元素，需要先通过索引 index 获取相应位置的结点，并在该位置开辟一个新的结点来存储元素 element，最后还需要修改相邻结点间的引用

  public void add(int index, E element) {
      checkPositionIndex(index); //检查索引是否处于[0-size]之间
  
      if (index == size)//添加在链表尾部
          linkLast(element);
      else//添加在链表中间
          linkBefore(element, node(index));
  }

• addAll(Collection c )：将集合插入到链表尾部

  public boolean addAll(Collection<? extends E> c) {
      return addAll(size, c);
  }

• addAll(int index, Collection c)： 将集合从指定位置开始插入

  • 上面可以看出addAll方法通常包括下面四个步骤：
  • 1.检查index范围是否在size之内
  • 2.toArray()方法把集合的数据存到对象数组中
  • 3.得到插入位置的前驱和后继节点
  • 4.遍历数据，将数据插入到指定位置

  public boolean addAll(int index, Collection<? extends E> c) {
      //1:检查index范围是否在size之内
      checkPositionIndex(index);
  
      //2:toArray()方法把集合的数据存到对象数组中
      Object[] a = c.toArray();
      int numNew = a.length;
      if (numNew == 0)
          return false;
  
      //3：得到插入位置的前驱节点和后继节点
      Node<E> pred, succ;
      //如果插入位置为尾部，前驱节点为last，后继节点为null
      if (index == size) {
          succ = null;
          pred = last;
      }
      //否则，调用node()方法得到后继节点，再得到前驱节点
      else {
          succ = node(index);
          pred = succ.prev;
      }
  
      // 4：遍历数据将数据插入
      for (Object o : a) {
          @SuppressWarnings("unchecked") E e = (E) o;
          //创建新节点
          Node<E> newNode = new Node<>(pred, e, null);
          //如果插入位置在链表头部
          if (pred == null)
              first = newNode;
          else
              pred.next = newNode;
          pred = newNode;
      }
  
      //如果插入位置在尾部，重置last节点
      if (succ == null) {
          last = pred;
      }
      //否则，将插入的链表与先前链表连接起来
      else {
          pred.next = succ;
          succ.prev = pred;
      }
  
      size += numNew;
      modCount++;
      return true;
  }

• addFirst(E e)： 将元素添加到链表头部

  public void addFirst(E e) {
      linkFirst(e);
  }
  
  private void linkFirst(E e) {
      final Node<E> f = first;
      final Node<E> newNode = new Node<>(null, e, f);//新建节点，以头节点为后继节点
      first = newNode;
      //如果链表为空，last节点也指向该节点
      if (f == null)
          last = newNode;
      //否则，将头节点的前驱指针指向新节点，也就是指向前一个元素
      else
          f.prev = newNode;
      size++;
      modCount++;
  }

• addLast(E e)： 将元素添加到链表尾部，与 add(E e) 方法一样

  public void addLast(E e) {
      linkLast(e);
  }

get方法

• get(int index)：：根据指定索引返回数据

  public E get(int index) {
      //检查index范围是否在size之内
      checkElementIndex(index);
      //调用Node(index)去找到index对应的node然后返回它的值
      return node(index).item;
  }

• 获取头节点（index=0）数据方法:

  public E getFirst() {
      final Node<E> f = first;
      if (f == null)
          throw new NoSuchElementException();
      return f.item;
  }
  public E element() {
      return getFirst();
  }
  public E peek() {
      final Node<E> f = first;
      return (f == null) ? null : f.item;
  }
  
  public E peekFirst() {
      final Node<E> f = first;
      return (f == null) ? null : f.item;
  }

• 区别：

  • getFirst(),element(),peek(),peekFirst()。这四个获取头结点方法的区别在于对链表为空时的处理，是抛出异常还是返回null，其中getFirst() 和**element()**方法将会在链表为空时，抛出异常element()方法的内部就是使用getFirst()实现的。它们会在链表为空时，抛出NoSuchElementException

• 获取尾节点（index=-1）数据方法:

  public E getLast() {
      final Node<E> l = last;
      if (l == null)
          throw new NoSuchElementException();
      return l.item;
  }
  public E peekLast() {
      final Node<E> l = last;
      return (l == null) ? null : l.item;
  }

• 两者区别：

  • getLast() 方法在链表为空时，会抛出NoSuchElementException，而peekLast() 则不会，只是会返回 null。

indexOf方法

• int indexOf(Object o)： 从头遍历找

  public int indexOf(Object o) {
      int index = 0;
      if (o == null) {
          //从头遍历
          for (Node<E> x = first; x != null; x = x.next) {
              if (x.item == null)
                  return index;
              index++;
          }
      } else {
          //从头遍历
          for (Node<E> x = first; x != null; x = x.next) {
              if (o.equals(x.item))
                  return index;
              index++;
          }
      }
      return -1;
  }

• int lastIndexOf(Object o)： 从尾遍历找

  public int lastIndexOf(Object o) {
      int index = size;
      if (o == null) {
          //从尾遍历
          for (Node<E> x = last; x != null; x = x.prev) {
              index--;
              if (x.item == null)
                  return index;
          }
      } else {
          //从尾遍历
          for (Node<E> x = last; x != null; x = x.prev) {
              index--;
              if (o.equals(x.item))
                  return index;
          }
      }
      return -1;
  }

contains方法

• contains(Object o)： 检查对象o是否存在于链表中

  public boolean contains(Object o) {
      return indexOf(o) != -1;
  }

remove()方法

• remove() 方法有两种重载形式，其内部都是通过调用 unlink(Node<E> x) 方法来移除指定结点在链表中的引用，不同于 ArrayList 在移除元素时可能导致的大量数据移动，LinkedList 只需要通过移除引用即可将指定元素从链表中移除。

• remove() ,removeFirst(),pop(): 删除头节点

  public E pop() {
      return removeFirst();
  }
  public E remove() {
      return removeFirst();
  }
  public E removeFirst() {
      final Node<E> f = first;
      if (f == null)
          throw new NoSuchElementException();
      return unlinkFirst(f);
  }

• removeLast(),pollLast(): 删除尾节点

  public E removeLast() {
      final Node<E> l = last;
      if (l == null)
          throw new NoSuchElementException();
      return unlinkLast(l);
  }
  public E pollLast() {
      final Node<E> l = last;
      return (l == null) ? null : unlinkLast(l);
  }

  • 区别： removeLast()在链表为空时将抛出NoSuchElementException，而pollLast()方法返回null。

• remove(Object o): 删除指定元素

  public boolean remove(Object o) {
      //如果删除对象为null
      if (o == null) {
          //从头开始遍历
          for (Node<E> x = first; x != null; x = x.next) {
              //找到元素
              if (x.item == null) {
                 //从链表中移除找到的元素
                  unlink(x);
                  return true;
              }
          }
      } else {
          //从头开始遍历
          for (Node<E> x = first; x != null; x = x.next) {
              //找到元素
              if (o.equals(x.item)) {
                  //从链表中移除找到的元素
                  unlink(x);
                  return true;
              }
          }
      }
      return false;
  }

  • 当删除指定对象时，只需调用remove(Object o)即可，不过该方法一次只会删除一个匹配的对象，如果删除了匹配对象，返回true，否则false。

• unlink(Node<E> 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;
  }

• **remove(int index)**：删除指定位置的元素

  public E remove(int index) {
      //检查index范围
      checkElementIndex(index);
      //将节点删除
      return unlink(node(index));
  }

示例

• 代码如下：

  package list;
  
  import java.util.Iterator;
  import java.util.LinkedList;
  
  public class LinkedListDemo {
      public static void main(String[] srgs) {
          //创建存放int类型的linkedList
          LinkedList<Integer> linkedList = new LinkedList<>();
          /************************** linkedList的基本操作 ************************/
          linkedList.addFirst(0); // 添加元素到列表开头
          linkedList.add(1); // 在列表结尾添加元素
          linkedList.add(2, 2); // 在指定位置添加元素
          linkedList.addLast(3); // 添加元素到列表结尾
  
          System.out.println("LinkedList（直接输出的）: " + linkedList);
  
          System.out.println("getFirst()获得第一个元素: " + linkedList.getFirst()); // 返回此列表的第一个元素
          System.out.println("getLast()获得第最后一个元素: " + linkedList.getLast()); // 返回此列表的最后一个元素
          System.out.println("removeFirst()删除第一个元素并返回: " + linkedList.removeFirst()); // 移除并返回此列表的第一个元素
          System.out.println("removeLast()删除最后一个元素并返回: " + linkedList.removeLast()); // 移除并返回此列表的最后一个元素
          System.out.println("After remove:" + linkedList);
          System.out.println("contains()方法判断列表是否包含1这个元素:" + linkedList.contains(1)); // 判断此列表包含指定元素，如果是，则返回true
          System.out.println("该linkedList的大小 : " + linkedList.size()); // 返回此列表的元素个数
  
          /************************** 位置访问操作 ************************/
          System.out.println("-----------------------------------------");
          linkedList.set(1, 3); // 将此列表中指定位置的元素替换为指定的元素
          System.out.println("After set(1, 3):" + linkedList);
          System.out.println("get(1)获得指定位置（这里为1）的元素: " + linkedList.get(1)); // 返回此列表中指定位置处的元素
  
          /************************** Search操作 ************************/
          System.out.println("-----------------------------------------");
          linkedList.add(3);
          System.out.println("indexOf(3): " + linkedList.indexOf(3)); // 返回此列表中首次出现的指定元素的索引
          System.out.println("lastIndexOf(3): " + linkedList.lastIndexOf(3));// 返回此列表中最后出现的指定元素的索引
  
          /************************** Queue操作 ************************/
          System.out.println("-----------------------------------------");
          System.out.println("peek(): " + linkedList.peek()); // 获取但不移除此列表的头
          System.out.println("element(): " + linkedList.element()); // 获取但不移除此列表的头
          linkedList.poll(); // 获取并移除此列表的头
          System.out.println("After poll():" + linkedList);
          linkedList.remove();
          System.out.println("After remove():" + linkedList); // 获取并移除此列表的头
          linkedList.offer(4);
          System.out.println("After offer(4):" + linkedList); // 将指定元素添加到此列表的末尾
  
          /************************** Deque操作 ************************/
          System.out.println("-----------------------------------------");
          linkedList.offerFirst(2); // 在此列表的开头插入指定的元素
          System.out.println("After offerFirst(2):" + linkedList);
          linkedList.offerLast(5); // 在此列表末尾插入指定的元素
          System.out.println("After offerLast(5):" + linkedList);
          System.out.println("peekFirst(): " + linkedList.peekFirst()); // 获取但不移除此列表的第一个元素
          System.out.println("peekLast(): " + linkedList.peekLast()); // 获取但不移除此列表的第一个元素
          linkedList.pollFirst(); // 获取并移除此列表的第一个元素
          System.out.println("After pollFirst():" + linkedList);
          linkedList.pollLast(); // 获取并移除此列表的最后一个元素
          System.out.println("After pollLast():" + linkedList);
          linkedList.push(2); // 将元素推入此列表所表示的堆栈（插入到列表的头）
          System.out.println("After push(2):" + linkedList);
          linkedList.pop(); // 从此列表所表示的堆栈处弹出一个元素（获取并移除列表第一个元素）
          System.out.println("After pop():" + linkedList);
          linkedList.add(3);
          linkedList.removeFirstOccurrence(3); // 从此列表中移除第一次出现的指定元素（从头部到尾部遍历列表）
          System.out.println("After removeFirstOccurrence(3):" + linkedList);
          linkedList.removeLastOccurrence(3); // 从此列表中移除最后一次出现的指定元素（从头部到尾部遍历列表）
          System.out.println("After removeFirstOccurrence(3):" + linkedList);
  
          /************************** 遍历操作 ************************/
          System.out.println("-----------------------------------------");
          linkedList.clear();
          for (int i = 0; i < 100000; i++) {
              linkedList.add(i);
          }
          // 迭代器遍历
          long start = System.currentTimeMillis();
          Iterator<Integer> iterator = linkedList.iterator();
          while (iterator.hasNext()) {
              iterator.next();
          }
          long end = System.currentTimeMillis();
          System.out.println("Iterator：" + (end - start) + " ms");
  
          // 顺序遍历(随机遍历)
          start = System.currentTimeMillis();
          for (int i = 0; i < linkedList.size(); i++) {
              linkedList.get(i);
          }
          end = System.currentTimeMillis();
          System.out.println("for：" + (end - start) + " ms");
  
          // 另一种for循环遍历
          start = System.currentTimeMillis();
          for (Integer i : linkedList)
              ;
          end = System.currentTimeMillis();
          System.out.println("for2：" + (end - start) + " ms");
  
          // 通过pollFirst()或pollLast()来遍历LinkedList
          LinkedList<Integer> temp1 = new LinkedList<>();
          temp1.addAll(linkedList);
          start = System.currentTimeMillis();
          while (temp1.size() != 0) {
              temp1.pollFirst();
          }
          end = System.currentTimeMillis();
          System.out.println("pollFirst()或pollLast()：" + (end - start) + " ms");
  
          // 通过removeFirst()或removeLast()来遍历LinkedList
          LinkedList<Integer> temp2 = new LinkedList<>();
          temp2.addAll(linkedList);
          start = System.currentTimeMillis();
          while (temp2.size() != 0) {
              temp2.removeFirst();
          }
          end = System.currentTimeMillis();
          System.out.println("removeFirst()或removeLast()：" + (end - start) + " ms");
      }
  }

其他常用的方法源码

• 如下所示

  //判断是否包含元素 o
  public boolean contains(Object o) {
    return indexOf(o) != -1;
  }
  
  //获取元素个数
  public int size() {
    return size;
  }
  
  //清空链表元素
  //这里将各个结点之间的引用都切断了，这并不是必须的，但这样有助于GC回收
  public void clear() {
    for (Node<E> x = first; x != null; ) {
      Node<E> next = x.next;
      x.item = null;
      x.next = null;
      x.prev = null;
      x = next;
    }
    first = last = null;
    size = 0;
    modCount++;
  }
  
  //返回第一个元素值为 o 的结点所在的索引值
  //如果查找不到，则返回 -1
  public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
      for (Node<E> x = first; x != null; x = x.next) {
        if (x.item == null)
          return index;
        index++;
      }
    } else {
      for (Node<E> x = first; x != null; x = x.next) {
        if (o.equals(x.item))
          return index;
        index++;
      }
    }
    return -1;
  }
  
  //返回最后一个元素值为 o 的结点所在的索引值
  //如果查找不到，则返回 -1
  public int lastIndexOf(Object o) {
    int index = size;
    if (o == null) {
      for (Node<E> x = last; x != null; x = x.prev) {
        index--;
        if (x.item == null)
          return index;
      }
    } else {
      for (Node<E> x = last; x != null; x = x.prev) {
        index--;
        if (o.equals(x.item))
          return index;
      }
    }
    return -1;
  }

CopyOnWriteArrayList

使用场景

• 什么是CopyOnWriteArrayList，它与ArrayList有何不同？

  • CopyOnWriteArrayList是ArrayList的一个线程安全的变体，其中所有可变操作（add、set等等）都是通过对底层数组进行一次新的复制来实现的。相比较于ArrayList它的写操作要慢一些，因为它需要实例的快照。
  • CopyOnWriteArrayList中写操作需要大面积复制数组，所以性能肯定很差，但是读操作因为操作的对象和写操作不是同一个对象，读之间也不需要加锁，读和写之间的同步处理只是在写完后通过一个简单的”=”将引用指向新的数组对象上来，这个几乎不需要时间，这样读操作就很快很安全，适合在多线程里使用，绝对不会发生ConcurrentModificationException ，因此CopyOnWriteArrayList适合使用在读操作远远大于写操作的场景里，比如缓存。

• CopyOnWriteArrayList 在写操作的同时允许读操作，大大提高了读操作的性能，因此很适合读多写少的应用场景。

• 但是 CopyOnWriteArrayList 有其缺陷：

  • 内存占用：在写操作时需要复制一个新的数组，使得内存占用为原来的两倍左右；
  • 数据不一致：读操作不能读取实时性的数据，因为部分写操作的数据还未同步到读数组中。
  • 所以 CopyOnWriteArrayList 不适合内存敏感以及对实时性要求很高的场景。

读写分离

• 写操作在一个复制的数组上进行，读操作还是在原始数组中进行，读写分离，互不影响。

• 写操作需要加锁，防止并发写入时导致写入数据丢失。

• 写操作结束之后需要把原始数组指向新的复制数组。

  public boolean add(E e) {
      final ReentrantLock lock = this.lock;
      lock.lock();
      try {
          Object[] elements = getArray();
          int len = elements.length;
          Object[] newElements = Arrays.copyOf(elements, len + 1);
          newElements[len] = e;
          setArray(newElements);
          return true;
      } finally {
          lock.unlock();
      }
  }
  
  final void setArray(Object[] a) {
      array = a;
  }
  
  @SuppressWarnings("unchecked")
  private E get(Object[] a, int index) {
      return (E) a[index];
  }

list集合读写

场景

• Vector 和 ArrayList 作为动态数组，其内部元素以数组形式顺序存储的，所以非常适合随机访问的场合。
  • 除了尾部插入和删除元素，往往性能会相对较差，比如我们在中间位置插入一个元素，需要移动后续所有元素。
• 而 LinkedList 进行节点插入、删除却要高效得多，但是随机访问性能则要比动态数组慢。

读写机制

• ArrayList在执行插入元素是超过当前数组预定义的最大值时，数组需要扩容，
  • 扩容过程需要调用底层System.arraycopy()方法进行大量的数组复制操作；
  • 在删除元素时并不会减少数组的容量（如果需要缩小数组容量，可以调用trimToSize()方法）；
  • 在查找元素时要遍历数组，对于非null的元素采取equals的方式寻找。
• LinkedList在插入元素时，须创建一个新的Entry对象，并更新相应元素的前后元素的引用；
  • 在查找元素时，需遍历链表；
  • 在删除元素时，要遍历链表，找到要删除的元素，然后从链表上将此元素删除即可。
• Vector与ArrayList仅在插入元素时容量扩充机制不一致。
  • 对于Vector，默认创建一个大小为10的Object数组，并将capacityIncrement设置为0；
  • 当插入元素数组大小不够时，
    • 如果capacityIncrement大于0，则将Object数组的大小扩大为现有size+capacityIncrement；
    • 如果capacityIncrement<=0,则将Object数组的大小扩大为现有大小的2倍。

读写效率

• ArrayList对元素的增加和删除都会引起数组的内存分配空间动态发生变化。因此，对其进行插入和删除速度较慢，但检索速度很快。

• LinkedList由于基于链表方式存放数据，增加和删除元素的速度较快，但是检索速度较慢。

• 做个测试，看下两者之间的差距

  • 分别向 ArrayList 和 LinkedList 存入同等数据量的数据，然后各自移除 100 个元素以及遍历 10000 个元素，观察两者所用的时间。

  • 可以看出来，两者之间的差距还是非常大的，因此，在使用集合时需要根据实际情况来判断到底哪一种数据结构才更加适合。

        public static void main(String[] args) {
        
                List<String> stringArrayList = new ArrayList<>();
                for (int i = 0; i < 300000; i++) {
                    stringArrayList.add("leavesC " + i);
                }
                //开始时间
                long startTime = System.currentTimeMillis();
                for (int i = 0; i < 100; i++) {
                    stringArrayList.remove(100 + i);
                }
                //结束时间
                long endTime = System.currentTimeMillis();
                System.out.println("移除 ArrayList 中的100个元素，所用时间：" + (endTime - startTime) + "毫秒");
        
                //开始时间
                startTime = System.currentTimeMillis();
                for (int i = 0; i < 10000; i++) {
                    stringArrayList.get(i);
                }
                //结束时间
                endTime = System.currentTimeMillis();
                System.out.println("遍历 ArrayList 中的10000个元素，所用时间：" + (endTime - startTime) + "毫秒");
        
                List<String> stringLinkedList = new LinkedList<>();
                for (int i = 0; i < 300000; i++) {
                    stringLinkedList.add("leavesC " + i);
                }
                //开始时间
                startTime = System.currentTimeMillis();
                for (int i = 0; i < 100; i++) {
                    stringLinkedList.remove(100 + i);
                }
                //结束时间
                endTime = System.currentTimeMillis();
                System.out.println("移除 LinkedList 中的100个元素，所用时间：" + (endTime - startTime) + "毫秒");
                //开始时间
                startTime = System.currentTimeMillis();
                for (int i = 0; i < 10000; i++) {
                    stringLinkedList.get(i);
                }
                //结束时间
                endTime = System.currentTimeMillis();
                System.out.println("遍历 LinkedList 中的10000个元素，所用时间：" + (endTime - startTime) + "毫秒");
            }
        
            移除 ArrayList 中的100个元素，所用时间：31毫秒
            遍历 ArrayList 中的10000个元素，所用时间：0毫秒
            移除 LinkedList 中的100个元素，所用时间：1毫秒
            遍历 LinkedList 中的10000个元素，所用时间：329毫秒
    
    
    
    ## List怎么实现排序
    
    - List排序方式
    
      - 实现排序，可以使用sort方法
        - sort(null): 自然排序,需要排序的类中实现Comparable接口
        - 自定义排序：list.sort(new Comparator(){...})
    
    - Arrays.sort()
    
      - 该算法是一个经过调优的快速排序，此算法在很多数据集上提供N\*log(N)的性能，这导致其他快速排序会降低二次型性能。
    
    - 使用Collections进行快速排序：Collections.sort(list)
    
      - 该算法是一个经过修改的合并排序算法（其中，如果低子列表中的最高元素效益高子列表中的最低元素，则忽略合并）。此算法可提供保证的N\*log(N)的性能，此实现将指定列表转储到一个数组中，然后再对数组进行排序，在重置数组中相应位置处每个元素的列表上进行迭代。
    
    ### 对字符串进行排序
    
    - 代码如下所示
    
      ```java
      ArrayList<String> list = new ArrayList<>();
      list.add("yc");
      list.add("doubi");
      list.add("ychong");
      list.add("123");
      list.add("abc");
      list.add("xiaoyang");
      System.out.println("yc----排序前：" + list);
      if (Build.VERSION.SDK_INT >= Build.VERSION_CODES.N) {
        Collections.sort(list, new Comparator< String>() {
          @Override
          public int compare(String lhs, String rhs) {
            int i = lhs.compareTo(rhs);
            if ( i > 0 ) {
              return 1;
            } else {
              return -1;
            }
          }
        });
        System.out.println("yc----排序后：" + list);
      }
      
      // 打印结果
      yc----排序前：[yc,doubi, ychong, 123, abc, xiaoyang]
      yc----排序后：[123, abc,doubi, xiaoyang, yc, ychong]

对数字进行排序

• 代码如下所示

  ArrayList<Integer> list = new ArrayList<>();
  list.add(9);
  list.add(15);
  list.add(5);
  list.add(52);
  list.add(-34);
  list.add(21);
  System.out.println("yc----排序前：" + list);
  if (Build.VERSION.SDK_INT >= Build.VERSION_CODES.N) {
    list.sort(new Comparator<Integer>() {
      @Override
      public int compare(Integer o1, Integer o2) {
        //这是顺序
        int i = o1.compareTo(o2);
        return i;
      }
    });
    System.out.println("yc----排序后：" + list);
  }
  
  // 打印结果
  yc----排序前：[9, 15, 5, 52, -34, 21]
  yc----排序后：[-34, 5, 9, 15, 21, 52]

对对象集合排序

• 自然排序,类实现Comparable接口

  class Dog implements Comparable<Dog>{
  	@Override
  	public int compareTo(Dog o) {
  		return this.age - o.age ;
  	}
  
  }

• 排序代码

  public static void main(String[] args) {
    List<Dog> dogs = new ArrayList<Dog>();
    Dog wangwang = new Dog("旺旺","金毛",2);
    Dog meimei = new Dog("美美","吉娃娃",3);
    Dog wangcai = new Dog("旺财","松狮",1);
    dogs.add(wangwang);
    dogs.add(meimei);
    dogs.add(wangcai);
  
    //遍历
    dogs.forEach(System.out::println);
  
    //2.实现自然排序
    dogs.sort(null);
  
    //实现comparator年龄降序
    dogs.sort((dog1,dog2)->dog2.getAge() - dog1.getAge());
  
    //删除美美
    dogs.remove(meimei);
  
    //
    System.out.println(dogs.size());	//2
  
  }

去除集合中的重复值

创建新集合

• 代码如下：

  分析：
  * A:创建集合对象
  * B:添加多个字符串元素(包含内容相同的)
  * C:
  *	    有：不搭理它
  *     没有：就添加到新集合
  * F:遍历新集合
  
  	// 创建集合对象
  	ArrayList array = new ArrayList();
  
  	// 添加多个字符串元素(包含内容相同的)
  	array.add("hello");
  	array.add("world");
  	array.add("java");
  	array.add("world");
  	array.add("java");
  	array.add("world");
  	array.add("world");
  	array.add("world");
  	array.add("world");
  	array.add("java");
  	array.add("world");
  
  	// 创建新集合
  	ArrayList newArray = new ArrayList();
  
  	// 遍历旧集合,获取得到每一个元素
  	Iterator it = array.iterator();
  	while (it.hasNext()) {
  	String s = (String) it.next();
  
  	// 拿这个元素到新集合去找，看有没有
  	if (!newArray.contains(s)) {
  		newArray.add(s);
  		}
  	}
  
  	// 遍历新集合
  	for (int x = 0; x < newArray.size(); x++) {
  		String s = (String) newArray.get(x);
  		System.out.println(s);
  	}

不创建新的集合去除重复

• 代码

  // 由选择排序思想引入，我们就可以通过这种思想做这个题目
  // 拿0索引的依次和后面的比较，有就把后的干掉
  // 同理，拿1索引...
  
  for(int i =0;i<array.size()-1;i++){
      for(int j =i+1;j<array.size();j++){
          if(array.get(i).equals(array.get(j))){
              array.remove(j);
              j--;
          }
      }
  }

去除自定义对象的重复值

• 代码如下

  Iterator it = array.iterator();
  while (it.hasNext()) {
  	Student s = (Student) it.next();
  	// 拿这个元素到新集合去找，看有没有
  	if (!newArray.contains(s)) {
  		newArray.add(s);
  	}
  }
  
  结果：
  	对象全部复制到新的数组了；
  --------------------------------
  原因:
      contains()方法的底层依赖的是equals()方法。
      而我们的学生类中没有equals()方法，这个时候，默认使用的是它父亲Object的equals()方法
      Object()的equals()默认比较的是地址值，所以，它们进去了。因为new的东西，地址值都不同。
      按照我们自己的需求，比较成员变量的值，重写equals()即可。
  -------------------------------------------------------------------------------------
  @Override
  	public boolean equals(Object obj) {
  		if (this == obj)
  			return true;
  		if (obj == null)
  			return false;
  		if (getClass() != obj.getClass())
  			return false;
  		Student other = (Student) obj;
  		if (age != other.age)
  			return false;
  		if (name == null) {
  			if (other.name != null)
  				return false;
  		} else if (!name.equals(other.name))
  			return false;
  		return true;
  	}

总结

子类	底层数据结构	特点	安全	效率
ArrayList	数组	查询快，增删慢	线程不安全	效率高
Vector	数组	查询快，增删慢	线程安全	效率低
LinkedList	链表	查询慢，增删快	线程不安全	效率高

如何选择合适list

• 对于随机查询与迭代遍历操作，数组比所有的容器都要快。所以在随机访问中一般使用ArrayList。
• LinkedList使用双向链表对元素的增加和删除提供了非常好的支持，而ArrayList执行增加和删除元素需要进行元素位移。
• 对于Vector而已，我们一般都是避免使用。（ArrayList可用通过Collections中的方法转换为线程安全类）
• 将ArrayList当做首选，毕竟对于集合元素而已我们都是进行遍历，只有当程序的性能因为List的频繁插入和删除而降低时，再考虑LinkedList。