集合类与IO

import java.util.ArrayList;   //集合类基本都是在java.util包下定义的

public class Main {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        list.add("树脂666");
    }
}

public interface Collection<E> extends Iterable<E> {
    //-------这些是查询相关的操作----------

   	//获取当前集合中的元素数量
    int size();

    //查看当前集合是否为空
    boolean isEmpty();

    //查询当前集合中是否包含某个元素
    boolean contains(Object o);

    //返回当前集合的迭代器，我们会在后面介绍
    Iterator<E> iterator();

    //将集合转换为数组的形式
    Object[] toArray();

    //支持泛型的数组转换，同上
    <T> T[] toArray(T[] a);

    //-------这些是修改相关的操作----------

    //向集合中添加元素，不同的集合类具体实现可能会对插入的元素有要求，
  	//这个操作并不是一定会添加成功，所以添加成功返回true，否则返回false
    boolean add(E e);

    //从集合中移除某个元素，同样的，移除成功返回true，否则false
    boolean remove(Object o);


    //-------这些是批量执行的操作----------

    //查询当前集合是否包含给定集合中所有的元素
  	//从数学角度来说，就是看给定集合是不是当前集合的子集
    boolean containsAll(Collection<?> c);

    //添加给定集合中所有的元素
  	//从数学角度来说，就是将当前集合变成当前集合与给定集合的并集
  	//添加成功返回true，否则返回false
    boolean addAll(Collection<? extends E> c);

    //移除给定集合中出现的所有元素，如果某个元素在当前集合中不存在，那么忽略这个元素
  	//从数学角度来说，就是求当前集合与给定集合的差集
  	//移除成功返回true，否则false
    boolean removeAll(Collection<?> c);

    //Java8新增方法，根据给定的Predicate条件进行元素移除操作
    default boolean removeIf(Predicate<? super E> filter) {
        Objects.requireNonNull(filter);
        boolean removed = false;
        final Iterator<E> each = iterator();   //这里用到了迭代器，我们会在后面进行介绍
        while (each.hasNext()) {
            if (filter.test(each.next())) {
                each.remove();
                removed = true;
            }
        }
        return removed;
    }

    //只保留当前集合中在给定集合中出现的元素，其他元素一律移除
  	//从数学角度来说，就是求当前集合与给定集合的交集
  	//移除成功返回true，否则false
    boolean retainAll(Collection<?> c);

    //清空整个集合，删除所有元素
    void clear();


    //-------这些是比较以及哈希计算相关的操作----------

    //判断两个集合是否相等
    boolean equals(Object o);

    //计算当前整个集合对象的哈希值
    int hashCode();

    //与迭代器作用相同，但是是并行执行的，我们会在下一章多线程部分中进行介绍
    @Override
    default Spliterator<E> spliterator() {
        return Spliterators.spliterator(this, 0);
    }

    //生成当前集合的流，我们会在后面进行讲解
    default Stream<E> stream() {
        return StreamSupport.stream(spliterator(), false);
    }

    //生成当前集合的并行流，我们会在下一章多线程部分中进行介绍
    default Stream<E> parallelStream() {
        return StreamSupport.stream(spliterator(), true);
    }
}

//List是一个有序的集合类，每个元素都有一个自己的下标位置
//List中可插入重复元素
//针对于这些特性，扩展了Collection接口中一些额外的操作
public interface List<E> extends Collection<E> {
    ...
   	
    //将给定集合中所有元素插入到当前结合的给定位置上（后面的元素就被挤到后面去了，跟我们之前顺序表的插入是一样的）
    boolean addAll(int index, Collection<? extends E> c);

    ...

   	//Java 8新增方法，可以对列表中每个元素都进行处理，并将元素替换为处理之后的结果
    default void replaceAll(UnaryOperator<E> operator) {
        Objects.requireNonNull(operator);
        final ListIterator<E> li = this.listIterator();  //这里同样用到了迭代器
        while (li.hasNext()) {
            li.set(operator.apply(li.next()));
        }
    }

    //对当前集合按照给定的规则进行排序操作，这里同样只需要一个Comparator就行了
    @SuppressWarnings({"unchecked", "rawtypes"})
    default void sort(Comparator<? super E> c) {
        Object[] a = this.toArray();
        Arrays.sort(a, (Comparator) c);
        ListIterator<E> i = this.listIterator();
        for (Object e : a) {
            i.next();
            i.set((E) e);
        }
    }

    ...

    //-------- 这些是List中独特的位置直接访问操作 --------

   	//获取对应下标位置上的元素
    E get(int index);

    //直接将对应位置上的元素替换为给定元素
    E set(int index, E element);

    //在指定位置上插入元素，就跟我们之前的顺序表插入是一样的
    void add(int index, E element);

    //移除指定位置上的元素
    E remove(int index);


    //------- 这些是List中独特的搜索操作 -------

    //查询某个元素在当前列表中的第一次出现的下标位置
    int indexOf(Object o);

    //查询某个元素在当前列表中的最后一次出现的下标位置
    int lastIndexOf(Object o);


    //------- 这些是List的专用迭代器 -------

    //迭代器我们会在下一个部分讲解
    ListIterator<E> listIterator();

    //迭代器我们会在下一个部分讲解
    ListIterator<E> listIterator(int index);

    //------- 这些是List的特殊转换 -------

    //返回当前集合在指定范围内的子集
    List<E> subList(int fromIndex, int toIndex);

    ...
}

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
		
    //默认的数组容量
    private static final int DEFAULT_CAPACITY = 10;

    ...

    //存放数据的底层数组，这里的transient关键字我们会在后面I/O中介绍用途
    transient Object[] elementData;

    //记录当前数组元素数的
    private int size;

   	//这是ArrayList的其中一个构造方法
    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);
        }
    }
  
    //这是ArrayList的无参构造方法
  	public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
  
  	...
      
   	public boolean add(E e) {
        modCount++;   //用于后期判断是否出现并发异常，比如遍历时修改或是多线程操作（暂时忽略）
        add(e, elementData, size);  //调用内部私有辅助方法实现插入操作，因为是尾插，index直接写size就行
        return true;  //直接返回真插入成功
    }
  
    private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length)   //首先判断长度是否超出当前内部数组容量
            elementData = grow();   //超出那么就得扩容，扩容会对类的elementData进行重新赋值，下面介绍
        elementData[s] = e;   //接着正常插入元素即可
        size = s + 1;  //让size自增
    }
  
    public void add(int index, E element) {
        rangeCheckForAdd(index);   //先判断插入位置是否超出范围
        modCount++;   //同上
        final int s;
        Object[] elementData;
      	//看着有点绕，但实际上就是让s等于size，elementData等于类的elementData
        //然后再比较长度是否已经一样，一样就扩容，跟上面思路是差不多的
        if ((s = size) == (elementData = this.elementData).length)
            elementData = grow();
        System.arraycopy(elementData, index,
                         elementData, index + 1,
                         s - index);  //因为是中间插入，这里调用C++实现的数组移动操作，把位置让出来
        elementData[index] = element;  //位置让出来之后，设置新元素
        size = s + 1;  //让size自增
    }
  	
  	...
  
    private Object[] grow() {
        return grow(size + 1);   //调用内部其他方法实现，并制定扩容最小值为当前容量+1
    }
  
  	private Object[] grow(int minCapacity) {
        int oldCapacity = elementData.length;   //首先保存下现在的容量
        if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            //判断当前容量是否不为0（因为初始就是0，不为0一定被扩容过）
            //然后计算新的容量，这里传入当前长度、最小扩容长度和推荐扩容长度三个参数，通过辅助方法衡量该如何扩容
            int newCapacity = ArraysSupport.newLength(oldCapacity,
                    minCapacity - oldCapacity, /* 最小扩容长度 */
                    oldCapacity >> 1           /* 推荐扩容长度 */);
            return elementData = Arrays.copyOf(elementData, newCapacity);  //得到最终扩容大小，创建新数组
        } else {
            //这里相当于现在容量为0，也就是初始状态，此时会直接创建一个容量为10的新数组
            //注意这里需要取minCapacity和默认容量的最大值，因为grow不仅仅在单个插入时会调用，批量插入的时候也会调用，有可能出现批量插入20个的情况，那么初始容量就装不下了
            return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
        }
    }
}

		//默认的列表最大长度为Integer.MAX_VALUE - 8
    //因为在部分JVM的C++实现中，在数组的对象头中有一个_length字段，用于记录数组的长度
    //所以这个8（保守估计，不一定是）就是存了数组_length字段（这个只做了解就行）
    public static final int SOFT_MAX_ARRAY_LENGTH = Integer.MAX_VALUE - 8;

    public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
        //计算新的长度，因为minGrowth和prefGrowth谁更大不确定，需要进行比较，然后得到新的长度
        int prefLength = oldLength + Math.max(minGrowth, prefGrowth);
        //接着比较新的长度是否已经超出数组允许的最大长度了
        if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {
            return prefLength;  //没有直接返回
        } else {
            // 如果超出最大长度，需要进一步处理
            return hugeLength(oldLength, minGrowth);
        }
    }

		private static int hugeLength(int oldLength, int minGrowth) {
        //先看看现在需要的最小长度，因为走到这里有可能是因为prefLength过长，但并不代表就真的需要这么长，因为prefLength有可能加的是prefGrowth，不一定是最小值
        int minLength = oldLength + minGrowth;  
        if (minLength < 0) { // 如果加出来最小长度已经小于0了，那包是超过int最大值了（前面二进制章节有介绍为什么）
            throw new OutOfMemoryError(   //直接无情抛异常
                "Required array length " + oldLength + " + " + minGrowth + " is too large");
        } else if (minLength <= SOFT_MAX_ARRAY_LENGTH) {  //如果在最大长度允许范围内
            return SOFT_MAX_ARRAY_LENGTH;   //直接给最大的
        } else {
            return minLength;  
            //这种情况相当于在SOFT_MAX_ARRAY_LENGTH和int最大值之间，没法了，只能直接返回
            //虽然有些JVM会可能直接抛出异常，但是可以抱着试试的心态搞一下
        }
    }

public static void main(String[] args) {
    List<String> list = new ArrayList<>();   //使用接口的引用来操作具体的集合类实现，是为了方便日后如果我们想要更换不同的集合类实现，而且接口中本身就已经定义了主要的方法，所以说没必要直接用实现类
    list.add("科技与狠活");   //使用add添加元素
  	list.add("上头啊");
    System.out.println(list);   //打印集合类，可以得到一个非常规范的结果
}

public static void main(String[] args) {
    List<Integer> list = new ArrayList<>();
    list.add(10);   //添加Integer的值10
    list.remove((Integer) 10);   //注意，不能直接用10，默认情况下会认为传入的是int类型值，删除的是下标为10的元素，我们这里要删除的是刚刚传入的值为10的Integer对象
    System.out.println(list);   //可以看到，此时元素成功被移除
}

public static void main(String[] args) {
    List<Integer> list = new ArrayList<>();
    list.add(new Integer(10));   //添加的是一个对象
    list.remove(new Integer(10));   //删除的是另一个对象
    System.out.println(list);
}

//ArrayList源码部分
public boolean remove(Object o) {
    if (o == null) {
        ...
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {   //这里只是对两个对象进行equals判断
                fastRemove(index);
                return true;  //只要判断成功，直接认为就是要删除的对象，删除就完事
            }
    }
    return false;
}

public static void main(String[] args) {
    List<String> list = new ArrayList<>();
    String str = "哟唉嘛干你";
    list.add(str);
    list.add(str);
    System.out.println(list);
}

public static void main(String[] args) {
    List<String> list = new ArrayList<>();
    String str = "哟唉嘛干你";
    list.add(str);
    list.add(str);
    list.remove(str);
    System.out.println(list);
}

public static void main(String[] args) {
    List<List<String>> list = new LinkedList<>();
    list.add(new LinkedList<>());   //集合中的每一个元素就是一个集合，这个套娃是可以一直套下去的
    System.out.println(list.get(0).isEmpty());
}

public static void main(String[] args) {
    List<String> list = Arrays.asList("A", "B", "C");   //非常方便
    System.out.println(list);
}

public static void main(String[] args) {
    List<String> list = new ArrayList<>(Arrays.asList("A", "B", "C"));
    System.out.println(list);
}

public static void main(String[] args) {
    List<String> list = new ArrayList<String>() {{   //使用匿名内部类（匿名内部类在Java8无法使用钻石运算符，但是之后的版本可以）
            add("A");
            add("B");
            add("C");
    }};
    System.out.println(list);
}

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;

    //引用首结点
    transient Node<E> first;
    //引用尾结点
    transient Node<E> last;

    //构造方法，很简单，直接创建就行了
    public LinkedList() {
    }
  
  	...
      
    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 boolean add(E e) {
        linkLast(e);   //调用内部方法进行尾部连接
        return true;
    }
  
  	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;  //否则更新当前尾结点的next引用，把新的结点串起来
        size++;   //让size自增
        modCount++;
    }
  
    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;   //如果前驱结点为空，说明这个结点就是就是第一个，直接让first等于next就行了
        } else {
            prev.next = next;  //否则让前驱结点直接去连接下一个
            x.prev = null;   //取消当前结点对于前驱结点的引用，便于JVM自动垃圾回收
        }

        if (next == null) {  //同上，处于后驱结点，操作差不多
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }

        x.item = null;   //前后处理干净，然后把待删除结点对于元素的引用取消，彻底废弃掉此结点
        size--;   //让size自减
        modCount++;
        return element;  //返回被删元素
    }
  
    ...
}

public static void main(String[] args) {
    List<String> list = Arrays.asList("A", "B", "C");
    for (String s : list) {   //集合类同样支持这种语法
        System.out.println(s);
    }
}

public static void main(String[] args) {
    List<String> list = Arrays.asList("A", "B", "C");
    Iterator var2 = list.iterator();   //这里使用的是List的迭代器在进行遍历操作

    while(var2.hasNext()) {
        String s = (String)var2.next();
        System.out.println(s);
    }

}

public static void main(String[] args) {
    List<String> list = Arrays.asList("A", "B", "C");
  	//通过调用iterator方法快速获取当前集合的迭代器
  	//Iterator迭代器本身也是一个接口，由具体的集合实现类来根据情况实现
    Iterator<String> iterator = list.iterator();
}

public interface Iterator<E> {
    //看看是否还有下一个元素
    boolean hasNext();

    //遍历当前元素，并将下一个元素作为待遍历元素
    E next();

    //移除上一个被遍历的元素（某些集合不支持这种操作）
    default void remove() {
        throw new UnsupportedOperationException("remove");
    }

    //对剩下的元素进行自定义遍历操作
    default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

public E next() {
    ...
    cursor = i + 1;   //移动指针
    return (E) elementData[lastRet = i];  //直接返回指针所指元素
}

public E next() {
    ...
    next = next.next;   //向后继续寻找结点
    nextIndex++;
    return lastReturned.item;  //返回结点内部存放的元素
}

public static void main(String[] args) {
    List<String> list = Arrays.asList("A", "B", "C");
    Iterator<String> iterator = list.iterator();
    while (iterator.hasNext()) {    //每次循环一定要判断是否还有元素剩余
        System.out.println(iterator.next());  //如果有就可以继续获取到下一个元素
    }
}

public static void main(String[] args) {
    List<String> list = Arrays.asList("A", "B", "C");
    for (String s : list) {
        System.out.println(s);
    }
}

public static void main(String[] args) {
    List<String> list = Arrays.asList("A", "B", "C");
    list.forEach(System.out::println);
    //这里有一个常见误区，lambda里面禁止修改外部的非final变量
}

default void forEach(Consumer<? super T> action) {
    Objects.requireNonNull(action);
    for (T t : this) {   //foreach语法遍历每一个元素
        action.accept(t);   //调用Consumer的accept来对每一个元素进行消费
    }
}

//注意这个接口是集合接口的父接口，不要跟之前的迭代器接口搞混了
public interface Iterable<T> {
    //生成当前集合的迭代器，在Collection接口中重复定义了一次
    Iterator<T> iterator();

    //Java8新增方法，因为是在顶层接口中定义的，因此所有的集合类都有这个方法
    default void forEach(Consumer<? super T> action) {
        Objects.requireNonNull(action);
        for (T t : this) {
            action.accept(t);
        }
    }

    //这个方法会在多线程部分中进行介绍，暂时不做讲解
    default Spliterator<T> spliterator() {
        return Spliterators.spliteratorUnknownSize(iterator(), 0);
    }
}

public class Test implements Iterable<String>{   //这里我们随便写一个类，让其实现Iterable接口
    @Override
    public Iterator<String> iterator() {
        return new Iterator<String>() {   //生成一个匿名的Iterator对象
            @Override
            public boolean hasNext() {   //这里随便写的，直接返回true，这将会导致无限循环
                return true;
            }

            @Override
            public String next() {   //每次就直接返回一个字符串吧
                return "测试";
            }
        };
    }
}

public static void main(String[] args) {
    Test test = new Test();
    for (String s : test) {
        System.out.println(s);
    }
}

public interface ListIterator<E> extends Iterator<E> {
    //原本就有的
    boolean hasNext();

    //原本就有的
    E next();

    //查看前面是否有已经遍历的元素
    boolean hasPrevious();

    //跟next相反，这里是倒着往回遍历
    E previous();

    //返回下一个待遍历元素的下标
    int nextIndex();

    //返回上一个已遍历元素的下标
    int previousIndex();

    //原本就有的
    void remove();

    //将上一个已遍历元素修改为新的元素
    void set(E e);

    //在遍历过程中，插入新的元素到当前待遍历元素之前
    void add(E e);
}

public static void main(String[] args) {
    List<String> list = new ArrayList<>(Arrays.asList("A", "B", "C"));
    ListIterator<String> iterator = list.listIterator();
    iterator.next();   //此时得到A
    iterator.set("X");  //将A原本位置的上的元素设定为成新的
    System.out.println(list);
}