Java 集合系列（四）—— ListIterator 源碼分析

来源:https://www.cnblogs.com/phpstudy2015-6/archive/2019/04/05/10660457.html
-Advertisement-
Play Games

以腦圖的形式來展示Java集合知識，讓零碎知識點形成體系 Iterator 對比 Iterator（迭代器）是一種設計模式，是一個對象，用於遍歷集合中的所有元素。 Iterator 包含四個方法，分別是：next()、hasNext()、remove()、forEachRemaining(Consu ...


以腦圖的形式來展示Java集合知識，讓零碎知識點形成體系

Iterator 對比

  Iterator（迭代器）是一種設計模式，是一個對象，用於遍歷集合中的所有元素。
  Iterator 包含四個方法，分別是：next()、hasNext()、remove()、forEachRemaining(Consumer<? super E> action)

  Collection 介面繼承 java.lang.Iterable，因此所有 Collection 實現類都擁有 Iterator 迭代能力。
  逆向思考，Iterable 面向眾多的 Collection 類型實現類，定義的方法就不可能太定製化，因此 Iterator 定義的功能比較簡單。
  僅有如上所列出來的四種方法，並且該迭代器只能夠單向移動。

  由於 List 類型的 Collection 是一個有序集合，對於擁有雙向迭代是很有意義的。
  ListIterator 介面則在繼承 Iterator 介面的基礎上定義了：add(E newElement)、set(E newElement)、hasPrevious()、previous()、nextIndex()、previousIndex() 等方法，使得 ListIterator 迭代能力增強，能夠進行雙向迭代、迭代過程中可以進行增刪改操作。

現象與問題

 

  1. add() 方法在迭代器位置前面添加一個新元素
  2. next() 與 previous() 返回越過的對象
  3. set() 方法替換的是 next() 和 previous() 方法返回的上一個元素
  4. next() 後，再 remove() 則刪除前面的元素；previous() 則會刪除後面的元素
 1         List<String> list = new LinkedList<>();
 2         list.add("aaa");
 3         list.add("bbb");
 4         list.add("ccc");
 5 
 6         ListIterator<String> listIterator = list.listIterator();
 7 
 8         //迭代器位置： add-1 | aaa bbb ccc
 9         listIterator.add("add-1");
10         // add-1 add-1 | aaa bbb ccc
11         listIterator.add("add-2");
12 
13         // 返回： aaa
14         // add-1 add-1 aaa | bbb ccc
15         listIterator.next();
16         // add-1 add-1 aaa-set | bbb ccc
17         listIterator.set("aaa-set");
18         // bbb
19         // add-1 add-1 aaa-set bbb | ccc
20         listIterator.next();
21 
22         // 返回： bbb
23         // add-1 add-1 aaa-set | bbb ccc
24         listIterator.previous();
25         // add-1 add-1 aaa-set | bbb-set ccc
26         listIterator.set("bbb-set");
27 
28         // 刪除 bbb-set
29         listIterator.remove();
30         listIterator.remove();
31 
32         System.out.println(list);

 

很多書本都有給出這樣子的結論：

  • 鏈表有 n 個元素，則有 n+1 個位置可以添加新元素；

  • add() 方法只依賴迭代器的+位置；remove() 和 set() 方法依賴於迭代器的狀態（此時迭代的方向）；

  • 連續兩個 remove() 會出錯，remove() 前應先執行 next() 或 previous()。

迭代同時修改問題： 

  一個迭代器指向另一個迭代器剛剛刪除的元素，則現在這個迭代器就變成無效的了（節點刪除被回收；即使沒被回收，該節點的前後引用也被重置為null）。
鏈表迭代器有能夠檢測到這種修改的功能，當發現集合被修改了，將會拋出一個 ConcurrentModificationException 異常

  為什麼出現上面的這些現象與問題呢，我們還是從源碼中尋找答案吧

 

源碼分析

  有多個集合類根據自己的特點實現了 ListIterator 介面，其實現都大同小異，這裡我們主要分析 LinkedList 中所實現的 ListIterator。

  首先我們來分析 LinkedList 的 listIterator() 和 listIterator(int index) 方法獲取 ListIterator 迭代器過程。

 1 // AbstractList.java
 2 // listIterator() 方法 LinkedList 類本身並沒有重寫，需要追溯到 AbstractList 抽象類
 3 
 4     // 獲取 ListIterator 迭代器
 5     public ListIterator<E> listIterator() {
 6         return listIterator(0);
 7     }
 8 
 9     public ListIterator<E> listIterator(final int index) {
10         rangeCheckForAdd(index);    // 檢查 index 範圍是否超出
11 
12         return new ListItr(index);  // 該抽象類也有實現 ListItr 類
13     }
14 
15     private void rangeCheckForAdd(int index) {
16         if (index < 0 || index > size())
17             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
18     }
  1 // LinkedList.java
  2 // LinkedList 類重寫了 listIterator(int index) 方法
  3 
  4     public ListIterator<E> listIterator(int index) {
  5         checkPositionIndex(index);  // 同理 檢查 index 範圍；相關代碼就不貼了
  6         return new ListItr(index);
  7     }
  8 
  9 
 10     private class ListItr implements ListIterator<E> {
 11         private Node<E> lastReturned;   // 上一次處理的節點
 12         private Node<E> next;   // 即將要處理的節點
 13         private int nextIndex;  // 即將要處理的節點的 index
 14         // modCount 表示集合和迭代器修改的次數；expectedModCount 表示當前迭代器對集合修改的次數
 15         private int expectedModCount = modCount;
 16 
 17         ListItr(int index) {
 18             // assert isPositionIndex(index);
 19             next = (index == size) ? null : node(index);
 20             nextIndex = index;
 21         }
 22 
 23         public boolean hasNext() {
 24             return nextIndex < size;
 25         }
 26 
 27         /**
 28         * 處理對象：迭代器當前的 next 節點
 29         * 將處理目標儲到 lastReturned 變數中
 30         * 然後將當前的 next.next 節點保存起來，用於下一次迭代處理
 31         * nextIndex 同時 +1
 32         * 返回 lastReturned.item 元素
 33         * 執行後：lastReturned 指向該次處理的節點；next、nextIndex 指向該次處理節點的後一個節點
 34         */
 35         public E next() {
 36             // 檢查 modCount 與 expectedModCount 是否相等
 37             // 實際檢查該鏈表是否被其他迭代器或者集合本身修改
 38             checkForComodification();
 39             // 判斷是否存在 next 節點
 40             if (!hasNext())
 41                 throw new NoSuchElementException();
 42             
 43             lastReturned = next;    // 將這次返回的 node 節點更新到迭代器中的 lastReturned 變數
 44             next = next.next;   // 將下一次需要處理 node 節點更新會 next 變數
 45             nextIndex++;    // 變數 nextIndex +1
 46             return lastReturned.item;   // 返回元素
 47         }
 48 
 49         public boolean hasPrevious() {
 50             return nextIndex > 0;
 51         }
 52 
 53         /**
 54         * 處理對象：迭代器當前的 next.prev 節點
 55         * 將處理目標儲到 lastReturned 變數中
 56         * 然後將當前的 next.prev 節點保存起來，用於下一次迭代處理
 57         * nextIndex 同時 -1
 58         * 返回當前的 next.item 元素
 59         * 執行後：next、lastReturned、nextIndex 指向該次處理節點的前一個節點
 60         */
 61         public E previous() {
 62             checkForComodification();
 63             // 判斷是否存在 prev 節點
 64             if (!hasPrevious())
 65                 throw new NoSuchElementException();
 66 
 67             // 處理當前 next 的 prev 節點
 68             // 特殊情況：next = null 時，則它的 prev 節點為 last 節點  
 69             lastReturned = next = (next == null) ? last : next.prev;    
 70             nextIndex--;    // nextIndex -1
 71             return lastReturned.item;
 72         }
 73 
 74         public int nextIndex() {
 75             return nextIndex;
 76         }
 77 
 78         public int previousIndex() {
 79             return nextIndex - 1;
 80         }
 81 
 82         /**
 83         * 處理對象：lastReturned
 84         * 刪除 lastReturned 指向的節點，並置為 null
 85         * 同時保證 next 和 nextIndex 指向同一個節點
 86         */
 87         public void remove() {
 88             checkForComodification();   // 同理， 檢查 modCount 與 expectedModCount 是否相等
 89             if (lastReturned == null)
 90                 throw new IllegalStateException();
 91 
 92             Node<E> lastNext = lastReturned.next;  // 暫存 lastReturned 的 next 節點，用於恢復迭代狀態
 93             unlink(lastReturned);   // 刪除最後返回的節點    modCount++;
 94             
 95             // 分迭代方向處理（因為刪除一個節點後，需要恢復迭代狀態：next 和 nextIndex 指向同一個節點）
 96             if (next == lastReturned)   // next 與 lastReturned 節點相同則表明最近一次迭代操作是 previous()
 97                 next = lastNext;        // 刪除了原有 next 指向的節點，因此 nextIndex 相對指向的節點變為 next.next，需要更新 next 變數的指向
 98             else
 99                 nextIndex--;    // next() 迭代方向；刪除了next前面的節點，因此next的相對位置發生變化，需要 nextIndex -1
100             lastReturned = null;    
101             expectedModCount++;     // 同時 expectedModCount++
102         }
103 
104         /**
105         * 處理對象：lastReturned
106         */
107         public void set(E e) {
108             if (lastReturned == null)
109                 throw new IllegalStateException();
110             checkForComodification();
111             lastReturned.item = e;
112         }
113 
114         /**
115         * 分位置進行添加
116         */
117         public void add(E e) {
118             checkForComodification();
119             lastReturned = null;
120             if (next == null)
121                 linkLast(e);
122             else
123                 linkBefore(e, next);
124             nextIndex++;
125             expectedModCount++;
126         }
127 
128         public void forEachRemaining(Consumer<? super E> action) {
129             Objects.requireNonNull(action);
130             while (modCount == expectedModCount && nextIndex < size) {
131                 action.accept(next.item);
132                 lastReturned = next;
133                 next = next.next;
134                 nextIndex++;
135             }
136             checkForComodification();
137         }
138 
139         /**
140         * 檢查 modCount 與 expectedModCount 是否相等，否則拋出錯誤
141         * ListIterator 迭代器進行增刪操作時，都會同時對這兩個變數 +1
142         * 目的：
143         * 使用 ListIterator 迭代器期間，LinkedList 對象有且只能當前這一個迭代器可以進行修改
144         * 避免 LinkedList 對象本身以及其他迭代器進行修改導致鏈表混亂
145         */
146         final void checkForComodification() {
147             if (modCount != expectedModCount)
148                 throw new ConcurrentModificationException();
149         }
150     }

 

 

小結

  總的來說 ListIterator 是記錄 List 位置的一個對象，它主要的成員變數是 lastReturned、next、nextIndex 以及 expectedModCount。

  1. next() 處理的是 next 節點，返回 next.item

  2. previous() 處理的是 next.prev 節點 返回 next.prev.item

  3. remove() 處理的是 lastReturned 節點，並置為null，但要註意的是，刪除節點後的 next 與 nextIndex 需分情況處理。

  4. set() 處理的是 lastReturned 節點，lastReturned.item = e

  5. add() 添加，並將 lastReturned 置為null

  這就很好地解釋上面所提到的一些現象與問題了。
  典型的就是連續兩個 remove() 會報錯，那是因為第一個 reomve() 之後 lastReturned 被置為null；第二個 remove() 處理的對象是null，因此炮錘 IllegalStateException

 

知識腦圖

From Java Core Knowledge Tree

 

 

在 github 上建了一個 repository ，Java Core Knowledge Tree，各位看官若是喜歡請給個star，以示鼓勵，謝謝。
https://github.com/suifeng412/JCKTree

 

（以上是自己的一些見解，若有不足或者錯誤的地方請各位指出）

 作者：那一葉隨風   http://www.cnblogs.com/phpstudy2015-6/

 原文地址： https://www.cnblogs.com/phpstudy2015-6/p/10660457.html

 聲明：本博客文章為原創，只代表本人在工作學習中某一時間內總結的觀點或結論。轉載時請在文章頁面明顯位置給出原文鏈接

 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • Node.js http.createServer 簡單服務配置
    基本實現： 解析GET參數： 解析POST： ...
  • 原生 JS 實現掃雷 (分析+代碼實現)
    原生 JavaScript 實現掃雷 完整思路分析，代碼實現。 ...
  • C++STL之Vector的應用
    這是我第一次寫博客，請多指教！ vector是一種向量容器，說白了就是可以改變大小的數組。 vector是一個模板類，如果直接這樣會報錯： 1 vector a; //報錯，因為要指定模板。 需要像這樣： 那麼，什麼是 模板 呢？ 模板是C++支持參數化多態的工具，使用模板可以使用戶為類或者函數聲明 ...
  • 結合JDK源碼看設計模式——裝飾者模式
    定義 在不改變原有對象的基礎之上，將功能附加到對象上 適用場景 詳解 在看到定義的時候，可能很多人會想，這不就是繼承嗎？的確很像，不過是比繼承更加有彈性的替代方案。就像原型模式和new之間的關係一樣，有區別，但是區別又不是特別大。裝飾者一個很重要的詞就是動態，他可以靈活的選擇要這個功能還是不要。在裝 ...
  • 第一式 策略模式
    策略模式 一 開發模擬鴨子游戲 已經有一個很成功的鴨子模擬游戲，裡面有各種鴨子，一邊游泳，一邊呱呱叫。該系統採用的標準OO技術，設計了一個鴨子超類，並讓各種鴨子繼承此超類。 實現如下：超類中定義了鴨子的各種行為，包括呱呱叫，游泳，外觀等。由於各種鴨子的外觀是不一樣的，display方法抽象出來，各個 ...
  • java--變數，常量，數據類型的聲明及使用
    一、概念： 變數是指記憶體中的一個存儲區域，該區域要有自己的名稱（變數名）、類型（數據類型），該區域的數據可以在同一數據類型的範圍內不斷變化值； 二、變數的使用註意事項： 1、Java中的變數必須聲明後才能進行使用。 2、變數的作用域：在一對｛｝中為有效區間。 3、需要進行初始化後才能使用變數。 三、 ...
  • Rabbit安裝(windows)
    安裝rabbit後，啟動服務，瀏覽器打開控制台找不到。查百度說是要裝插件。翻了好幾篇都是互相抄，沒有能用到。 多翻了幾篇終於找到一個靠譜的。可以打開控制台了。記錄下： 首先要安裝Erlang語言支持，我用的是 安裝完Erlang後，需要配置環境變數 再配置path變數 安裝rabbit。安裝路徑不要 ...
  • Springboot項目redisTemplate實現輕量級消息隊列
    背景 公司項目有個需求, 前端上傳excel文件, 後端讀取數據、處理數據、返回錯誤數據, 最簡單的方式同步處理, 客戶端上傳文件後一直阻塞等待響應, 但用戶體驗無疑很差, 處理數據可能十分耗時, 沒人願意傻等, 由於項目暫未使用ActiveMQ等消息隊列中間件, 而redis的lpush和rpop ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類