对比

ArrayList

• ArrayList 允许存放任意值，包括 null，允许重复(List 接口特点)；
• ArrayList 底层是用数组实现数据存储的；

• ArrayList 基本等同于 Vector，区别是 ArrayList 是线程不安全的(执行效率高)，多线程下不推荐使用；

  源码分析: 初始化及扩容

• ArrayList 维护了一个 Object 类型的数组 elementData 来存储元素；

• 使用无参构造器创建 ArrayList 对象时，初始 elementData 数组容量为 0，第一次添加时扩容为 10，当容量不够时扩容为原来的 1.5 倍；
• 使用指定容量大小的构造器创建对象，初始 elementData 数组容量为指定大小，需要扩容时则扩容为原来的 1.5 倍；

关键属性

// 存储元素的数组 transient 表示该属性不会被序列化
transient Object[] elementData; // non-private to simplify nested class access
// The size of the ArrayList (the number of elements it contains).
private int size;

构造器

// 无参构造器
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 指定大小的有参构造器
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
    }
}

1. 添加元素

   public boolean add(E e) {
    // 确认数组容量是否足够添加元素
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
   }

2. 确定 minCapacity，

• 如果 elementData 数组初始为空时，初始化为 10；

• 如果elementData已经初始化，minCapacity 代表存放当前集合元素需要的最小空间（即 size + 1），判断 elementData 数组长度是否足够存放，决定是否要扩容。

  // 计算容量
  private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // DEFAULT_CAPACITY = 10
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
  }
  private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, 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);
  }
  

  存疑 计算容量时判断 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) elementData 为空数组，为什么还要 执行Math.max(DEFAULT_CAPACITY, minCapacity)，不直接默认赋值为10？

// 计算容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // DEFAULT_CAPACITY = 10
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

overflow-conscious code

这里是指考虑溢出。
问：a < b 和 a - b<0代表相同的含义吗？
答：在计算机中不同，因为数字用的是有限位的补码，也正是因此才会有考虑溢出的代码。
参考：https://blog.csdn.net/lijianqingfeng/article/details/107912190
参考：https://stackoverflow.com/questions/33147339/difference-between-if-a-b-0-and-if-a-b

Vector

• 存储数据特性与 ArrayList 类似；
• 线程同步，即线程安全，操作方法前带有 synchronized 关键字；
• 底层是用数组 elementData 来实现数据存储的；
• 无参构造器创建对象，初始大小为 10，每次扩容为原来的 2 倍；

• 有参构造器创建对象，初始大小为指定的参数值，扩容为原来的 2 倍，或者增加指定的值；

  构造器

  public Vector() {
    this(10);
  }
  public Vector(int initialCapacity) {
    this(initialCapacity, 0);
  }
  public Vector(int initialCapacity, int capacityIncrement) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
    this.elementData = new Object[initialCapacity];
    this.capacityIncrement = capacityIncrement;
  }
  

  添加元素

  public synchronized void addElement(E obj) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = obj;
  }
  

  扩容

  private void ensureCapacityHelper(int minCapacity) {
    // 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 + ((capacityIncrement > 0) ?
                                     capacityIncrement : oldCapacity);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
  }
  

  LinkedList

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

• LinkedList 实现了双向链表和双向队列；

• 可以添加任意元素，可以为null，可重复；
• 线程不安全，没有实现同步；
• LinkedList 底层维护了一个双向链表；
• LinkedList 中维护了两个属性 first 和 last 分别指向首结点和尾结点；
• 每个结点（Node 对象）里面又维护了 prev、next、item 三个属性，其中通过 prev 指向前一个，通过 next 指向后一个结点。

• LinkedList 中元素的添加和删除，相对数组来说效率较高；

  初始化

• 节点属性 ```java transient int size = 0;

/**

• Pointer to first node.
• Invariant: (first == null && last == null) || (first.prev == null && first.item != null) */ transient Node first;

/**

• Pointer to last node.
• Invariant: (first == null && last == null) || (last.next == null && last.item != null) */ transient Node last; ```

• 构造器

  /**
  * Constructs an empty list.
  */
  public LinkedList() {
  }
  

  构造器初始化一个空的双向链表，此时结点 first、last 为 null，链表长度 size = 0；

  队列和链表方法

  由于 LinkedList 是 List 和 Deque 接口的双链接列表实现，所以提供了一系列队列和链表的相关操作方法：

链表属性