Java笔记---集合（List）

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();
        }
    }
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 196,264评论 5赞 462
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 82,549评论 2赞 373
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 143,389评论 0赞 325
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 52,616评论 1赞 267
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 61,461评论 5赞 358
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 46,351评论 1赞 273
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 36,776评论 3赞 387
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 35,414评论 0赞 255
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 39,722评论 1赞 294
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 34,760评论 2赞 314
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 36,537评论 1赞 326
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 32,381评论 3赞 315
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 37,787评论 3赞 300
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,030评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,304评论 1赞 252
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 41,734评论 2赞 342
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 40,943评论 2赞 336