Java基础系列（四十一）：集合之List

前言

List是继承自Collection的一个子接口，它提供了一个有序的集合，在这个集合中我们可以使用索引去获取集合中的值，同时，我们也可以通过迭代器去访问集合中的元素，第一种方法被称为随机访问，因为我们可以按照任意的顺序去访问元素，而使用迭代器就必须顺序的去访问元素。

结构图

可以看出List的结构图也非常简单，只是简单的继承了Collection，这里不再进行过多的阐述，我们来看一下源码。

源码

package java.util;
import java.util.function.UnaryOperator;
public interface List<E> extends Collection<E> {
    // Query Operations
    int size();
    boolean isEmpty();
    boolean contains(Object o);
    Iterator<E> iterator();
    Object[] toArray();
    <T> T[] toArray(T[] a);
    // Modification Operations
    boolean add(E e);
    boolean remove(Object o);
    // Bulk Modification Operations
    boolean containsAll(Collection<?> c);
    boolean addAll(Collection<? extends E> c);
    boolean addAll(int index, Collection<? extends E> c);
    boolean removeAll(Collection<?> c);
    boolean retainAll(Collection<?> c);
    default void replaceAll(UnaryOperator<E> operator) {
        Objects.requireNonNull(operator);
        final ListIterator<E> li = this.listIterator();
        while (li.hasNext()) {
            li.set(operator.apply(li.next()));
        }
    }
    @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);
        }
    }
    void clear();
    // Comparison and hashing
    boolean equals(Object o);
    int hashCode();
    // Positional Access Operations
    E get(int index);
    E set(int index, E element);
    void add(int index, E element);
    E remove(int index);
    // Search Operations
    int indexOf(Object o);
    int lastIndexOf(Object o);
    // List Iterators
    ListIterator<E> listIterator();
    /**
    * 这里返回的列表迭代器是第一次调用next返回的给定索引的元素，也就是说，这个迭代器指向的索引为n的元素前面的位置。
    */
    ListIterator<E> listIterator(int index);
    // View
    List<E> subList(int fromIndex, int toIndex);
    @Override
    default Spliterator<E> spliterator() {
        return Spliterators.spliterator(this, Spliterator.ORDERED);
    }
}

可以看到相比于它的父接口Collection，并没有发生很大的改动，但是由于List是一个有序的集合，所以提供了一些基于索引进行的操作：

get(int index)：获取该集合中索引等于index的元素

set(int index, E element)：将该集合中索引等于index的元素赋值为element

add(int index, E element)：在集合中索引等于index的位置将element插入，并将当前处于该位置的元素及其后续元素的索引加1。

remove(int index)：删除指定索引（index）位置的元素，并将处于该位置后面的元素索引减1

indexOf(Object o)：获取对象o在集合中的索引

lastIndexOf(Object o)：获取对象o在集合中最后一次出现的索引值，如果集合中不存在这个对象，返回-1。

同时，提供了一个Iterator的子接口ListIterator，基于这个迭代器，我们实现了两个默认方法replaceAll(UnaryOperator<E> operator)和sort(Comparator<? super E> c)。

replaceAll(UnaryOperator<E> operator)这里和String类中replaceAll()方法并不相同，这里的接收参数是一个函数式接口，我们来看一下这个函数式接口的源码：

package java.util.function;
@FunctionalInterface
public interface UnaryOperator<T> extends Function<T, T> {
    /**
     * Returns a unary operator that always returns its input argument.
     *
     * @param <T> the type of the input and output of the operator
     * @return a unary operator that always returns its input argument
     */
    static <T> UnaryOperator<T> identity() {
        return t -> t;
    }
}

通过翻译我们可以知道，这个函数式接口继承了Function<T,T>，传入的是一个值，返回的是一个经过操作符之后的值，我接下来来写一个小李子来讲解一下用法：

List<String> strList = new ArrayList<>();
strList.add("Hungary");
strList.add("Foolish");

strList.replaceAll(t -> "Stay " + t);
strList.forEach(s -> System.out.println(s));

打印结果为

Stay Hungary Stay Foolish

而sort(Comparator<? super E> c)传入的同样是一个函数式接口，我们可以自定义排序规则后，调用这个方法进行排序：

List<Human> humans = Lists.newArrayList(new Human("Sarah", 10), new Human("Jack", 12));

humans.sort((Human h1, Human h2) -> h1.getName().compareTo(h2.getName()))

（PS：Java 8 提供了Lambda语法糖，给人带来一种非常舒服的编程体验，建议大家多多使用）

这里是Arrays.sort的源码，可以看到使用了归并算法和TimSort算法来进行排序，后面关于算法和数据结构的知识会详细对这些内容进行讲解，这里只作为一个了解~

public static <T> void sort(T[] a, Comparator<? super T> c) {
    if (c == null) {
        sort(a);
    } else {
        if (LegacyMergeSort.userRequested)
            legacyMergeSort(a, c);
        else
            TimSort.sort(a, 0, a.length, c, null, 0, 0);
    }
}

ListIterator

前面我们已经提过，ListIterator作为Iterator的子接口，给有序的集合List提供了一个链表结构下的迭代器，接下来，我们来看一下ListIterator的源码：

package java.util;


public interface ListIterator<E> extends Iterator<E> {
    // Query Operations

    boolean hasNext();

    E next();

    boolean hasPrevious();

    E previous();

    int nextIndex();

    int previousIndex();

    // Modification Operations

    void remove();

    void set(E e);

    void add(E e);
}

可以看出和Iterator不同的是，ListIterator新增了一些基于链表数据结构的操作以及可以用来反向遍历链表的方法：

hasPrevious()：当反向迭代列表时，还有可供访问的元素，返回true。

previous()：返回前一个对象，如果已经到达了列表的头部，抛出一个NoSuchElementException异常

nextIndex()：返回下一次调用next方法将返回的元素索引

previousIndex()：返回下一次调用previous方法将返回的元素索引

add(E newElement)：在当前位置前添加一个元素。

set(E newElement)：用新元素取代next或previous上次访问的元素。如果在next或previous上次调用之后列表结构被修改了，将抛出一个IllegalStateException异常。

下节预告

下一节，我们会去深入的学习AbstractList。

公众号