数据结构

List接口继承自Collection接口，是Collection三大延伸接口之一。List中的元素都是有序的，并且都支持用索引访问。同时List中的元素允许重复。

// 替换所有 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()));
    }
}
// 排序
@SuppressWarnings({"unchecked", "rawtypes"})
default void sort(Comparator<? super E> c) {
    Object[] a = this.toArray();
    // 主要使用 Arrays.sort 进行排序
    Arrays.sort(a, (Comparator) c);
    // 迭代原集合
    ListIterator<E> i = this.listIterator();
    // 遍历新数组
    for (Object e : a) {
        i.next();
        // 使原集合中元素位置跟新数组中一致，这里直接替换
        i.set((E) e);
    }
}
// 根据索引查找
E get(int index);
// 根据索引设置元素
E set(int index, E element);
// 根据索引位置添加
void add(int index, E element);
// 根据索引位置删除
E remove(int index);
// 获取元素在集合中的第一个索引
int indexOf(Object o);
// 获取元素在集合中最后一个索引
int lastIndexOf(Object o);
// 获取一个列表迭代器
ListIterator<E> listIterator();
// 从某个位置开始构建迭代器
ListIterator<E> listIterator(int index);
// 截取某一段构建集合
List<E> subList(int fromIndex, int toIndex);

相对于Collection接口来说，List接口增加了很多索引操作，并且不仅仅提供普通Iterator迭代器，并且提供ListIterator列表迭代器，双向操作更加方便

AbstractList 抽象类

AbstractList实现List接口，从名字就可以看出该类也是抽象类，提供了对列表类操作的一些基本实现。

public abstract class AbstractList<E>
        extends AbstractCollection<E> implements List<E>

构造函数

protected AbstractList() {}

属性

// 修改次数
protected transient int modCount = 0;

未实现的方法

abstract public E get(int index);

已实现的方法

AbstractList中除了极少数方法没有被子类覆盖（如equals、hashCode），大部分方法都被子类覆盖

添加

public boolean add(E e) {
    add(size(), e);
    return true;
}

public void add(int index, E element) {
    throw new UnsupportedOperationException();
}

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;
}

private void rangeCheckForAdd(int index) {
    if (index < 0 || index > size())
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

add(E e)调用add(int index, E element)，注意直接调用会抛异常，子类必须覆盖此方法

设值

public E set(int index, E element) {
    throw new UnsupportedOperationException();
}

同样需要注意，直接调用会抛异常，子类必须覆盖此方法

删除

public E remove(int index) {
    throw new UnsupportedOperationException();
}

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();
    }
}

直接调用remove(int index)会抛异常，子类必须覆盖此方法

查找

// 获取元素索引
public int indexOf(Object o) {
    // 获取此集合列表迭代器
    ListIterator<E> it = listIterator();
    if (o==null) {
        // 参数为空时找元素为空的索引
        while (it.hasNext())
            // 找到第一个就返回
            if (it.next()==null)
                return it.previousIndex();
    } else {
        // 参数不为空，找元素和参数equals一样的索引
        while (it.hasNext())
            // 找到第一个就返回
            if (o.equals(it.next()))
                return it.previousIndex();
    }
    // 没有找到返回-1
    return -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 {
        // 参数不为空，找元素和参数equals一样的索引（倒着找）
        while (it.hasPrevious())
            // 找到第一个就返回（倒找找第一个，实际上就是最后一个）
            if (o.equals(it.previous()))
                return it.nextIndex();
    }
    // 没有找到返回-1
    return -1;
}

清空

public void clear() {
    // 从第一个元素开始删除
    removeRange(0, size());
}

hashCode方法

public int hashCode() {
    // 初始化为1，如果元素为空，hashCode就为1
    int hashCode = 1;
    for (E e : this)
        // 上一次 hashCode 乘以31，加上当前元素的 hashCode
        hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
    // 返回 hashCode
    return hashCode;
}

equals方法

public boolean equals(Object o) {
    // 参数与当前集合内存地址一样，返回true
    if (o == this)
        return true;
    // 参数不是List或List子类的实例，返回false
    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();
        // 判断两个元素是否一致，都为空或equals一致
        if (!(o1==null ? o2==null : o1.equals(o2)))
            return false;
    }
    // 能到这至少有一个迭代完，有一个没迭代完就返回false
    return !(e1.hasNext() || e2.hasNext());
}

迭代器

// 获取迭代器
public Iterator<E> iterator() {
    return new Itr();
}
// 获取列表迭代器
public ListIterator<E> listIterator() {
    return listIterator(0);
}
// 从某一位置构建迭代器
public ListIterator<E> listIterator(final int index) {
    rangeCheckForAdd(index);

    return new ListItr(index);
}

内部类Itr

private class Itr implements Iterator<E> {

    int cursor = 0;
    int lastRet = -1;
    int expectedModCount = modCount;
    public boolean hasNext() {...}
    public E next() {...}
    public void remove() {...}
    final void checkForComodification() {...}
}

此内部类主要是实现Iterator迭代器基本功能

内部类ListItr

private class ListItr extends Itr implements ListIterator<E> {
    ListItr(int index) {...}
    public boolean hasPrevious() {...}
    public E previous() {...}
    public int nextIndex() {...}
    public int previousIndex() {...}
    public void set(E e) {...}
    public void add(E e) {...}
}

此内部类继承Itr并实现ListIterator，经典的适配器模式，并且扩展Itr，使其拥有双向迭代功能

外部内SubList

class SubList<E> extends AbstractList<E>

SubList类继承自AbstractList抽象类，因此它的实例列表可以使用AbstractList的各种已经实现的方法。

外部类RandomAccessSubList

class RandomAccessSubList<E> extends SubList<E> implements RandomAccess

RandomAccessSubList类继承自SubList，并实现了RandomAccess接口，RandomAccess接口只是表示此类的实例支持随机访问。

AbstractList 抽象类

AbstractList实现List接口，从名字就可以看出该类也是抽象类，提供了对列表类操作的一些基本实现。

publicabstractclassAbstractList<E>
extendsAbstractCollection<E>implementsList<E>

构造函数

protectedAbstractList(){
}

属性

// 修改次数
protectedtransientint modCount =0;

未实现的方法

abstractpublic E get(int index);

已实现的方法

AbstractList中除了极少数方法没有被子类覆盖（如equals、hashCode），大部分方法都被子类覆盖

添加

publicboolean add(E e){
add(size(), e);
returntrue;
}
publicvoid add(int index, E element){
thrownewUnsupportedOperationException();
}
publicboolean addAll(int index,Collection<?extends E> c){
// 是否越界校验
rangeCheckForAdd(index);
boolean modified =false;
for(E e : c){
add(index++, e);
modified =true;
}
return modified;
}
privatevoid rangeCheckForAdd(int index){
if(index <0|| index > size())
thrownewIndexOutOfBoundsException(outOfBoundsMsg(index));
}

add(E e)调用add(int index, E element)，注意直接调用会抛异常，子类必须覆盖此方法

设值

public E set(int index, E element){
thrownewUnsupportedOperationException();
}

同样需要注意，直接调用会抛异常，子类必须覆盖此方法

删除

public E remove(int index){
thrownewUnsupportedOperationException();
}
protectedvoid removeRange(int fromIndex,int toIndex){
// 按起始位置构建列表迭代器
ListIterator<E> it = listIterator(fromIndex);
// 遍历范围内的所有元素
for(int i=0, n=toIndex-fromIndex; i<n; i++){
// 迭代删除
it.next();
it.remove();
}
}

直接调用remove(int index)会抛异常，子类必须覆盖此方法

查找

// 获取元素索引
publicint indexOf(Object o){
// 获取此集合列表迭代器
ListIterator<E> it = listIterator();
if(o==null){
// 参数为空时找元素为空的索引
while(it.hasNext())
// 找到第一个就返回
if(it.next()==null)
return it.previousIndex();
}else{
// 参数不为空，找元素和参数equals一样的索引
while(it.hasNext())
// 找到第一个就返回
if(o.equals(it.next()))
return it.previousIndex();
}
// 没有找到返回-1
return-1;
}
// 按索引查找
publicint lastIndexOf(Object o){
// 获取此集合列表迭代器
ListIterator<E> it = listIterator(size());
if(o==null){
// 参数为空时找元素为空的索引，这里是从最后一个找起
while(it.hasPrevious())
// 找到第一个就返回（倒找找第一个，实际上就是最后一个）
if(it.previous()==null)
return it.nextIndex();
}else{
// 参数不为空，找元素和参数equals一样的索引（倒着找）
while(it.hasPrevious())
// 找到第一个就返回（倒找找第一个，实际上就是最后一个）
if(o.equals(it.previous()))
return it.nextIndex();
}
// 没有找到返回-1
return-1;
}

清空

publicvoid clear(){
// 从第一个元素开始删除
removeRange(0, size());
}

hashCode方法

publicint hashCode(){
// 初始化为1，如果元素为空，hashCode就为1
int hashCode =1;
for(E e :this)
// 上一次 hashCode 乘以31，加上当前元素的 hashCode
hashCode =31*hashCode +(e==null?0: e.hashCode());
// 返回 hashCode
return hashCode;
}

equals方法

publicboolean equals(Object o){
// 参数与当前集合内存地址一样，返回true
if(o ==this)
returntrue;
// 参数不是List或List子类的实例，返回false
if(!(o instanceofList))
returnfalse;
// 获取两个迭代器
ListIterator<E> e1 = listIterator();
ListIterator<?> e2 =((List<?>) o).listIterator();
// 同时迭代两个集合，同时有值才可以迭代
while(e1.hasNext()&& e2.hasNext()){
// 分别获取元素
E o1 = e1.next();
Object o2 = e2.next();
// 判断两个元素是否一致，都为空或equals一致
if(!(o1==null? o2==null: o1.equals(o2)))
returnfalse;
}
// 能到这至少有一个迭代完，有一个没迭代完就返回false
return!(e1.hasNext()|| e2.hasNext());
}

迭代器

// 获取迭代器
publicIterator<E> iterator(){
returnnewItr();
}
// 获取列表迭代器
publicListIterator<E> listIterator(){
return listIterator(0);
}
// 从某一位置构建迭代器
publicListIterator<E> listIterator(finalint index){
rangeCheckForAdd(index);
returnnewListItr(index);
}

内部类Itr

privateclassItrimplementsIterator<E>{
int cursor =0;
int lastRet =-1;
int expectedModCount = modCount;
publicboolean hasNext(){...}
public E next(){...}
publicvoid remove(){...}
finalvoid checkForComodification(){...}
}

此内部类主要是实现Iterator迭代器基本功能

内部类ListItr

privateclassListItrextendsItrimplementsListIterator<E>{
ListItr(int index){...}
publicboolean hasPrevious(){...}
public E previous(){...}
publicint nextIndex(){...}
publicint previousIndex(){...}
publicvoidset(E e){...}
publicvoid add(E e){...}
}

此内部类继承Itr并实现ListIterator，经典的适配器模式，并且扩展Itr，使其拥有双向迭代功能

外部内SubList

classSubList<E>extendsAbstractList<E>

SubList类继承自AbstractList抽象类，因此它的实例列表可以使用AbstractList的各种已经实现的方法。

外部类RandomAccessSubList

classRandomAccessSubList<E>
extendsSubList<E>implementsRandomAccess

RandomAccessSubList类继承自SubList，并实现了RandomAccess接口，RandomAccess接口只是表示此类的实例支持随机访问。

AbstractList 抽象类

构造函数

属性

未实现的方法

已实现的方法

添加

设值

删除

查找

清空

hashCode方法

equals方法

迭代器

内部类Itr

内部类ListItr

外部内SubList

外部类RandomAccessSubList

AbstractList 抽象类

构造函数

属性

未实现的方法

已实现的方法

添加

设值

删除

查找

清空

hashCode方法

equals方法

迭代器

内部类Itr

内部类ListItr

外部内SubList

外部类RandomAccessSubList

相关推荐