前面介紹了集合與映射兩類容器,它們的共同特點是每個元素都是唯一的,並且採用二叉樹方式的類型還自帶有序性。然而這兩個特點也存在弊端:其一,為啥內部元素必須是唯一的呢?像手機店賣出了兩部Mate20,雖然這兩部手機一模一樣,但理應保存兩條銷售記錄才是。其二,不管是哈希類型還是二叉類型,居然都不允許按照加 ...
前面介紹了集合與映射兩類容器,它們的共同特點是每個元素都是唯一的,並且採用二叉樹方式的類型還自帶有序性。然而這兩個特點也存在弊端:其一,為啥內部元素必須是唯一的呢?像手機店賣出了兩部Mate20,雖然這兩部手機一模一樣,但理應保存兩條銷售記錄才是。其二,不管是哈希類型還是二叉類型,居然都不允許按照加入時間的先後排序,要知道現實生活中不乏各種先來後到的業務場景。為了更方便地應對真實場景中的各類需求,Java又設計了清單List這麼一種容器,用來處理集合與映射所不支持的業務功能。
提到清單,腦海裡頓時浮現出從上往下排列的一組表格,例如購物清單、願望清單、待辦事項等等,它們的共同點一是都有序號,二是按線性排列。清單里的元素允許重覆加入,並且根據入伙的時間順序先後羅列,這些特征決定了清單是種貼近日常生活的簡易容器。不過Java中的List屬於介面,實際開發用到的是它的一個實現類ArrayList(列表,又稱動態數組)。在某種程度上,列表的確跟數組很像,比如二者的內部元素都分配了整數序號/下標、都支持通過序號/下標來訪問指定位置的元素等等。但列表貴為容器中的一員,自然擁有幾點數組所不能比擬的優勢,包括但不限於:
一、列表允許動態添加新元素,不管調用多少次add方法,也不必擔心列表空間不夠用的問題。下麵代碼便演示瞭如何聲明列表實例並對其依次添加元素:
// 創建一個列表(動態數組),其元素為MobilePhone類型 ArrayList<MobilePhone> list = new ArrayList<MobilePhone>(); list.add(new MobilePhone("華為", 5000)); // 第一個添加的元素,預設分配序號為0 list.add(new MobilePhone("小米", 2000)); // 第二個添加的元素,預設分配序號為1 list.add(new MobilePhone("OPPO", 4000)); // 第三個添加的元素,預設分配序號為2 list.add(new MobilePhone("vivo", 1000)); // 第四個添加的元素,預設分配序號為3 list.add(new MobilePhone("vivo", 1000)); // 第五個添加的元素,預設分配序號為4
而數組的大小一經初始化設定就不可調整,除非另外給它分配新的數組空間;
二、數組只能對指定位置的元素進行修改操作,列表不但支持修改指定位置的元素(set方法),還支持在指定位置插入新元素(add方法),或者移除指定位置的元素(remove方法)。
三、數組只有兩種遍歷方式:按下標遍歷、通過簡化的for迴圈遍歷。而列表支持多達四種的遍歷方式,分別說明如下:
1、簡化的for迴圈。該方式同樣適用於數組和容器,具體的遍歷代碼示例如下:
// 第一種遍歷方式:簡化的for迴圈同樣適用於數組和容器 for (MobilePhone for_item : list) { System.out.println(String.format("for_item:%s %d", for_item.getBrand(), for_item.getPrice())); }
2、迭代器遍歷。該方式與利用迭代器遍歷集合是一樣,都要先獲得當前容器的迭代器,然後依次調用迭代器的next逐個獲取元素。利用迭代器遍歷列表的代碼如下所示:
// 第一種遍歷方式:簡化的for迴圈同樣適用於數組和容器 for (MobilePhone for_item : list) { System.out.println(String.format("for_item:%s %d", for_item.getBrand(), for_item.getPrice())); }
3、索引遍歷。這裡的索引是以0開始的序號,對應於數組的下標,只不過列表通過get方法獲取指定位置的元素,而數組通過方括弧引用某個下標。下麵是使用索引遍歷列表的代碼例子:
// 第三種遍歷方式:與數組通過下標訪問相似,列表通過索引獲取指定位置的元素 for (int i = 0; i < list.size(); i++) { MobilePhone index_item = list.get(i); System.out.println(String.format("index_item:%s %d", index_item.getBrand(), index_item.getPrice())); }
4、forEach遍歷。Java8之後,每種容器都支持聯合應用forEach與Lambda表達式的遍歷方式,該方式的遍歷代碼見下:
// 第四種遍歷方式:使用forEach方法夾帶Lambda表達式進行遍歷 list.forEach(each_item -> System.out.println(String.format( "each_item:%s %d", each_item.getBrand(), each_item.getPrice())));
儘管列表對於大多數的業務場景來說夠用了,可是仍舊無法滿足部分特定的業務需求,因為ArrayList預設把新元素添加到列表末尾,也不存在預設的刪除操作。而在電腦科學常見的數據結構當中,至少還有兩種是列表所不能實現的,其中一個叫做隊列Deque,另一個叫做棧Stack。
隊列取材於生活中的排隊場景,譬如春運期間大家在火車站排隊買車票,雖然有個別人嚷嚷著“我要插隊”且自顧自地插了進去,也有人忍受不了漫長的等待而中途放棄排隊改為騎單車回家,但多數人都會循規蹈矩地從隊尾開始排隊,買了票之後從隊首離隊。於是排隊業務就抽象成為這麼一種隊列結構:添加時預設往末尾添加,刪除時預設從開頭刪除。
至於棧則取材於電腦系統的寄存器操作,棧的特點是裡面保存的數據為先進後出(同時也是後進先出),即最早添加的元素會被最後移除、最晚添加的元素會被最先移除。基於棧具有的數據先進後出特性,它常用於保存中斷時的斷點、保存子程式調用後的返回點、保存CPU的現場數據、在程式間傳遞參數等等。就棧作為一種容器的角色而言,每次添加的元素會預設加到開頭,且每次刪除操作會預設刪去開頭的元素,從而實現後進先出/先進後出的機制。
然而不管是隊列還是棧,它們的存儲形式都如同清單那樣線性排列,區別在於數據進出的預設方位。因此Java把隊列、棧以及清單三者加以融合,推出了鏈表LinkedList(又稱雙端隊列)這種數據結構,它一起實現了List與Deque介面,併在某種程度上模擬了棧的功能,從而變成專治各種不服的萬能清單。
作為清單大家族的一員,鏈表LinkedList的基本用法與列表ArrayList相同,並基於它的三個祖宗分別進行了下列方法拓展:
1、在清單List的功能增強方面,補充瞭如下的擴展方法:
addFirst:添加到清單開頭
addLast:添加到清單末尾
removeFirst:刪除清單開頭的元素
removeLast:刪除清單末尾的元素
getFirst:獲取清單開頭的元素
getLast:獲取清單末尾的元素
2、在隊列Queue的功能實現方面,提供瞭如下的隊列方法:
offer:添加到隊列末尾
offerFirst:添加到隊列開頭
offerLast:添加到隊列末尾
peek:獲取隊列開頭的元素
peekFirst:獲取隊列開頭的元素
peekLast:獲取隊列末尾的元素
poll:刪除隊列開頭的元素
pollFirst:刪除隊列開頭的元素
pollLast:刪除隊列末尾的元素
3、在棧Stack的功能模擬方面,添加瞭如下的額外方法:
pop:隊列開頭的元素出棧,相當於方法removeFirst和pollFirst
push:新元素入棧,相當於方法addFirst和offerFirst
總的來說,鏈表的數據存儲兼顧清單和隊列的組織結構,常用於對數據進出有特殊要求的場合,例如採取先進先出FIFO的隊列操作,以及採取先進後出FILO的棧操作。
更多Java技術文章參見《Java開發筆記(序)章節目錄》