Java笔记---集合（List）

List(有序的集合)

• List使用一个数组来持有元素，可以在任意位置插入和删除元素，也可以通过索引访问任意位置的元素。
• List允许插入重复的元素，若List的实现支持null还可以插入多个null元素。
• List对iterator, add, remove, equals, and hashCode methods等接口做了额外的定义，为了方便在List中又重复声明了Collection中的接口
• List还定义了一个ListIterator的迭代器，支持双向访问、插入和修改元素，并可以从任意位置处开始迭代。
• List定义了两个查找指定对象的接口，但这个查找是线性查找效率并不高。
• 试图查找一个不存在的元素时有的List实现会抛出异常有的则会返回false。

一、List接口

1.1 增

、1.1.1 booxlean add(E e)

将指定元素添加到List的末尾。有的List可能会对元素的类型做限制如不允许添加null。

1.1.2、 void add(int index, E element);

将元素添加到指定位置，原位置以及后面的元素右移。

1.1.3、 boolean addAll(Collection<? extends E> c)

按集合c的iterator的返回顺序将所有元素添加到List的末尾。
该方法不是线程安全的若在进行此操作的同时其他线程修改了List那么该操作的结果是不确定的。

1.14、 boolean addAll(int index, Collection<? extends E> c);

按c集合Iterator的返回顺序将所有元素添加到index开始处，index及后面的元素右移。
该方法不是线程安全的若在进行此操作的同时其他线程修改了List那么该操作的结果是不确定的。

1.2、删

1.2.1、 boolean remove(Object o)

将指定元素从List中移除（可选）,若元素存在则移除并返回true。
若元素在List中存在多个则移除第一个即index最小的一个。

1.2.2、E remove(int index);

移除指定位置的元素并将其返回。
移除后后面的元素左移。

1.2.3、 bboolean removeAll(Collection<?> c);

将存在于指定集合中的所有元素删除。
若有元素被移除则返回true。

1.2.4、 boolean retainAll(Collection<?> c)

删除所有未在指定集合中存在的元素。
若有元素被移除则返回true

3、查

1.3.1、 boolean contains(Object o)

判断元素在List中是否存在，若在集合中至少存在一个相等的元素则返回true。
一般判断元素是否相等：(o==null ? e==null : o.equals(e))

1.3.2、 boolean containsAll(Collection<?> c)

若List中包含指定集合的所有元素则放回true。

1.3.3、 E get(int index)

返回index处的元素，若index<0||index>=size()抛出IndexOutOfBoundsException异常。

1.3.4、 int indexOf(Object o)

返回指定元素的在List中最小的的index。若List中不存在指定元素则返回-1。

1.3.5、 int lastIndexOf(Object o);

返回指定元素的在List中的最后index（即最大的）。若List中不存在指定元素则返回-1.

1.3.6、 Iterator<E> iterator()

返回顺序的List迭代器

1.3.7、ListIterator<E> listIterator()

返回List的ListIterator迭代器

1.3.8、ListIterator<E> listIterator(int index)

返回从index开始的ListIterator，获取到ListIterator后直接调用next返回的是index处的元素。

1.3.8、 List<E> subList(int fromIndex, int toIndex)

放回从fromIndex（包括）开始到toIndex（不包括）的子List，对返回的子List的操作会影响到源List。

1.4、改

1.4.1、 E set(int index, E element)

将指定位置处的元素替换为指定元素并返回之前的元素

1.4.2、default void replaceAll(UnaryOperator<E> operator)

用指定的UnaryOperator，对所有元素进行更新。

default void replaceAll(UnaryOperator<E> operator) {
   Objects.requireNonNull(operator);
   final ListIterator<E> li = this.listIterator();
   while (li.hasNext()) {
       li.set(operator.apply(li.next()));
   }
}

1.5、其它

1.5.1、 int size()

返回List的大小，若超过Integer.MAX_VALUE则返回Integer.MAX_VALUE。

1.5.2、 boolean isEmpty()

若集合中一个元素都没有则返回true。

1.5.3、boolean equals(Object o)

当且仅当o也是List且o的大小与该List大小相等，并且两个List中的所有元素相等时放回true。

1.5.4、int hashCode()

List的hashCode，List建议List的hashCode使用以下方式生成。这样保证List的equals相等时hashCode也是相等的。

int hashCode = 1;
for (E e : list)
     hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
}

二、AbstractList

AbstractList实现了一些List的通用的默认方法，同时定义了用来遍历List的Iterator和ListIterator的具体的迭代类。

在AbstractList定义了一个记录List修改次数的变量，在每次变更List时都会加1，在通过Iterator或ListIterator遍历List时会比较修改次数是否与遍历开始时相同，若不同则会抛出ConcurrentModificationException异常。

public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
    protected transient int modCount = 0;
    
    // 将元素添加到List的末尾。调用添加到指定位置的add(int, E)实现，但AbstractList并未实现添加到指定位置的add
    public boolean add(E e) {
        add(size(), e);
        return true;
    }
    public void add(int index, E element) {
        throw new UnsupportedOperationException();
    }
    
    // 查询元素在List中首次出现的位置。通过listIterator迭代器逐个遍历比较，若不存在则返回-1。
    public int indexOf(Object o) {
        ListIterator<E> it = listIterator();
        if (o == null) {
            while (it.hasNext())
                if (it.next() == null) {
                    return it.previousIndex();
                }
        } else {
            while (it.hasNext())
                if (o.equals(it.next()))
                    return it.previousIndex();
        }
        return -1;
    }

    //查询元素在List中最后出现的位置。通过listIterator(size())获取从末尾开始的迭代器然后previous向前逐个遍历比较。
    public int lastIndexOf(Object o) {
        ListIterator<E> it = listIterator(size());
        if (o==null) {
            while (it.hasPrevious())
                if (it.previous()==null)
                    return it.nextIndex();
        } else {
            while (it.hasPrevious())
                if (o.equals(it.previous()))
                    return it.nextIndex();
        }
        return -1;
    }
    
    // 通过removeRange整个List范围从而清空List。
    public void clear() {
        removeRange(0, size());
    }
    protected void removeRange(int fromIndex, int toIndex) {
        ListIterator<E> it = listIterator(fromIndex);
        for (int i=0, n=toIndex-fromIndex; i<n; i++) {
            it.next();
            it.remove();
        }
    }

    // 将集合中的元素添加到index开始处。通过遍历集合调用add(int, Objet)逐个添加
    public boolean addAll(int index, Collection<? extends E> c) {
        rangeCheckForAdd(index);
        boolean modified = false;
        for (E e : c) {
            add(index++, e);
            modified = true;
        }
        return modified;
    }
    
    // Itr是在AbstractList中定义的一个迭代器，从0处开始遍历。
    public Iterator<E> iterator() {
        return new Itr();
    }

    // ListItr是在AbstractList中实现的一个ListIterator，默认从0处开始遍历，也可以从指定index处开始。
    public ListIterator<E> listIterator() {
        return listIterator(0);
    }
    public ListIterator<E> listIterator(final int index) {
        rangeCheckForAdd(index);
    
        return new ListItr(index);
    }

    //若指定元素是List、数量相等且按listIterator返回的顺序元素都相等则返回true。
    public boolean equals(Object o) {
        if (o == this)
            return true;
        if (!(o instanceof List))
            return false;
    
        ListIterator<E> e1 = listIterator();
        ListIterator<?> e2 = ((List<?>) o).listIterator();
        while (e1.hasNext() && e2.hasNext()) {
            E o1 = e1.next();
            Object o2 = e2.next();
            if (!(o1==null ? o2==null : o1.equals(o2)))
                return false;
        }
        return !(e1.hasNext() || e2.hasNext());
    }
}

三、Itr

在AbstractList中定义了一个List的默认迭代器的内部类Itr。Itr从0处开始逐个遍历到size处。

创建Itr时Itr会记住当前List的修改次数，在迭代元素时会比较List的当前修改次数与Itr记录的次数是否相等，若不等则抛出ConcurrentModificationException异常。所以在使用Iterator遍历List时不能通过List提供的方法去改变List。

Iterator定义了remove接口，在Itr中也实现了该接口。Itr的reomve方法时安全的，因为在每次调用Itr的remove时Itr都会重新同步List的当前修改次数，这样调用Itr的List后继续通过Itr遍历List时安全的。

private class Itr implements Iterator<E> {
    // 初始在0处
    int cursor = 0;
    // 最后返回的元素index
    int lastRet = -1;
    // 保存当前的修改次数
    int expectedModCount = modCount;
    // cursor一直遍历到seize()-1处
    public boolean hasNext() {
        return cursor != size();
    }
    /**
     * 使用get(i)获取元素，然后cursor加1。
    */
    public E next() {
        checkForComodification();
        try {
            int i = cursor;
            E next = get(i);
            lastRet = i;
            cursor = i + 1;
            return next;
        } catch (IndexOutOfBoundsException e) {
            checkForComodification();
            throw new NoSuchElementException();
        }
    }
    // 删除前先判断修改次数是否一一致，一直则调用AbstractList的remove方法。修改后更新修改次数，所有使用Iterator的remvoe是安全的。
    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            AbstractList.this.remove(lastRet);
            if (lastRet < cursor)
                cursor--;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException e) {
            throw new ConcurrentModificationException();
        }
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

四、ListIterator

List扩展了一个支持前后遍历、插入和修改的ListIterator迭代器。ListIterator没有当前元素，它的index在previous()和next()之间。因为List是基于数组的，所以ListIterator也提供了元素在数组中位置的相关的接口。ListIterator新增了一些接口：

public interface ListIterator<E> extends Iterator<E> {
    /* 
     * 将元素插入到List中，新元素将插入到next返回的元素之前previous返回的元素之后。
     * 新插入元素后next调用不受影响，但previous()将返回新插入的元素.
     * set和add方法不是对当前index处的元素，而是针对previous或next最后放回的元素。
     */
    void add(E e);
    
    // 如果反向遍历还有元素则返回true
    boolean hasPrevious();
    
    // 返回上一个元素，同时index向前移动。调用previous后再调用next则会返回相同的元素。
    E previous();

    // 返回下一次next调用返回的元素的index。
    int nextIndex();
    
    // 返回下一次previous调用返回的元素的index。
    int previousIndex();

    // 删除上一次next或previous调用返回的元素。只能再进行next或previous调用后进行移除remove()调用。如果上传调用next或previous后又调用了add则不可以调用remove。
    void remove();

    // 将最后next或previous返回的元素更新未指定元素。如果next或previous后调用了add或remove方法则不可调用set。
    void set(E e);
}

ListItr

在AbstractList中定义了一个的默认ListIterator迭代器ListItr的内部类。需要指定开始的位置。

private class ListItr extends Itr implements ListIterator<E> {
    // 创建时要指定开始的位置
    ListItr(int index) {
        cursor = index;
    }

    // 返回上一个元素，先检查是在遍历期间是否进行了修改
    public E previous() {
        checkForComodification();
        try {
            int i = cursor - 1;
            E previous = get(i);
            lastRet = cursor = i;
            return previous;
        } catch (IndexOutOfBoundsException e) {
            checkForComodification();
            throw new NoSuchElementException();
        }
    }
    // 下一个元素的index
    public int nextIndex() {
        return cursor;
    }
    // 上一个元素的index
    public int previousIndex() {
        return cursor-1;
    }
    // 更新最后一个返回的元素，更新后也更新修改次数，所以ListIterator的set调用是安全的，单List的set调用或在对ListIterator进行调用就会抛出异常。
    public void set(E e) {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            AbstractList.this.set(lastRet, e);
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    // 在previous和next间添加一个元素。添加后修改ListIterator的修改次数，所以通过ListIterator调用add方法是安全的。
    public void add(E e) {
        checkForComodification();

        try {
            int i = cursor;
            AbstractList.this.add(i, e);
            lastRet = -1;
            cursor = i + 1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
}