NO IMAGE

從上篇部落格,我們知道了Java集合框架分為Collection和Map,此篇部落格開始,將對集合框架中的List,Set,Queue和Map分別總結,進一步學習Java集合。本篇部落格從List出發。

一. List的定義

    List集合代表一個元素有序、可重複的集合,集合中每個元素都有其對應的順序索引。List集合允許加入重複元素,因為它可以通過索引來訪問指定位置的集合元素。List集合預設按元素的新增順序設定元素的索引。

二. List的實現

    1. List listA=new ArrayList();
        底層資料結構是陣列,查詢快,增刪慢;執行緒不安全,效率高

    2. List listB=new Vector();
        底層資料結構是陣列,查詢快,增刪慢;執行緒安全,效率低

    3. List listC=new LinkedList();
        底層資料結構是連結串列,查詢慢,增刪快;執行緒不安全,效率高

三. ArrayList和Vector

    ArrayList和Vector類都是基於陣列實現的List類,其封裝了一個動態的、允許再分配的Object[]陣列。ArrayList或Vector物件使用initalCapacity引數來設定該陣列的長度,當向ArrayList或Vector中新增元素超過了該陣列的長度時,它們的initalCapacity會自動增加。

    (一)ArrayList包含三個建構函式方法,如下:

    1. ArrayList() :Constructs an empty list with an initial capacity of ten.
    構造一個空陣列,其初始容量預設為10.

    2. ArrayList(Collection c) :Constructs a list containing the elements of the specified collection, in the order they are returned by the collection’s iterator.
    按照集合迭代器返回的順序構造包含指定集合元素的列表。

    3. ArrayList(int initialCapacity) :Constructs an empty list with the specified initial capacity.
    構造一個指定初始容量的空陣列。

    若呼叫add()方法,向一個陣列中新增元素,會先呼叫ensureCapacityInternal()方法,該方法用來確保陣列中是否還有足夠容量。最後有個判斷:如果剩餘容量足夠存放這個資料,則進行下一步,如果不夠,則需要執行一個重要的方法:grow(int minCapacity) ,對陣列進行擴容。
    所以說,ArrayList是一個動態擴充套件的陣列,Vector也同樣如此。如果開始就知道ArrayList或Vector集合需要儲存多少個元素,則可以在建立它們時就指定initalCapacity的大小,這樣可以提高效能。
    此外,ArrayList還提供了兩個額外的方法來調整其容量大小:
    1. void ensureCapacity(int minCapacity): 如有必要,增加此 ArrayList 例項的容量,以確保它至少能夠容納最小容量引數所指定的元素數。
    2. void trimToSize():將此 ArrayList 例項的容量調整為列表的當前大小。

    (二)ArrayList支援3種遍歷方式:

    1. 通過迭代器遍歷 :

Integer value = null;
Iterator iter = list.iterator();
while (iter.hasNext()) {
value = (Integer)iter.next();
}

    2. 隨機訪問,通過索引值去遍歷:

Integer value = null;
int size = list.size();
for (int i=0; i<size; i  ) {
value = (Integer)list.get(i);        
}

    3. for迴圈遍歷 :

Integer value = null;
for (Integer integ:list) {
value = integ;
}

遍歷ArrayList時,使用隨機訪問(即,通過索引序號訪問)效率最高,而使用迭代器的效率最低。

四. LinkedList

    LinkedList類是List介面的實現類——這意味著它是一個List集合,可以根據索引來隨機訪問集合中的元素。除此之外,LinkedList還實現了Deque介面,可以被當作成雙端佇列來使用,因此既可以被當成“棧”來使用,也可以當成佇列來使用。
    LinkedList的實現機制與ArrayList完全不同。ArrayList內部是以陣列的形式來儲存集合中的元素的,因此隨機訪問集合元素時有較好的效能;而LinkedList內部以連結串列的形式來儲存集合中的元素,因此隨機訪問集合元素時效能較差,但在插入、刪除元素時效能比較出色。
    (一)LinkedList包含兩個建構函式方法,如下:

    1. LinkedList() :Constructs an empty list.
    構造一個空陣列.

    2. LinkedList(Collection c) :Constructs a list containing the elements of the specified collection, in the order they are returned by the collection’s iterator.
    按照集合迭代器返回的順序構造包含指定集合元素的列表。

    LinkedList呼叫預設建構函式,建立一個連結串列。由於維護了一個表頭,表尾的Node物件的變數。可以進行後續的新增元素到連結串列中的操作,以及其他刪除,插入等操作。也因此實現了雙向佇列的功能,即可向表頭加入元素,也可以向表尾加入元素.

    (二)LinkedList支援多種遍歷方式:

    1.通過迭代器遍歷LinkedList

    2通過快速隨機訪問遍歷LinkedList

    3.通過for迴圈遍歷LinkedList

    4.通過pollFirst()遍歷LinkedList

    5.通過pollLast()遍歷LinkedList

    6通過removeFirst()遍歷LinkedList

    7.通過removeLast()遍歷LinkedList

其中採用逐個遍歷的方式,效率比較高。採用隨機訪問的方式去遍歷LinkedList的方式效率最低。

五. ArrayList和LinkedList效能對比

    ArrayList 是一個陣列佇列,相當於動態陣列。它由陣列實現,隨機訪問效率高,隨機插入、隨機刪除效率低。ArrayList應使用隨機訪問(即,通過索引序號訪問)遍歷集合元素。

    LinkedList 是一個雙向連結串列。它也可以被當作堆疊、佇列或雙端佇列進行操作。LinkedList隨機訪問效率低,但隨機插入、隨機刪除效率高。LinkedList應使用採用逐個遍歷的方式遍歷集合元素。

    如果涉及到“動態陣列”、“棧”、“佇列”、“連結串列”等結構,應該考慮用List,具體的選擇哪個List,根據下面的標準來取捨。

    1. 對於需要快速插入,刪除元素,應該使用LinkedList。
    2. 對於需要快速隨機訪問元素,應該使用ArrayList。
    3. 對於“單執行緒環境” 或者 “多執行緒環境,但List僅僅只會被單個執行緒操作”,此時應該使用非同步的類(如ArrayList)。對於“多執行緒環境,且List可能同時被多個執行緒操作”,此時,應該使用同步的類(如Vector)或支援併發的類。

六. ArrayList專案中的應用

    之前在專案中遇到過一個需求,按規則分發人員,產品和測試理規則理了很久,而我開發時間其實很短,用程式語言來說,他們的規則,無非是我對幾個list集合取並集,交集的操作,而這些操作,List都有實現的方法可直接用,allAll(),retainAll(),最後使用set去重。(set集合將在下篇部落格進行詳細總結)

        List<String> allEmployeesList = new ArrayList<>();
//根據客戶繫結的專線查詢對應的員工,分發該詢價單
List<String> dispatchEmployees = companyLineService.dispatchEmployeeByCompanyLine(customerId, companyIdItem);
logger.info("-------所有繫結該專線員工集合:"   dispatchEmployees);
//查詢對應服務品牌的員工
List<String> dispatchBrandEmployees = companyLineService.dispatchEmployeeByBrand(brand, companyIdItem);
logger.info("-------所有繫結該品牌員工集合:"   dispatchBrandEmployees);
//查詢所有在用的員工
List<String> dispatchUsedEmployee = companyLineService.queryUsedEmployees(companyIdItem);
logger.info("--------所有在用的員工集合:"   dispatchUsedEmployee);
//專線員工集合
allEmployeesList.addAll(dispatchEmployees);
if (allEmployeesList.size() == 0) {
//若未查詢到繫結專線的員工,則將繫結品牌的集合合併
allEmployeesList.addAll(dispatchBrandEmployees);
}
//若專線 品牌集合都不為空,則取兩個集合的差集
if (dispatchEmployees.size() > 0 && dispatchBrandEmployees.size() > 0) {
allEmployeesList.addAll(dispatchEmployees);
allEmployeesList.retainAll(dispatchBrandEmployees);
}
//如果專線 品牌的員工集合為空,則合併其他所有在用的員工集合
if (allEmployeesList.size() == 0) {
allEmployeesList.addAll(dispatchUsedEmployee);
}
//set去除list中的重複元素
Set<String> set = new HashSet<>(allEmployeesList);
logger.info("去重後的所有員工id集合:"   set);
return set;