List(有序的集合)
- List使用一个数组来持有元素，可以在任意位置插入或删除元素，也可以通过索引访问任意位置的元素。
- List允许插入重复的元素，若List的实现支持null还可以插入多个null元素。
- 为了方便在List中又重复声明了Collection中的接口
- List还定义了一个ListIterator的迭代器，支持双向访问、插入和修改元素，并可以从任意位置处开始迭代。
- List定义了两个查找指定对象的接口，但这个查找是线性查找效率并不高。
- 试图查找一个不存在的元素时有的List实现会抛出异常有的则会返回false。
一、List接口
public interface List<E> extends Collection<E> {
// ...
}
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、 boolean removeAll(Collection<?> c);
将存在于集合c中的所有元素删除。
若有元素被移除则返回true。
1.2.4、 boolean retainAll(Collection<?> c)
删除所有未在集合c中存在的元素。
若有元素被移除则返回true
1.3、查
1.3.1、 boolean contains(Object o)
判断元素在List中是否存在，若在集合中至少存在一个与o相等的元素则返回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处的元素，若“ndex < 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或previous返回的是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异常。所以各个List的在遍历是都不能使用List直接修改，但可以使用Iterator进行修改。
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
// 修改次数
protected transient int modCount = 0;
}
2.1 boolean add(E e)
将元素添加到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();
}
2.2 int indexOf(Object o)
查询元素在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;
}
2.3 int lastIndexOf(Object o)
查询元素在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;
}
2.4 public void clear()
通过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();
}
}
2.5 boolean addAll(int index, Collection<? extends E> c)
将集合中的元素添加到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;
}
2.6 Iterator<E> iterator()
Itr是在AbstractList中定义的一个迭代器，从0处开始遍历。
public Iterator<E> iterator() {
return new Itr();
}
2.7 ListIterator<E> listIterator()
ListItr是在AbstractList中实现的一个ListIterator，支持前后遍历默认从0处开始遍历。
public ListIterator<E> listIterator() {
return listIterator(0);
}
public ListIterator<E> listIterator(final int index) {
rangeCheckForAdd(index);
return new ListItr(index);
}
2.8 boolean equals(Object o)
判断list是否相等，若指定元素是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的remove后继续通过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继承自Iterator。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();
}
}
}
