大綱
- List接口
-
- 類聲明
- 特有方法
- Collection 方法
- AbstractList抽象類
-
- 類聲明
- 主要字段
- 構造函數
- List 方法實作
- Collection 方法實作
- 特有方法
- 内部類 Itr
- 内部類 ListItr
- SubList
- RandomAccessSubList
List接口
存取順序一緻,有索引,允許重複
類聲明
特有方法
所有通過索引操作的方法都要注意其索引的範圍,否則容易導緻發生
IndexOutOfBoundsException
void add(int index, E element); // 向指定索引處增加元素 0 <= index <= size
boolean addAll(int index, Collection<? extends E> c); // 向指定索引處增加集合中的所有元素 0 <= index <= size
E remove(int index); // 删除指定索引位置的元素 0 <= index < size
E set(int index, E element); // 修改指定索引處的元素 0 <= index < size
E get(int index); // 擷取指定索引處的元素 0 <= index < size
int indexOf(Object o); // 擷取指定元素第一次出現的索引,若不存在則傳回-1
int lastIndexOf(Object o); // 擷取指定元素最後一次出現的索引,若不存在則傳回-1
List<E> subList(int fromIndex, int toIndex); // 傳回集合中從fromIndex(含)到toIndex(不含)的視圖,與原集合會互相影響
ListIterator<E> listIterator(); // 傳回listIterator hasPrevious()、previous()、add(E e);
ListIterator<E> listIterator(int index); // 從指定索引處開始傳回listIterator 0 <= index <= size
// jdk1.8新增方法
default void sort(Comparator<? super E> c){} // 根據Comparator來排序數組
default void replaceAll(UnaryOperator<E> operator) {} // 将該清單的每個元素替換為該運算符應用于該元素的結果
Collection 方法
重寫了
Collection
的抽象方法和一個預設方法
int size();
boolean isEmpty();
boolean contains(Object o);
Iterator<E> iterator();
Object[] toArray();
<T> T[] toArray(T[] a);
boolean add(E e);
boolean remove(Object o);
boolean containsAll(Collection<?> c);
boolean addAll(Collection<? extends E> c);
boolean removeAll(Collection<?> c);
boolean retainAll(Collection<?> c);
void clear();
boolean equals(Object o);
int hashCode();
@Override
default Spliterator<E> spliterator() {
return Spliterators.spliterator(this, Spliterator.ORDERED);
}
上訴可以看到,
List
将
Collection
中的抽象方法重新定義了一遍,既然一樣為什麼要寫重複的代碼?
Collection 表示的是一組共性集合, 沒有特點 (是否排序, 是否去重)。而List、Set之類的各有其特點,重新定義可以針對其特點寫不同的注釋,并且也可以一目了然的知道該類有哪些方法,在調用鍊上更加明了清晰
AbstractList抽象類
實作了
List
的部分方法,
iterator
和
size
沒有實作
類聲明
主要字段
// 維護了集合被修改的次數
protected transient int modCount = 0;
構造函數
List 方法實作
// 限定了add、set、remove操作, 由子類實作
public void add(int index, E element) { throw new UnsupportedOperationException();}
public E set(int index, E element) { throw new UnsupportedOperationException();}
public E remove(int index) { throw new UnsupportedOperationException();}
// 擷取指定角标的元素,未實作
abstract public E get(int index);
// 從前往後找,擷取指定元素在集合中第一次出現的索引,若不存在則傳回-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;
}
// 從後往前找,擷取指定元素在集合中第一次出現的索引,若不存在則傳回-1
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;
}
// 在集合末尾添加元素, add由子類實作
public boolean add(E e) {
add(size(), e);
return true;
}
// 向指定索引處增加集合中的所有元素, add由子類實作
public boolean addAll(int index, Collection<? extends E> c) {
// 索引檢查 index < 0 || index > size()
rangeCheckForAdd(index);
boolean modified = false;
for (E e : c) {
add(index++, e);
modified = true;
}
return modified;
}
// 調用 removeRange
public void clear() {
removeRange(0, size());
}
// 擷取疊代器
public Iterator<E> iterator() {
return new Itr();
}
// 擷取list疊代器
public ListIterator<E> listIterator() {
return listIterator(0);
}
// 從指定索引擷取疊代器
public ListIterator<E> listIterator(final int index) {
// 索引檢查 index < 0 || index > size()
rangeCheckForAdd(index);
return new ListItr(index);
}
// 截取集合,傳回的集合與原集合互相影響
public List<E> subList(int fromIndex, int toIndex) {
return (this instanceof RandomAccess ?
new RandomAccessSubList<>(this, fromIndex, toIndex) :
new SubList<>(this, fromIndex, toIndex));
}
// 兩個個内部類
private class Itr implements Iterator<E> {}
private class ListItr extends Itr implements ListIterator<E> {}
// 在AbstractList類下的兩個類,**不是内部類
class SubList<E> extends AbstractList<E> {}
class RandomAccessSubList<E> extends SubList<E> implements RandomAccess {}
Collection 方法實作
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());
}
public int hashCode() {
int hashCode = 1;
for (E e : this)
hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
return hashCode;
}
特有方法
// 範圍删除,包含 fromIndex,不包含 toIndex
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();
}
}
内部類 Itr
AbstractList通過使用兩個内部類
Itr
和
ListItr
實作集合的周遊
private class Itr implements Iterator<E> {
// 用來辨別目前所要周遊元素的下标
int cursor = 0;
// 用來記錄調用next調用後所指向的下标,調用remove後會重置為-1
int lastRet = -1;
// 用來辨別最初的modCount(來至于外部類AbstractList),調用疊代器的修改方法會重新指派
int expectedModCount = modCount;
// 每次周遊時add/remove都會修改modCount,若檢測到expectedModCount和modCount不一緻就會抛異常
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
// 判斷是否有下一個元素
public boolean hasNext() {
return cursor != size();
}
// 擷取下一個元素,先檢測modCount是否被修改,擷取元素,修改lastRet和cursor
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();
}
}
// 删除元素,删除前必須調用next()方法,删除的是目前元素也就是角标為lastRet的元素
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
// 調用子類實作的remove方法删除元素,并給cursor、lastRet和expectedModCount重新指派
AbstractList.this.remove(lastRet);
if (lastRet < cursor)
cursor--;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException e) {
throw new ConcurrentModificationException();
}
}
}
内部類 ListItr
ListItr
繼承了
Itr
實作了
ListIterator
,
ListIterator
接口是對
Iterator
的擴充,使疊代器不僅能向後疊代也能向前疊代,還能擷取目前元素和将要周遊元素的下标,也可對元素進行增、删、改操作
private class ListItr extends Itr implements ListIterator<E> {
ListItr(int index) {
cursor = index;
}
// 是否有前一個元素
public boolean hasPrevious() {
return cursor != 0;
}
// 擷取前一個元素并修改cursor和lastRet
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();
}
}
// 擷取下一個将要疊代的元素角标
public int nextIndex() {
return cursor;
}
// 擷取目前元素的角标
public int previousIndex() {
return cursor-1;
}
// 調用子類實作的set方法修改元素并給并給expectedModCount重新指派
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();
}
}
// 調用子類實作的add方法修改元素并給并給cursor、lastRet和expectedModCount重新指派
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();
}
}
}
SubList
SubList
調用subList方法所建立的對象,所引用的還是原數組
class SubList<E> extends AbstractList<E> {
// 用于存放原List的引用
private final AbstractList<E> l;
// 子List在原List中的開始位置
private final int offset;
// 子List的大小
private int size;
// 構造函數初始化
SubList(AbstractList<E> list, int fromIndex, int toIndex) {
if (fromIndex < 0)
throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
if (toIndex > list.size())
throw new IndexOutOfBoundsException("toIndex = " + toIndex);
if (fromIndex > toIndex)
throw new IllegalArgumentException("fromIndex(" + fromIndex +
") > toIndex(" + toIndex + ")");
l = list;
offset = fromIndex;
size = toIndex - fromIndex;
this.modCount = l.modCount;
}
// 下标檢測
private void rangeCheck(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
// add下标檢測
private void rangeCheckForAdd(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
// 修改檢測,判斷原集合中的modCount和SubList中的modCount是否相等
private void checkForComodification() {
if (this.modCount != l.modCount)
throw new ConcurrentModificationException();
}
// 調用原集合的set方法 offset+index
public E set(int index, E element) {
rangeCheck(index);
checkForComodification();
return l.set(index+offset, element);
}
// 調用原集合的get方法 offset+index
public E get(int index) {
rangeCheck(index);
checkForComodification();
return l.get(index+offset);
}
// 子集合的大小
public int size() {
checkForComodification();
return size;
}
// 調用原集合的add方法 offset+index,并修改this.mod和size
public void add(int index, E element) {
rangeCheckForAdd(index);
checkForComodification();
l.add(index+offset, element);
this.modCount = l.modCount;
size++;
}
// 調用原集合的remove方法 offset+index,并修改this.mod和size
public E remove(int index) {
rangeCheck(index);
checkForComodification();
E result = l.remove(index+offset);
this.modCount = l.modCount;
size--;
return result;
}
// 調用原集合的removeRange方法
protected void removeRange(int fromIndex, int toIndex) {
checkForComodification();
l.removeRange(fromIndex+offset, toIndex+offset);
this.modCount = l.modCount;
size -= (toIndex-fromIndex);
}
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
int cSize = c.size();
if (cSize==0)
return false;
checkForComodification();
l.addAll(offset+index, c);
this.modCount = l.modCount;
size += cSize;
return true;
}
public Iterator<E> iterator() {
return listIterator();
}
public ListIterator<E> listIterator(final int index) {
checkForComodification();
rangeCheckForAdd(index);
// 匿名内部類 對ListIterator實作
return new ListIterator<E>() {
// ...
};
}
// 套娃subList
public List<E> subList(int fromIndex, int toIndex) {
return new SubList<>(this, fromIndex, toIndex);
}
// 異常消息
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size;
}
}
RandomAccessSubList
RandomAccess
是一個标記接口,表明實作這個接口的 List 集合是支援快速随機通路,使用for循環周遊效率會高于疊代器周遊
class RandomAccessSubList<E> extends SubList<E> implements RandomAccess {
RandomAccessSubList(AbstractList<E> list, int fromIndex, int toIndex) {
super(list, fromIndex, toIndex);
}
public List<E> subList(int fromIndex, int toIndex) {
return new RandomAccessSubList<>(this, fromIndex, toIndex);
}
}