List

3.List接口

List 接口继承 Collection 接口，是有序，可以重复的集合；集合中每个元素都有其对应的顺序索引，索引从 0 开始，可以包含多个null。

public interface List<E> extends Collection<E> {}

接口方法

List 除了使用 Collection 继承的 Iterator 迭代器外，还有一个 ListIterator 迭代器。该迭代器拥有针对于 List 的额外方法：

List 接口遍历还可以使用普通 for 循环（索引方式）进行遍历。

4.Arraylist

• 底层维护一个Object类型的数组elementData，transient Object[] elementData
• 创建对象时，如果使用无参构造，则初始化elementData容量为0；第一次add添加时，则扩容elementData容量为10；如需要再次扩容时，则扩容elementData容量为1.5倍
• 创建对象时，如果使用指定大小构造器，则初始化elementData容量为指定大小；如需要扩容时，则直接扩容elementData容量为原大小的1.5倍
• 扩容使用Arrays.coppyof()方法
• 线程不安全，效率高；插删效率低，改查效率高
• jdk1.2

构造

//存储元素的数组 transient 表示该属性不会被序列化
transient Object[] elementData; 
// the number of elements it contains
private int size;//集合的大小
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};//默认容量的空数组
private static final Object[] EMPTY_ELEMENTDATA = {};//空数组

// 无参构造器 初始化elementData容量为0
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);
    }
}

add(E e)

private static final int DEFAULT_CAPACITY = 10;//默认初始容量
private static final Object[] EMPTY_ELEMENTDATA = {};
public boolean add(E e) {
    // 确认数组容量是否足够添加元素，size=0
    ensureCapacityInternal(size + 1); 
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    //返回前集合元素需要的最小空间与10的最大值
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//
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 ensureExplicitCapacity(int minCapacity) {
    modCount++;// 记录当前集合被修改的次数, 防止多线程同时修改
    // overflow-conscious code
    //minCapacity代表存放当前集合元素需要的最小空间（即 size + 1），判断 elementData 数组长度是否足够存放，决定是否要扩容
        grow(minCapacity);// 扩容方法
}

private void grow(int minCapacity) {
    // overflow-conscious code
    ////记录数组的实际长度,此时由于木有存储元素,长度为0
    int oldCapacity = elementData.length;
    ////核心扩容算法 原容量的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    //// 调用数组工具类方法,创建一个新数组,将新数组的地址赋值给elementData
    elementData = Arrays.copyOf(elementData, newCapacity);
}

remove(Object o)

public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            ////判断集合的元素是否为null
            if (elementData[index] == null) {
                //如果相等,调用fastRemove方法快速删除
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            //用o对象的equals方法和集合每一个元素进行比较
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    //如果集合没有o该元素,那么就会返回false
    return false;
}
private void fastRemove(int index) {
    modCount++;
    //计算集合需要移动元素的个数
    int numMoved = size - index - 1;
    ////如果需要移动的个数大于0,调用arrayCopy方法进行拷贝
    if (numMoved > 0)   
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--size] = null; // clear to let GC do its work
}

get(int index)

public E get(int index) {
    rangeCheck(index);//范围校验

    return elementData(index);//直接根据索引取出集合元素
}
private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

12.遍历 ArrayList 时移除一个元素

//创建集合对象
List<String> list = new ArrayList<String>();
//添加元素
list.add("hello");
list.add("Java");
list.add("PHP");
//获取迭代器
Iterator<String> it = list.iterator();
//遍历集合
while (it.hasNext()) {
    String s = it.next();
    if(s.equals("PHP")) {
        list.remove("PHP");
    }
}//java.util.ConcurrentModificationException

//创建集合对象
List<String> list = new ArrayList<String>();
//添加元素
list.add("hello");
list.add("PHP");
list.add("Java");

//获取迭代器
Iterator<String> it = list.iterator();
//遍历集合
while (it.hasNext()) {
    String s = it.next();
    if(s.equals("PHP")) {
        list.remove("PHP");
    }
}//[hello，java] 集合size2，cursor也是2  删除的元素不是最后一个不会引发并发修改异常

public Iterator<E> iterator() {
    return new Itr();
}
//ArrayList内部类
//一定要注意观察 Itr 类中的几个成员变量
private class Itr implements Iterator<E> {
    int cursor; // 下一个要返回元素的索引
    int lastRet = -1; // 最后一个返回元素的索引
//将实际修改集合次数 赋值 给预期修改次数，在迭代的过程中,只要实际修改次数和预期修改次数不一致就会产生并发修改异常由于expectedModCount是Itr的成员变量,那么只会被赋值一次!!!同时由于集合调用了三次add方法,那么实际修改集合次数就是 3,因此expectedModCount的值也是 3
    int expectedModCount = modCount;
    public boolean hasNext() {
        return cursor != size;
    }
//获取元素的方法
public E next() {
//每次获取元素,会先调用该方法校验 预期修改次数是否 == 实际修改次数
    checkForComodification();
//把下一个元素的索引赋值给i
    int i = cursor;
//判断是否有元素
    if (i >= size)
        throw new NoSuchElementException();
//将集合底层存储数据的数组赋值给迭代器的局部变量 elementData
    Object[] elementData = ArrayList.this.elementData;
//再次判断,如果下一个元素的索引大于集合底层存储元素的长度 并发修改异常。注意,尽管会产生并发修改异常,但是这里显示不是我们要的结果
    if (i >= elementData.length)
        throw new ConcurrentModificationException();
//每次成功获取到元素,下一个元素的索引都是当前索引+1
    cursor = i + 1;
//返回元素
    return (E) elementData[lastRet = i];
}
final void checkForComodification() {
    //如果预期修改次数 和 实际修改次数不相等 就产生并发修改异常
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    }
}

迭代器中的remove方法,删除集合中的元素。

• 迭代器remove方法底层调用的还是集合自身的remove方法删除元素
• 迭代器之所以不会产生并发修改异常，其原因是因为在迭代器的remove方法中会再次将 集合时机修改次数赋值给预期修改次数

Iterator itr = list.iterator();
while(itr.hasNext()) {
      if(itr.next().equals("jay") {
        itr.remove();
      }
}

倒叙遍历删除

for(int i=list.size()-1; i>-1; i--){
  if(list.get(i).equals("jay")){
    list.remove(list.get(i));
  }
}

5.LinkedList

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

链表方法

• 实现了双向链表和双向队列
• 底层维护一个双向链表，其中first和last属性分别指向首节点和尾节点。每个节点（Node对象）里面维护了prev、next、item三个属性，其中prev和next分别指向前一个和后一个节点，item属性存放值
• 线程不安全，效率高；插删效率高，改查效率低

构造

transient int size = 0;
//首节点和尾节点
transient Node<E> first;
transient Node<E> last;
//节点（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;
    }
}
//初始化一个空的双向链表，此时结点 first、last 为 null，链表长度 size = 0
public LinkedList() {
}

add(E e)

public boolean add(E e) {    linkLast(e);    return true;}void linkLast(E e) {    //    final Node<E> l = last;    //new一个加入的节点    final Node<E> newNode = new Node<>(l, e, null);    //将新节点赋给尾节点    last = newNode;    //如果尾节点是null，则将新节点赋给首节点，否则将原先尾节点指向新节点，同时size++    if (l == null)        first = newNode;    else        l.next = newNode;    size++;    modCount++;}

remove()

public E remove() {
    return removeFirst();//移除第一个
}
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}
private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

get (int index)

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}
private void checkElementIndex(int index) {
    if (!isElementIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

6.Vector

• 底层维护一个Object类型的数组elementData，protected Object[] elementData
• 如果无参，默认10个，每次按2倍扩容
• 如果指定大小，每次直接扩容2倍
• 扩容使用Arrays.coppyof()方法
• 线程安全（操作方法前带有 synchronized 关键字），效率低；插删效率低，改查效率高
• Jdk1.0

构造

protected Object[] elementData;
protected int elementCount;
protected int capacityIncrement;
public Vector() {
    //无参默认10个
    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;
}

add()

public synchronized boolean add(E e) {
    modCount++;//记录当前集合被修改的次数
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

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

remove(int index)

public synchronized E remove(int index) {
    modCount++;
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);
    E oldValue = elementData(index);

    int numMoved = elementCount - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--elementCount] = null; // Let gc do its work

    return oldValue;
}

7.Stack

Stack继承自Vector。

public
class Stack<E> extends Vector<E> {}

构造

public Stack() {
}

push(E item)

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

pop()

public synchronized E pop() {
    E       obj;
    int     len = size();

    obj = peek();
    removeElementAt(len - 1);

    return obj;
}
public synchronized E peek() {//返回stack中最顶端的元素。
    int     len = size();

    if (len == 0)
        throw new EmptyStackException();
    return elementAt(len - 1);
}
public synchronized E elementAt(int index) {
    if (index >= elementCount) {
        throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
    }

    return elementData(index);
}
E elementData(int index) {
    return (E) elementData[index];
}

参考

ArrayList原理.pdf