继续创作，加快成长！这是我参与「掘金日新计划 10 月更文应战」的第9天，点击查看活动概况

`ArrayList`原理

`ArrayList`调集底层数据结构

ArrayList调集介绍

List 接口的可调整巨细的数组完成。

数组：一旦初始化长度就不能够产生改动

数组结构特性

增删慢：每次删去元素，都需求更改数组长度、仿制以及移动元素方位。

查询快：由于数组在内存中是一块连续空间，因而能够依据地址+索引的方式快速获取对应方位上的元素。

`ArrayList`继承联系

`Serializable`序列化接口

类的序列化由完成java.io.Serializable接口的类启用。不完成此接口的类将不会使任何状况序列化或反序列化。可序列化类的一切子类型都是可序列化的。序列化接口没有办法或字段，仅用于标识可串行化的语义。

序列化是将目标状况转换为可坚持或传输的格式的进程。

与序列化相对的是反序列化，它将流转换为目标。

比方将目标的数据序列化后写入到文件；

将文件中目标的数据读取出来后反序列化解析成目标。

在需求进行目标数据网络传输或耐久化时，需求将目标进行序列化

源码

public interface Serializable {
}

从源码上看Serializable是一个空接口，Java里称为标识接口，当类完成Serializable接口，相当于给该类符号了“可被序列化”的元数据，打上了“可被序列化”的标签。

序列化/反序列化测验

static class SerTest01 {
  public static void main(String[] args) throws IOException, ClassNotFoundException {
    // 测验序列化写入文件
    writeObject();
    // 测验反序列化文件读取
    readObject();
   }

  // 将目标数据写入文件
  private static void writeObject() throws IOException {
    // 序列化：将目标的数据写入到文件(写目标)
    ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream("testoutfile\obj.txt"));
    User user = new User("李四", 78);
    // 将目标数据写入文件
    oos.writeObject(user);
    // 封闭流
    oos.close();
   }

  // 将目标数据写入文件
  private static void readObject() throws IOException, ClassNotFoundException {
    // 反序列化：将文件中目标的数据读取出来(读目标)
    ObjectInputStream ois = new ObjectInputStream(new FileInputStream("..\obj.txt"));
    User user = (User) ois.readObject();
    // 将目标数据写入文件
    System.out.println(user.toString());
    // 封闭流
    ois.close();
   }
}


// User实体类
public class User implements Serializable {
  /**
   * 类的序列化由完成`java.io.Serializable`接口的类启用。
   * 不完成此接口的类将不会使任何状况序列化或反序列化。
   * 可序列化类的一切子类型都是可序列化的。
   * 序列化接口没有办法或字段，仅用于标识可串行化的语义。
   */
  public final long serialVersionUID = 1510141000893066237L;

  private String name;
  private Integer age;

  public User() {
   }

  public User(String name, Integer age) {
    this.name = name;
    this.age = age;
   }

  public String getName() {
    return name;
   }

  public void setName(String name) {
    this.name = name;
   }

  public Integer getAge() {
    return age;
   }

  public void setAge(Integer age) {
    this.age = age;
   }

  @Override
  public String toString() {
    StringBuilder sb = new StringBuilder();
    sb.append("[").append("name = ").append(this.name).append(", ").append("age = ").append(this.age).append("]");
    return sb.toString();
   }
}

完成了Serializable接口的User类能够被ObjectOutputStream转换为字节省写入文件，一起也能够经过ObjectInputStream再将其从文件读取并解析为目标。

假如User实体类不完成Serializable则无法序列化或反序列化，就会抛出反常NotSerializableException。运转会呈现下图报错

判别是否完成Serializable的源码

if (obj instanceof String) {
  writeString((String) obj, unshared);
} else if (cl.isArray()) {
  writeArray(obj, desc, unshared);
} else if (obj instanceof Enum) {
  writeEnum((Enum<?>) obj, desc, unshared);
} else if (obj instanceof Serializable) {
  writeOrdinaryObject(obj, desc, unshared);
} else {
  if (extendedDebugInfo) {
    throw new NotSerializableException(
      cl.getName() + "\n" + debugInfoStack.toString());
   } else {
    throw new NotSerializableException(cl.getName());
   }
}

这儿能够看到，Java对字符串、数组、枚举类、一般类进行序列化时单独判别的，当一般类没有完成Serializable接口就会抛出反常NotSerializableException。

`RandomAccess`随机拜访

List完成运用的符号接口，标明它们支撑快速（通常是稳定时刻）随机拜访。此接口的首要意图是答应通用算法更改其行为，以便在运用于随机拜访列表或次序拜访列表时供给杰出的功能。

用于操作随机拜访列表（例如ArrayList ）的最佳算法在运用于次序拜访列表（例如LinkedList ）时会产生二次行为。鼓舞通用列表算法在运用算法之前查看给定列表是否是此接口的实例，假如将其运用于次序拜访列表会供给较差的功能，并在必要时更改它们的行为以确保可接受的功能。

众所周知，随机拜访和次序拜访之间的区别通常是模糊的。例如，假如某些List完成变得很大，则供给渐近线性拜访时刻，但在实践中拜访时刻是稳定的。这样的List完成一般应该完成这个接口。依据经验，假如对于类的典型实例，假如呈现以下循环，则List完成应该完成此接口：

// 随机拜访，list.get(i)依据索引遍历
for (int i=0, n=list.size(); i < n; i++)
  list.get(i);

运转速度比这个循环快：

// 次序拜访，迭代器进行遍历
for (Iterator i=list.iterator(); i.hasNext(); )
  i.next();

源码

public interface RandomAccess {
}

测验次序拜访和随机拜访速度

  /**
   * 测验随机拜访比次序拜访快，这儿仅对ArrayList做遍历操作
   *
   * @param args
   */
  public static void main(String[] args) {
    // 创立ArrayList调集
    List<String> list = new ArrayList<>();
    // 增加50W条数据
    for (int i = 0; i < 500000; i++) {
      list.add(i + "a");
     }
    System.out.println("----经过索引(随机拜访)----");
    long startTime = System.currentTimeMillis();
    for (int i = 0; i < list.size(); i++) {
      list.get(i);
     }
    long endTime = System.currentTimeMillis();
    System.out.println("随机拜访用时: " + (endTime - startTime));


    System.out.println("----经过迭代器(次序拜访)----");
    startTime = System.currentTimeMillis();
    Iterator<String> it = list.iterator();
    while (it.hasNext()) {
      it.next();
     }
    endTime = System.currentTimeMillis();
    System.out.println("次序拜访用时: " + (endTime - startTime));
   }
//----经过索引(随机拜访)----
//随机拜访用时: 3
//----经过迭代器(次序拜访)----
//次序拜访用时: 4

从输出成果来看ArrayList随机拜访比次序拜访快，接下来对比下LinkedList


  public static void main(String[] args) {
      // 创立ArrayList调集
      List<String> list = new LinkedList<>();
      // 增加10W条数据
      for (int i = 0; i < 100000; i++) {
        list.add(i + "a");
       }
      System.out.println("----经过索引(随机拜访)----");
      long startTime = System.currentTimeMillis();
      for (int i = 0; i < list.size(); i++) {
        list.get(i);
       }
      long endTime = System.currentTimeMillis();
      System.out.println("随机拜访用时: " + (endTime - startTime));


      System.out.println("----经过迭代器(次序拜访)----");
      startTime = System.currentTimeMillis();
      Iterator<String> it = list.iterator();
      while (it.hasNext()) {
        it.next();
       }
      endTime = System.currentTimeMillis();
      System.out.println("次序拜访用时: " + (endTime - startTime));
     }
//----经过索引(随机拜访)----
//随机拜访用时: 11851
//----经过迭代器(次序拜访)----
//次序拜访用时: 3

从输出成果来看LinkedList的次序遍历比随机拜访快。

LinkedList源码

public class LinkedList<E>
  extends AbstractSequentialList<E>
  implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
  // 详细完成源码此处不进行评论，省略...
}

能够看到LinkedList并没有完成RandomAccess接口，契合RandomAccess接口介绍内容，此外LinkedList结构也确认了它的次序遍历比随机拜访快。

实践运用场景中主张运用instanceof判别调集是否完成了RandomAccess接口，再依据实践情况运用随机拜访或次序拜访。

if(list instanceof RandomAccess)
  // 随机拜访
else
  // 次序拜访

Cloneable克隆接口

一个类完成了Cloneable接口，以向Object.clone()办法指示该办法能够合法地对该类的实例进行逐一字段的仿制。

在未完成Cloneable接口的实例上调用 Object.clone() 办法会导致抛出反常CloneNotSupportedException 。

源码

public interface Cloneable {
}

Cloneable也是一个标识接口，此接口不包括clone办法。因而，不可能仅凭仗完成该接口的实例来克隆目标。即便以反射方式调用 clone 办法，也不能确保它会成功。

clone()运用实例

public static void main(String[] args) {
  // 创立用户目标调集
  ArrayList<User> list = new ArrayList<User>();
  list.add(new User("李四", 78));
  list.add(new User("张三", 28));

  Object o = list.clone();
  System.out.println(o);
  System.out.println(list);
  System.out.println(o == list);
}

// false
// [[name = 李四, age = 78], [name = 张三, age = 28]]
// [[name = 李四, age = 78], [name = 张三, age = 28]]

从输出看，clone()创立了一个新的目标，内容与原目标一致。

ArrayList完成了Cloneable接口，故而该类能够能够调用Object.clone()办法完成目标克隆。

若类没有完成Cloneable接口，该实例调用 Object.clone() 办法会导致抛出反常CloneNotSupportedException 。

clone源码

public Object clone() {
  try {
    ArrayList<?> v = (ArrayList<?>) super.clone();
    v.elementData = Arrays.copyOf(elementData, size);
    v.modCount = 0;
    return v;
   } catch (CloneNotSupportedException e) {
    // this shouldn't happen, since we are Cloneable
    throw new InternalError(e);
   }
}

一般类支撑 `Object.clone()` 办法

修正User类，使得支撑 Object.clone() 办法

public class User implements Serializable, Cloneable {
  
  public final long serialVersionUID = 1510141000893066237L;
  
  // 特点 getter setter toString...
  
  // 重写clone
  @Override
  public Object clone() throws CloneNotSupportedException {
    return super.clone();
   }
}

User类完成Cloneable接口，并重写 Object.clone() 办法。

重写原则

子类回来类型小于等于父类办法回来类型

子类抛出反常小于等于父类办法抛出反常

子类拜访权限大于等于父类办法拜访权限（public>protected>friendly，private不能被继承）

static class Cloneable01 {
  public static void main(String[] args) throws CloneNotSupportedException {
    User user1 = new User("张", 12);

    Object user2 = user1.clone();
    System.out.println(user1);
    System.out.println(user2);
    System.out.println(user1 == user2);
   }
}
// [name = 张, age = 12]
// [name = 张, age = 12]
// false

浅仿制

新建Address类，如下所示

public class Address implements Serializable {
  public final long serialVersionUID = 1578511564815489L;

  private String city;

  public Address() {
   }

  public Address(String city) {
    this.city = city;
   }

  public String getCity() {
    return city;
   }

  public void setCity(String city) {
    this.city = city;
   }

  @Override
  public String toString() {
    return city;
   }
}

修正User类如下所示

public class User implements Serializable, Cloneable {
    public final long serialVersionUID = 1510141000893066237L;

  private String name;
  private Integer age;

  private Address address;
  
  // setter getter...
  
  @Override
  public String toString() {
    StringBuilder sb = new StringBuilder();
    sb.append("[").append("name = ").append(this.name).append(", ").append("age = ").append(this.age);
    if (address != null)
      sb.append(", address = ").append(this.address.toString());
    sb.append("]");
    return sb.toString();
   }

  @Override
  public Object clone() throws CloneNotSupportedException {
    return super.clone();
   }
}

浅仿制测验类

/**
 * 浅仿制
 */
static class Cloneable02 {
  public static void main(String[] args) throws CloneNotSupportedException {
    Address address = new Address("北京");
    User user1 = new User("张", 12, address);

    User user2 = (User)user1.clone();
    System.out.println(user1);
    System.out.println(user2);
    System.out.println(user1 == user2);

    System.out.println(user2.getAddress() == user1.getAddress());

    address.setCity("海口");
    user1.setAddress(address);
    System.out.println(user1);
    System.out.println(user2);
   }
}
//[name = 张, age = 12, address = 北京]
//[name = 张, age = 12, address = 北京]
//false
//true
//[name = 张, age = 12, address = 海口]
//[name = 张, age = 12, address = 海口]

从输出成果能够得知User类的基本数据类型能够到达彻底仿制，引证数据类型却不能够。

原因在于在User目标user1被克隆的时分，其特点address作为引证类型仅仅是仿制了一份引证，两者指向的地址仍是一致的。因而当address的值产生改动时，被克隆目标user2的特点address的值也会改动。

深仿制

修正Address类，如下所示

public class Address implements Serializable, Cloneable {
  public final long serialVersionUID = 1578511564815489L;
  
  // getter setter toString...
  
  @Override
  public Object clone() throws CloneNotSupportedException {
    return super.clone();
   }
}

Address类完成Cloneable接口，并重写 Object.clone() 办法。

修正User类如下所示

public class User implements Serializable, Cloneable {
  
  // 特点 setter getter toString...
  
  /**
   * 调用引证目标的clone()，完成深仿制
   *
   * @return
   * @throws CloneNotSupportedException
   */
  @Override
  public Object clone() throws CloneNotSupportedException {
    User user = (User) super.clone();
    Address address = (Address) this.address.clone();
    user.setAddress(address);
    return user;
   }
}

之前重写的super.clone()是不能仿制引证目标的，那么调用Address类的clone() 办法，仿制address特点后再赋值给user目标。

深仿制测验类

/**
 * 深仿制 完成地方在User、Address类
 */
static class Cloneable03 {
  public static void main(String[] args) throws CloneNotSupportedException {
    Address address = new Address("北京");
    User user1 = new User("张", 12, address);

    User user2 = (User) user1.clone();
    System.out.println(user1);
    System.out.println(user2);
    System.out.println(user1 == user2);

    System.out.println(user2.getAddress() == user1.getAddress());

    address.setCity("海口");
    user1.setAddress(address);
    System.out.println(user1);
    System.out.println(user2);
   }
}
//[name = 张, age = 12, address = 北京]
//[name = 张, age = 12, address = 北京]
//false
//false
//[name = 张, age = 12, address = 海口]
//[name = 张, age = 12, address = 北京]

测验类没有代码修正，首要修正在User、Address类。

从输出成果来看，现已完成对address引证目标的深仿制。

ArrayList源码

结构办法

public class ArrayList<E> extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
  // 默许长度为0的数组
  private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
  // 存储 ArrayList 元素的数组缓冲区。 ArrayList 的容量便是这个数组缓冲区的长度。
  transient Object[] elementData;
  // 给elementData赋值
  public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
   }

}

经过无参结构办法创立调集目标，仅仅将DEFAULTCAPACITY_EMPTY_ELEMENTDATA （一个默许长度为0的数组）的地址赋值给elementData（存储ArrayList元素的数组缓冲区）

public class ArrayList<E> extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
  // 用于空实例的同享空数组实例。
  private static final Object[] EMPTY_ELEMENTDATA = {};
  // 结构一个具有指定初始容量的空列表。
  public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
      // 长度大于0，创立指定长度的数组
      this.elementData = new Object[initialCapacity];
     } else if (initialCapacity == 0) {
      // 长度为0，将空数组的地址赋值给elementData
      this.elementData = EMPTY_ELEMENTDATA;
     } else {
      throw new IllegalArgumentException("Illegal Capacity: "+
                        initialCapacity);
     }
   }
}

依据 ArrayList 结构办法参数创立指定长度的数组，假如指定长度等于0，直接给elementData赋值EMPTY_ELEMENTDATA（空数组实例）

public class ArrayList<E> extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
  // 依照调集的迭代器回来的次序结构一个包括指定调集元素的列表
  public ArrayList(Collection<? extends E> c) {
    // 转成数组
    Object[] a = c.toArray();
    if ((size = a.length) != 0) {
      if (c.getClass() == ArrayList.class) {
        elementData = a;
       } else {
        elementData = Arrays.copyOf(a, size, Object[].class);
       }
     } else {
      // replace with empty array.
      elementData = EMPTY_ELEMENTDATA;
     }
   }
  // 完成Collection接口
  public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
   }
}


class Arrays {
  // 仿制指定的数组，切断或填充空值（如有必要），使副本具有指定的长度。
  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) {
    @SuppressWarnings("unchecked")
    // 不论三元运算符的成果怎么,都会创立一个新的数组
    // 新数组的长度一定是和调集的size相同
    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;
   }
  // 创立具有指定组件类型和长度的新数组。
  public static Object newInstance(Class<?> componentType, int length)
    throws NegativeArraySizeException {
    return newArray(componentType, length);
   }
}

运用ArrayList<User> userList = new ArrayList<User>(list)结构一个调集时，会进入到此结构办法，经过一个三目表达式判别是构建一个Object调集还是newType中元素类型的调集。

`add()`办法

增加单个元素

public class ArrayList<E> extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
  // ArrayList的巨细
  private int size;
  // 默许巨细为空的实例，同享空数组实例
  private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
  // 调集存元素的数组
  Object[] elementData;
  // 默许的容量
  private static final int DEFAULT_CAPACITY = 10;
  // 数组的最大巨细，2^31-1-8 = 2147483647-8，一些 VM 在数组中保存一些标题字。测验分配更大的数组可能会导致 OutOfMemoryError：请求的数组巨细超过 VM 限制
  private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
  
  // 将指定元素附加到此列表的结尾
  public boolean add(E e) {
    // 每次增加元素之前先动态调整数组巨细，避免溢出
    ensureCapacityInternal(size + 1); // Increments modCount!!
    // 每次都会把新增加的元素放到数组结尾,ArrayList次序寄存的原因
    elementData[size++] = e;
    return true;
   }
  
  private void ensureCapacityInternal(int minCapacity) {
    // 这儿会判别下当时ArrayList是否为空，为空则先初始化数组，
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
   }
  // 核算ArrayList容量，这儿能够看到当ArrayList为空，且第一次向容器增加元素时，会对ArrayList进行扩容，最小容量为10。
  private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // 假如当时容器为空，那么获取初始化数组的巨细，数组巨细不能小于DEFAULT_CAPACITY（10）
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // 默许容量为空的数组
      return Math.max(DEFAULT_CAPACITY, minCapacity);
     }
    return minCapacity;
   }

  private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // 假如当时元素数量到达了容器上限，就对容器进行扩容
    if (minCapacity - elementData.length > 0)
      grow(minCapacity);
   }

  private void grow(int minCapacity) {
    // oldCapacity为当时容器巨细
    int oldCapacity = elementData.length;
    // 扩容的中心算法，扩容为原容量的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 由于第一次容器有可能为空，elementData.length==0，newCapacity会小于minCapacity
    if (newCapacity - minCapacity < 0)
      newCapacity = minCapacity;
    // newCapacity不能大于MAX_ARRAY_SIZE，由于数组能分配的最大空间便是Integer.MAX_VALUE，
    if (newCapacity - MAX_ARRAY_SIZE > 0)
      newCapacity = hugeCapacity(minCapacity);
     // 确认好数组巨细后，对数组进行仿制，Arrays.copyOf的底层是一个native(非Java完成)办法。
    elementData = Arrays.copyOf(elementData, newCapacity);
   }
  // 有些VM会在数组中保存一些标题字，当仍需求更大容量时，则会赋予Integer.MAX_VALUE；当超出时会溢出，报错OOM。
  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 void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1); // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
             size - index);
    elementData[index] = element;
    size++;
   }

增加元素的时分，首先都要查看扩容，在add(int index, E element)办法中多一步操作，便是将指定方位今后的一切元素向后移动一位，留出当时方位用来寄存增加的元素。

将调集的一切元素一次性增加到调集


  public boolean addAll(Collection<? extends E> c) {
    //把有数据的调集转成数组
    Object[] a = c.toArray();
    //有数据调集长度赋值给numNew
    int numNew = a.length;
    //校验以及扩容
    ensureCapacityInternal(size + numNew); // Increments modCount
    //真实仿制的代码
    System.arraycopy(a, 0, elementData, size, numNew);
    //调集的长度进行更改
    size += numNew;
    //依据numNew的值回来是否增加成功
    return numNew != 0;
   }

  public boolean addAll(int index, Collection<? extends E> c) {
    //校验索引
    rangeCheckForAdd(index);
    //将数据源转成数组
    Object[] a = c.toArray();
    //记载数据源的长度 3
    int numNew = a.length;
    //意图便是为了给调集存储数据的数组进行扩容
    ensureCapacityInternal(size + numNew);

    //numMoved:代表要移动元素的个数 --> 1个
    //numMoved: 数据意图(调集list1)的长度-调用addAll的第一个参数 (索引1)
    int numMoved = size - index;
    //判别需求移动的个数是否大于0
    if (numMoved > 0)
      //运用System中的办法arraycopy进行移动
      System.arraycopy(elementData, index, elementData, index + numNew,
               numMoved);
    //才是真实将数据源(list)中的一切数据增加到数据意图(lsit1)
    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
   }

addAll办法原理也是相同的，多了一步将调集元素增加进程。

`set`办法

  public E set(int index, E element) {
    //校验索引
    rangeCheck(index);
    //依据索引取出元素 --> 被替换的元素
    E oldValue = elementData(index);
    //把element存入到elementData数组中
    elementData[index] = element;
    //回来被替换的元素
    return oldValue;
   }
  private void rangeCheck(int index) {
    if (index >= size)
      throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
   }

set办法依据索引将元素取出后，再数组中元素替换掉。

`get`办法


  public E get(int index) {
    //校验索引
    rangeCheck(index);
    //依据索引获取数组(调集)中的元素
    return elementData(index);
   }

get办法依据索引将元素取出后，直接回来。

`remove`办法

remove单个元素

  // 移除此列表中指定方位的元素。将任何后续元素向左移动（从它们的索引中减去 1）
  public E remove(int index) {
    // 索引范围判别，超出报IndexOutOfBoundsException
    rangeCheck(index);
    // 操作数自增1
    modCount++;
    // oldValue记载index索引当时值
    E oldValue = elementData(index);
    // 核算调集需求移动元素的个数
    int numMoved = size - index - 1;
    if (numMoved > 0)
      // 进行数组仿制，把索引位index后的元素向前移动一位
      System.arraycopy(elementData, index+1, elementData, index,
               numMoved);
    // 把调集最终一位元素赋null，尽早让废物收回机制收回
    elementData[--size] = null; // clear to let GC do its work
    // 将记载的原索引位元素值回来
    return oldValue;
   }

  // 从此列表中删去第一次呈现的指定元素（假如存在）。假如列表不包括该元素，则它不变。
  public boolean remove(Object o) {
    if (o == null) {
      for (int index = 0; index < size; index++)
        // 用==比较null元素
        if (elementData[index] == null) {
          fastRemove(index);
          return true;
         }
     } else {
      for (int index = 0; index < size; index++)
        // 用equals比较非null元素
        if (o.equals(elementData[index])) {
          fastRemove(index);
          return true;
         }
     }
    // 不存在该元素，不修正本列表，直接回来false
    return false;
   }
  // 私有办法，删去元素省去了索引范围判别，且不需求回来原值，直接进行数组仿制
  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 boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, false);
   }

  // 仅保存此列表中包括在指定调集中的元素。换句话说，从这个列表中删去一切不包括在指定调集中的元素。
  public boolean retainAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, true);
   }
  // 批量删去调集元素
  private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;
    boolean modified = false;
    try {
      for (; r < size; r++)
        // 判别调集包括元素，删去调集c外的其他元素
        if (c.contains(elementData[r]) == complement)
          elementData[w++] = elementData[r];
     } finally {
      // Preserve behavioral compatibility with AbstractCollection,
      // even if c.contains() throws.
      // 当r!=size时，判定上一步呈现反常，需求将之前修正过的数组再还原
      if (r != size) {
        System.arraycopy(elementData, r,
                 elementData, w,
                 size - r);
        w += size - r;
       }
      if (w != size) {
        // clear to let GC do its work
        for (int i = w; i < size; i++)
          elementData[i] = null;
        modCount += size - w;
        size = w;
        modified = true;
       }
     }
    return modified;
   }

removeAll和retainAll经过调用的办法是一个，仅经过一个开关完成截然相反的操作，

从Java源码上分析为什么`LinkedList`随机拜访比次序拜访要慢这么多？

// 随机拜访
for(int i=0;i<list.size();i++) {
  list.get(i);
}
// 次序拜访
Iterator<E> it = list.iterator();
while(it.hasNext()){
  it.next();
}

LinkedList的get()办法源码

public class LinkedList<E>
  extends AbstractSequentialList<E>
  implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
  // 回来此列表中指定方位的元素。
  public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
   }
  
  // 判别参数是否是现有元素的索引。
  private void checkElementIndex(int index) {
    if (!isElementIndex(index))
      throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
   }
  private boolean isElementIndex(int index) {
    return index >= 0 && index < size;
   }
  
  // ArrayList 的巨细
  private int size;
  // 存储 ArrayList 元素的数组缓冲区。
  transient Object[] elementData;
  // 回来指定元素索引处的（非空）节点。
  Node<E> node(int index) {
    // assert isElementIndex(index);
    if (index < (size >> 1)) {
      Node<E> x = first;
      // index小于长度一半时，是从链表头部往后找
      for (int i = 0; i < index; i++)
        x = x.next;
      return x;
     } else {
      Node<E> x = last;
      // index大于长度一半时，是从链表尾部往前找
      for (int i = size - 1; i > index; i--)
        x = x.prev;
      return x;
     }
   }

随机拜访运用list.get(i)办法，从源码中咱们能够得知，每次list.get(i)都遍历找到该元素方位再回来，当咱们需求遍历一次list，其实list.get(i)会遍历很多次，做了重复性作业。

list.iterator()源码

Iterator<E> it = list.iterator();

// AbstractList为LinkedList父类的父类
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
  // 回来此列表中元素的列表迭代器（以正确的次序）。
  public Iterator<E> iterator() {
    return listIterator();
   }
  // 回来参数为0的列表迭代器
  public ListIterator<E> listIterator() {
    return listIterator(0);
   }
}

public class LinkedList<E>
  extends AbstractSequentialList<E>
  implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
  public ListIterator<E> listIterator(int index) {
    checkPositionIndex(index);
    return new ListItr(index);
   }
  
  // 查看index范围
  private void checkPositionIndex(int index) {
    if (!isPositionIndex(index))
      throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
   }
  private boolean isPositionIndex(int index) {
    return index >= 0 && index <= size;
   }
  
  // LinkedList迭代器完成类
  private class ListItr implements ListIterator<E> {
    private Node<E> lastReturned;
    private Node<E> next;
    private int nextIndex;
    // 将实践修正调集次数赋值给预期修正次数
    private int expectedModCount = modCount;

    ListItr(int index) {
      // 判别 0 == size,实践上便是调用 node(index)办法
      next = (index == size) ? null : node(index);
      // 将index的值赋值给 nextIndex,便于下次查找
      nextIndex = index;
     }
    // 判别nextIndex是否在范围内
    public boolean hasNext() {
      return nextIndex < size;
     }
    // 获取下一个元素
    public E next() {
      // 查看调集实践修正次数和预期次数是否相同
      checkForComodification();
      // 再次判别是否有元素
      if (!hasNext())
        throw new NoSuchElementException();
      lastReturned = next;
      next = next.next;      
      nextIndex++;
      return lastReturned.item;
     }
    // 查看调集实践修正次数和预期次数是否相同
    final void checkForComodification() {
      if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
     }
   }
  
  // 在获取迭代器的时分也会进行减半判别的进程，但index=0
  Node<E> node(int index) {
    if (index < (size >> 1)) {
      // 但是在获取迭代器的时分 index 一定是0,因而 if 的条件建立
      Node<E> x = first;
      for (int i = 0; i < index; i++)
        x = x.next;
      // index=0 直接回来第一个元素
      return x;
     } else {
      Node<E> x = last;
      for (int i = size - 1; i > index; i--)
        x = x.prev;
      return x;
     }
   }
}

从迭代器源码中咱们得知，在进行次序拜访时，只在第一次，index=0时进行了一个减半判别，此后依照次序顺次向后传递获取元素，实践只进行了一次遍历进程。由此可见，LinkedList的次序遍历比随机遍历快很多。

JDK源码阅读：ArrayList原理

`ArrayList`原理

`ArrayList`调集底层数据结构

`ArrayList`继承联系

`Serializable`序列化接口

`RandomAccess`随机拜访

Cloneable克隆接口

一般类支撑 `Object.clone()` 办法

浅仿制

深仿制

ArrayList源码

结构办法

`add()`办法

`set`办法

`get`办法

`remove`办法

从Java源码上分析为什么`LinkedList`随机拜访比次序拜访要慢这么多？

作者信息

JDK源码阅读：ArrayList原理

ArrayList原理

ArrayList调集底层数据结构

ArrayList继承联系

Serializable序列化接口

RandomAccess随机拜访

Cloneable克隆接口

一般类支撑 Object.clone() 办法

浅仿制

深仿制

ArrayList源码

结构办法

add()办法

set办法

get办法

remove办法

从Java源码上分析为什么LinkedList随机拜访比次序拜访要慢这么多？

相关文章

计算机视觉的 基础学习

Android 绘制循环菜单

造轮子：滚轮选择器实现及原理解析(一)

成长初期的程序员一定会遇到的问题，我是如何解决并完成认知转变的

作者信息

`ArrayList`原理

`ArrayList`调集底层数据结构

`ArrayList`继承联系

`Serializable`序列化接口

`RandomAccess`随机拜访

一般类支撑 `Object.clone()` 办法

`add()`办法

`set`办法

`get`办法

`remove`办法

从Java源码上分析为什么`LinkedList`随机拜访比次序拜访要慢这么多？

计算机视觉的基础学习