ArrayList

  • 默认初始数组长度为10
  • 扩容的长度为： 旧数组长度的1.5倍 （Java官方是1.5 IOS是1.6）
    • int newCapacity = oldCapacity + (oldCapacity >>1);
    • 扩容所在的方法是add();
  • 加入泛型后 申请数组变为：
    • elements = (T[ ])new Object[capacity];
  • 缩容：
    • 缩容所在的方法是remove();
    • 比如剩余空间占总容量的一半时进行缩容
    • 例如，缩容后的容量为总容量的一半或者3/4

链表（LinkedList）

image.png

  • 定义接口List实现ArrayList 与 LinkedList的所有function ， 定义一个抽象类的父类 AbstractList来实现两者公共部分。AbstractList implements List 。
  • ELEMENT_NOT_FONT 等常量需要放在List中，而不是ArrayList 。

虚拟头结点

image.png

双向链表

image.png

  • clear()
    • 当令first = null ， last = null 后，原先的Node对象会被清空，即使Node节点在互相调用。
      • 因为Java中有一个gc root对象，只要不被它引用，就会被回收。gc root对象有：
        • 被栈指针（局部对象）指向的对象 （ 新new出来的对象在堆空间中，用局部变量指向堆空间中的新对象）

          静态链表

          image.png