list总结

//无参的构造函数得到的是一个空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

public () {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

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

public (Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
		// c.toArray might (incorrectly) not return Object[]
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

/**
 * @param src      源数组
 * @param srcPos   源数组中的起始位置
 * @param dest     目标数组
 * @param destPos  指定目标数据中的起始位置
 * @param length   要复制的数组元素的数量.
 */
public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

/**
 * @param original 	要复制的数组
 * @param newLength 要返回的副本的长度
 * @param newType 	要返回的副本的类型
 */
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        ("unchecked")
        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;
    }

//执行顺序1.
//size默认值是0
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

//2.其实是执行3和4的方法
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

//3.
/**
  * 这个方法是计算list的容量的:
  *    上面add方法调用的时候会传入(size+1)到这个计算的方法中
  *    如果当前的数组是空数组,那么就比较(size+1)与默认的容量(默认是10),取较大的值返回.
  *    如果不是空数组,那么直接返回(size+1)
  */
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        //默认容量DEFAULT_CAPACITY是10
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

//4.
/**
  * 因为是add操作,对列表结构有改动,需要modCount++
  * 如果传入的(size+1)值大于当前数组的长度的时候,才对此数组进行扩容的操作
  */
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

//5.如果是超过当前数组长度才需要进行数组扩容的操作
/**
 * 如果新数组大小还是小于传入的容量的话,那就直接取传入的容量作为新数组的长度
 * 如果新数组的长度要比最大定义的数组长的话
 *      (最大的数组长度是Integer.MAX_VALUE-8)
 *      那么就直接使用Integer.MAX_VALUE作为数组的长度.
 * 然后就将数组的元素拷贝到一个新的数组中
 */
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    //右移1位，此处得到新容量是旧容量的1.5倍
    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);
}

//插入到index的下标的位置,然后返回旧的值
public E set(int index, E element) {
    //判断传入的下标是否越界
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

public E get(int index) {
    //判断传入的下标是否越界
    rangeCheck(index);
    return elementData(index);
}

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);
    //更新列表的元素个数,清除最后一个元素,让GC回收
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

public boolean remove(Object o) {
    //移除null值元素
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        //for循环遍历列表,根据对象的equals方法来移除对应元素
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    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) {
    //如果参数为null,那么抛出异常
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}

private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;
    boolean modified = false;
    try {
        //注意此处的complement是false
        //所以就是将elementData中不存在c中的元素留下
        for (; r < size; r++)
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        //这里的判断的原因是因为 contains 方法可能会抛出异常
        //如果抛出异常的情况下,就需要对 elementData 进行处理
        if (r != size) {
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        //这里很简单,清除元素,修改 modCount 的值,然后返回true
        if (w != size) {
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

public Iterator<E> iterator() {
    return new Itr();
}

//是否还有下一个可遍历的元素
public boolean hasNext() {
    return cursor != size;
}

public E next() {
    checkForComodification();
    int i = cursor;
    //这里都是判断下标是否越界
    if (i >= size)
        throw new NoSuchElementException();
    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();
}

public void remove() {
    //这个地方就是为什么需要先执行 next 方法后才能调用 remove 方法的原因
    if (lastRet < 0)
        throw new IllegalStateException();
    //在移除元素之前，需要先判断列表结构是否被修改过
    checkForComodification();

    try {
        //调用arrayList的remove方法
        ArrayList.this.remove(lastRet);
        //重置一下游标,因为 next 操作里面将游标+1了
        cursor = lastRet;
        lastRet = -1;
        //更新结构修改次数，上面调用remove方法导致modCount增加了
        expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}

/**
  * List的遍历方式
  */
public void cycleList() {
    Integer[] ints = {1,2,3,4,5,6,7,8,9};
    // Arrays.asList(ints) 将数组转成List
    List<Integer> lists = Arrays.asList(ints);
    /**
      * 1.for循环遍历
      *
      * foreach循环(增强for循环)
      */
    for (int i = 0;i < lists.size();i++) {
        System.out.println(lists.get(i));
    }
    for (Integer i : lists) {
        System.out.println(i);
    }


    /**
      * 2.迭代器遍历
      */
    Iterator<Integer> iterator = lists.iterator();
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
    }

    /**
      * 3.JDK8的stream流方式
      */
    lists.stream().forEach(System.out::println);
}

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

//不包含toIndex下标的元素，即左闭右开
public List<E> subList(int fromIndex, int toIndex) {
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList(this, 0, fromIndex, toIndex);
}
SubList(AbstractList<E> parent,
        int offset, int fromIndex, int toIndex) {
    this.parent = parent;
    this.parentOffset = fromIndex;
    this.offset = offset + fromIndex;
    this.size = toIndex - fromIndex;
    this.modCount = ArrayList.this.modCount;
}

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

public LinkedList() {
}

//调用addAll方法，这个下面详说
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

//添加元素到链表末尾
//将元素包装成Node节点,然后就是链表的操作了
//	如果尾节点是空的,那么将该节点作为头和尾节点
//	如果尾节点非空,那么将该节点作为尾节点,并且加入到链表中
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++;
}
//添加元素到链表头
private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}
//链表操作,将 e 插入到 succ 前面
void linkBefore(E e, Node<E> succ) {
    // succ 不能为null
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        //即succ是头节点的情况
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}
/**
 * 采用折半法得到index所在的位置(左/右区间)
 * 然后采用for循环遍历的方式得到index位置上的元素
 */
Node<E> node(int index) {
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        //注意：这里是从后往前遍历
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

public boolean add(E e) {
    //插入链表的末尾
    linkLast(e);
    return true;
}

public void add(int index, E element) {
    //检查下标是否越界
    checkPositionIndex(index);
	
    if (index == size)
        //添加到链表最后,即调用上面的add(E e)方法
        linkLast(element);
    else
        //插入node(index)节点之前
        linkBefore(element, node(index));
}
//检查下标是否越界和index是否小于0
private void checkPositionIndex(int index) {
    if (!isPositionIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isPositionIndex(int index) {
    return index >= 0 && index <= size;
}

public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
    //检查下标是否越界
    checkPositionIndex(index);
	//得到指定插入的元素
    Object[] a = c.toArray();
    int numNew = a.length;
    if (numNew == 0)
        return false;
	//获取插入位置的前驱和后继节点
    Node<E> pred, succ;
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        succ = node(index);
        pred = succ.prev;
    }
	//for循环插入指定元素,并且设置好上面的前驱和后继节点
    for (Object o : a) {
        E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null);
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        pred = newNode;
    }
    if (succ == null) {
        last = pred;
    } else {
        pred.next = succ;
        succ.prev = pred;
    }
    size += numNew;
    modCount++;
    return true;
}

//返回头节点元素内容
public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}
//返回尾节点元素内容
public E getLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}
//获取指定下标的元素
public E get(int index) {
    checkElementIndex(index);
    //折半for循环查找指定下标的元素
    return node(index).item;
}
//检查下标是否越界和index是否小于0
private void checkElementIndex(int index) {
    if (!isElementIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isElementIndex(int index) {
    return index >= 0 && index < size;
}

//要求参数 x 不能为null
E unlink(Node<E> x) {
    //得到需要删除节点的内容、前驱节点和后继节点
    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;
}

private E unlinkFirst(Node<E> f) {
    // 要求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;
}

private E unlinkLast(Node<E> l) {
    // 要求l是尾节点并且不为null
    final E element = l.item;
    final Node<E> prev = l.prev;
    l.item = null;
    l.prev = null; // help GC
    last = prev;
    if (prev == null)
        //链表元素只有一个的情况
        first = null;
    else
        prev.next = null;
    size--;
    modCount++;
    return element;
}

//删除指定元素的节点，利用for循环便利链表，找到第一个配对的元素删除
//注意：如果链表有多个相同的元素，该方法只会删除第一个
public boolean remove(Object o) {
    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;
}

public E set(int index, E element) {
    //检查下标是否越界或者index是否小于0
    checkElementIndex(index);
    //找到index下标的元素,更新该item内容后返回旧值
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

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;
        //将新数组设置到 array 上
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

static final class COWIterator<E> implements ListIterator<E> {
    //原数组的副本
    private final Object[] snapshot;
    //游标
    private int cursor;
	//CopyOnWriteArrayList调用 iterator() 执行的构造函数
    private COWIterator(Object[] elements, int initialCursor) {
        cursor = initialCursor;
        snapshot = elements;
    }
    public boolean hasNext() {
        return cursor < snapshot.length;
    }
    public boolean hasPrevious() {
        return cursor > 0;
    }

    public E next() {
        if (! hasNext())
            throw new NoSuchElementException();
        return (E) snapshot[cursor++];
    }
    public E previous() {
        if (! hasPrevious())
            throw new NoSuchElementException();
        return (E) snapshot[--cursor];
    }
    public int nextIndex() {
        return cursor;
    }
    public int previousIndex() {
        return cursor-1;
    }
	//CopyOnWriteArrayList的迭代器不支持一下方法
    public void remove() {
        throw new UnsupportedOperationException();
    }
    public void set(E e) {
        throw new UnsupportedOperationException();
    }
    public void add(E e) {
        throw new UnsupportedOperationException();
    }
}