Java筆記---集合（List）

List(有序的集合)

  • List使用一個數(shù)組來持有元素椎镣，可以在任意位置插入或刪除元素悲敷，也可以通過索引訪問任意位置的元素屎暇。
  • List允許插入重復的元素囚巴，若List的實現(xiàn)支持null還可以插入多個null元素您炉。
  • 為了方便在List中又重復聲明了Collection中的接口
  • List還定義了一個ListIterator的迭代器柒爵，支持雙向訪問、插入和修改元素赚爵，并可以從任意位置處開始迭代棉胀。
  • List定義了兩個查找指定對象的接口，但這個查找是線性查找效率并不高冀膝。
  • 試圖查找一個不存在的元素時有的List實現(xiàn)會拋出異常有的則會返回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實現(xiàn)了一些List的通用的默認方法，同時定義了用來遍歷List的Iterator和ListIterator的迭代類染厅。

在AbstractList中定義了一個記錄List修改次數(shù)的變量痘绎，在每次變更List時都會加1，在通過Iterator或ListIterator遍歷List時會比較修改次數(shù)是否與遍歷開始時相同糟秘，若不同則會拋出ConcurrentModificationException異常简逮。所以各個List的在遍歷是都不能使用List直接修改，但可以使用Iterator進行修改尿赚。

public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
    // 修改次數(shù)
    protected transient int modCount = 0;
 
}
2.1 boolean add(E e)

將元素添加到List的末尾散庶。調用添加到指定位置的add(int, E)實現(xiàn)，但AbstractList并未實現(xiàn)添加到指定位置的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中首次出現(xiàn)的位置悲龟。通過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中最后出現(xiàn)的位置须教。通過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中實現(xiàn)的一個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)

判斷l(xiāng)ist是否相等琴庵，若指定元素是List误算、數(shù)量相等且按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處儿礼。

創(chuàng)建Itr時Itr會記住當前List的修改次數(shù)咖杂，在迭代元素時會比較List的當前修改次數(shù)與Itr記錄的次數(shù)是否相等，若不等則拋出ConcurrentModificationException異常蚊夫。所以在使用Iterator遍歷List時不能通過List提供的方法去改變List诉字。

Iterator定義了remove接口，在Itr中也實現(xiàn)了該接口这橙。Itr的reomve方法時安全的奏窑，因為在每次調用Itr的remove時Itr都會重新同步List的當前修改次數(shù)导披，這樣在調用Itr的remove后繼續(xù)通過Itr遍歷List是安全的屈扎。

private class Itr implements Iterator<E> {
    // 初始在0處
    int cursor = 0;
    // 最后返回的元素index
    int lastRet = -1;
    // 保存當前的修改次數(shù)
    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();
        }
    }

    // 刪除前先判斷修改次數(shù)是否一一致鹰晨，一致則調用AbstractList的remove方法。修改后會更新修改次數(shù)止毕，所以使用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();
        }
    }

    // 每次迭代時都會調用該方法比較修改次數(shù)是否有變化
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

四、ListIterator

List擴展了一個支持前后遍歷扁凛、插入和修改的ListIterator迭代器忍疾，ListIterator繼承自Iterator。ListIterator沒有當前元素谨朝，它的index在previous()和next()之間卤妒。List是基于數(shù)組的，對此ListIterator也提供了元素在數(shù)組中位置的相關的接口字币。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> {
    // 創(chuàng)建時要指定開始的位置
    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;
    }
    // 更新最后一個返回的元素席楚，更新后也更新修改次數(shù)咬崔，所以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的修改次數(shù)，所以通過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();
        }
    }
}
最后編輯于 ：
?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
  • 人面猴
    序言：七十年代末兜蠕，一起剝皮案震驚了整個濱河市，隨后出現(xiàn)的幾起案子抛寝，更是在濱河造成了極大的恐慌熊杨，老刑警劉巖，帶你破解...
    沈念sama閱讀 221,548評論 6贊 515
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件盗舰，死亡現(xiàn)場離奇詭異晶府，居然都是意外死亡，警方通過查閱死者的電腦和手機钻趋，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 94,497評論 3贊 399
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進店門川陆，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人蛮位，你說我怎么就攤上這事较沪。” “怎么了土至？”我有些...
    開封第一講書人閱讀 167,990評論 0贊 360
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵购对，是天一觀的道長。 經(jīng)常有香客問我陶因，道長骡苞，這世上最難降的妖魔是什么？ 我笑而不...
    開封第一講書人閱讀 59,618評論 1贊 296
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任楷扬，我火速辦了婚禮解幽，結果婚禮上，老公的妹妹穿的比我還像新娘烘苹。我一直安慰自己躲株，他們只是感情好，可當我...
    茶點故事閱讀 68,618評論 6贊 397
  • 惡毒庶女頂嫁案：這布局不是一般人想出來的
    文/花漫 我一把揭開白布镣衡。 她就那樣靜靜地躺著霜定，像睡著了一般档悠。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上望浩，一...
    開封第一講書人閱讀 52,246評論 1贊 308
  • 城市分裂傳說
    那天辖所，我揣著相機與錄音，去河邊找鬼磨德。 笑死缘回，一個胖子當著我的面吹牛，可吹牛的內容都是我干的典挑。 我是一名探鬼主播酥宴，決...
    沈念sama閱讀 40,819評論 3贊 421
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開眼，長吁一口氣：“原來是場噩夢啊……” “哼您觉！你這毒婦竟也來了拙寡？” 一聲冷哼從身側響起，我...
    開封第一講書人閱讀 39,725評論 0贊 276
  • 萬榮殺人案實錄
    序言：老撾萬榮一對情侶失蹤顾犹，失蹤者是張志新（化名）和其女友劉穎倒庵，沒想到半個月后，有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體炫刷，經(jīng)...
    沈念sama閱讀 46,268評論 1贊 320
  • ?護林員之死
    正文 獨居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內容為張勛視角 年9月15日...
    茶點故事閱讀 38,356評論 3贊 340
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年郁妈，在試婚紗的時候發(fā)現(xiàn)自己被綠了浑玛。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點故事閱讀 40,488評論 1贊 352
  • 活死人
    序言：一個原本活蹦亂跳的男人離奇死亡噩咪，死狀恐怖顾彰，靈堂內的尸體忽然破棺而出，到底是詐尸還是另有隱情胃碾，我是刑警寧澤涨享，帶...
    沈念sama閱讀 36,181評論 5贊 350
  • ?日本核電站爆炸內幕
    正文 年R本政府宣布，位于F島的核電站仆百，受9級特大地震影響厕隧，放射性物質發(fā)生泄漏。R本人自食惡果不足惜俄周，卻給世界環(huán)境...
    茶點故事閱讀 41,862評論 3贊 333
  • 男人毒藥：我在死后第九天來索命
    文/蒙蒙 一吁讨、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧峦朗，春花似錦建丧、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,331評論 0贊 24
  • 一樁弒父案翎朱，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽橄维。三九已至，卻和暖如春拴曲，著一層夾襖步出監(jiān)牢的瞬間挣郭，已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,445評論 1贊 272
  • 情欲美人皮
    我被黑心中介騙來泰國打工疗韵， 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留兑障，地道東北人。 一個月前我還...
    沈念sama閱讀 48,897評論 3贊 376
  • 代替公主和親
    正文 我出身青樓蕉汪，卻偏偏與公主長得像流译，于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子者疤，可洞房花燭夜當晚...
    茶點故事閱讀 45,500評論 2贊 359