java_集合體系之List體系總結、應用場景——07

摘要：

總結很重要、他能客觀的展現出你對這個體系的了解程度、首先要對整體的結構架構要掌握、再細化到每個分支的特點、再比較不同分支之間的相同點、不同點、再根據他們不同的特性分析他們的應用場景。

一：List的整體架構圖

java_集合體系之List體系總結、應用場景——07java_集合體系之List體系總結、應用場景——07

線條簡單說明：

1、上圖中虛線且無依賴字樣、說明是直接實作的接口

2、虛線但是有依賴字樣、說明此類依賴與接口、但不是直接實作接口

3、實線是繼承關系、類繼承類、接口繼承接口

類或接口說明：

1、Collection：高度抽象出來的集合、定義某一類集合所具有的基本的方法、标準。

2、Iterable：辨別性接口、要求子類提供擷取Iterator方法、并且要實作Iterator具有的幾個方法。

3、Iterator：疊代器、用于疊代Collection中元素、要求子類必須實作擷取Iterator的方法、

4、ListIterator：用于疊代List集合的疊代器、要求List子類必須實作擷取ListIterator方法、并且實作其必須方法。

5、List：以隊列的形式存儲、操作元素、定義了這種形式的集合所具有的基本方法、以及方法的定義。要求List實作類集合中每個元素都有索引、索引值從0開始、

6、Queue：以隊列的資料結構存儲、操作元素、Queue對于插入、提取和檢查操作。每個方法都存在兩種形式：一種抛出異常（操作失敗時），另一種傳回一個特殊值（null 或 false，具體取決于操作）。

7、Deque：實作Queue、使子類可以以雙向連結清單的資料結構形式存儲、操作資料、從這可以看出其子類的靈活性較大。

8、Enumeration：枚舉、用于Vector及其子類疊代元素、他避免了fail-fast機制、使得Vector及其子類在疊代元素的時候可以保證線程安全。

9、AbstractCollection：Collection的實作類、要求需要實作Collection接口的類都必須從它繼承、目的是用于簡化程式設計。

10、 AbstractList：繼承AbstractCollection、實作List接口中定義方法、目的也是簡化程式設計、并且其内部提供了擷取Iterator、ListIterator的方法。

11、 AbstractSequencedList：繼承AbstractList、使得List支援有序隊列、比如連結清單形式存儲操作元素。

12、 ArrayList：繼承AbstractList、以動态數組的形式存儲、操作元素、

13、 LinkedList：繼承AbstractSequencedList、實作Deque、List接口、以雙向連結清單的形式存儲、操作元素。

14、 Vector：繼承AbstractList、以動态數組的形式存儲、操作元素、線程安全

15、 Stack：繼承Vector、在Vector的基礎上新增以棧的形式存儲、操作元素。

二：LinkedList與ArrayList

1、相同之處

a）都直接或者間接繼承了AbstractList、都支援以索引的方式操作元素

b）都不必擔心容量問題、ArrayList是通過動态數組來儲存資料的、當容量不足時、數組會自動擴容、而LinkedList是以雙向連結清單來儲存資料的、不存在容量不足的問題

c）都是線程不安全的、一般用于單線程的環境下、要想在并發的環境下使用可以使用Collections工具類包裝。

2、不同之處

a）ArrayList是通過動态數組來儲存資料的、而LinkedList是以雙向連結清單來儲存資料的

b）相對與ArrayList而言、LinkedList實作了Deque接口、Deque繼承了Queue接口、同時LinkedList繼承了AbstractSequencedList類、使得LinkedList在保留使用索引操作元素的功能的同時、也實作了雙向連結清單所具有的功能、這就決定了LinkedList的特定

c）對集合中元素進行不同的操作效率不同、LinkedList善于删除、添加元素、ArrayList善于查找元素。本質就是不同資料結構之間差異。

三：ArrayList與Vector

1、相同之處：

a）都是繼承AbstractList、擁有相同的方法的定義、

b）内部都是以動态數組來存儲、操作元素的、并且都可以自動擴容。

2、不同之處：

a）線程安全：ArrayList是線程不安全的、适用于單線程的環境下、Vector是線程安全的、使用與多線程的環境下。

b）構造方法：Vector有四個構造方法、比ArrayList多一個可以指定每次擴容多少的構造方法

c）擴容問題：每當動态數組元素達到上線時、ArrayList擴容為：“新的容量”=“(原始容量x3)/2 + 1”、而Vector的容量增長與“增長系數有關”，若指定了“增長系數”，且“增長系數有效(即，大于0)”；那麼，每次容量不足時，“新的容量”=“原始容量+增長系數”。若增長系數無效(即，小于/等于0)，則“新的容量”=“原始容量 x 2”。

d）效率問題：因為Vector要同步方法、這個是要消耗資源的、是以效率會比較低下

e）Vector為擺脫fail-fast機制、自己内部多提供了一種疊代方法Enumeration、

四：LinkedList、ArrayList、Vector、Stack、Array

1、不同操作的效率對比

關于上面四個集合加一個數組、在這裡給出一個表格用于表示他們的不同的操作的效率的排名、這樣更直覺、

實作機制	随機通路	疊代操作	插入操作	删除操作
數組	連續記憶體區保護元素	1	不支援	不支援	不支援
ArrayList	以數組儲存元素	2	2	2	2
Vector	以數組儲存元素	3	3	3	3
Stack	以數組儲存元素	3	3	3	3
LinkedList	以連結清單儲存元素	4	1	1	1

通過執行個體來驗證上面表格的内容、由于數組比較特殊、他是犧牲的長度的變化直接在記憶體中開辟空間來存儲元素、是以查詢效率是毋庸置疑的、同時由于size一旦确定就不能改變、是以插入删除不支援。是以下面驗證沒有關于Array的的驗證

2、示例：

package com.chy.collection.example;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;
import java.util.Vector;

public class EfficiencyTest {
	
	private static ArrayList<String> arrayList = new ArrayList<String>();
	private static Vector<String> vector = new Vector<String>();
	private static Stack<String> stack = new Stack<String>();
	private static LinkedList<String> linkedList = new LinkedList<String>();

	/**
	 * 測試插入方法（每次都将新增加的元素插入到集合開始處）、注意不要寫成 add(Object o)方法、具體原因自己分析
	 */
	private static void testInsert(){
		testInsert(arrayList);
		testInsert(vector);
		testInsert(stack);
		testInsert(linkedList);
	}
	
	/**
	 * 測試随機通路效率
	 */
	private static void testRandomAccess(){
		testRandomAccess(arrayList);
		testRandomAccess(vector);
		testRandomAccess(stack);
		testRandomAccess(linkedList);
	}
	
	/**
	 * 測試Iterator疊代效率 
	 */
	private static void testIterator(){
		testIterator(arrayList);
		testIterator(vector);
		testIterator(stack);
		testIterator(linkedList);
	}
	
	/**
	 * 測試删除效率
	 */
	private static void testDelete(){
		testDelete(arrayList);
		testDelete(vector);
		testDelete(stack);
		testDelete(linkedList);
	}
	
	private static void testInsert(List<String> list){
		long start = currentTime();
		for (int i = 0; i < 10000; i++) {
			list.add(0,"a");
		}
		long end = currentTime();
		System.out.println("the add method of " + list.getClass().getName() + " use time : " + (end - start) + "ms");
	}
	
	private static void testRandomAccess(List<String> list){
		long start = currentTime();
		for (int i = 0; i < list.size(); i++) {
			list.get(i);
		}
		long end = currentTime();
		System.out.println("the random access method of " + list.getClass().getName() + " use time : " + (end - start) + "ms");
	}
	
	private static void testIterator(List<String> list){
		long start = currentTime();
		Iterator<String> it = list.iterator();
		while(it.hasNext()){
			it.next();
		}
		long end = currentTime();
		System.out.println("the iterator method of " + list.getClass().getName() + " use time : " + (end - start) + "ms");
	}
	
	private static void testDelete(List<String> list){
		long start = currentTime();
		for (int i = 0; i < 10000; i++) {
			if(!list.isEmpty()){
				list.remove(0);
			}
		}
		long end = currentTime();
		System.out.println("the delete method of " + list.getClass().getName() + " use time : " + (end - start) + "ms");
	}
	
	private static long currentTime(){
		return System.currentTimeMillis();
	}
	
	public static void main(String[] args) {
		testInsert();
		System.out.println("==========================================================");
		testRandomAccess();
		System.out.println("==========================================================");
		testIterator();
		System.out.println("==========================================================");
		testDelete();
	}
}

運作結果：

the add method of java.util.ArrayList use time : 32ms
the add method of java.util.Vector use time : 47ms
the add method of java.util.Stack use time : 31ms
the add method of java.util.LinkedList use time : 15ms
==========================================================
the random access method of java.util.ArrayList use time : 15ms
the random access method of java.util.Vector use time : 16ms
the random access method of java.util.Stack use time : 17ms
the random access method of java.util.LinkedList use time : 47ms
==========================================================
the iterator method of java.util.ArrayList use time : 16ms
the iterator method of java.util.Vector use time : 15ms
the iterator method of java.util.Stack use time : 17ms
the iterator method of java.util.LinkedList use time : 16ms
==========================================================
the delete method of java.util.ArrayList use time : 47ms
the delete method of java.util.Vector use time : 31ms
the delete method of java.util.Stack use time : 32ms
the delete method of java.util.LinkedList use time : 15ms

不同的運作環境、差異可能比較大。

3、差異原因分析：

在這裡不會主要讨論所有的差異、而是通過源碼的方式分析LinkedList與Arraylist、ArrayList與Vector在随機通路、插入、删除元素方面的差異原因、至于疊代Iterator、他們都是用從AbstractList繼承的擷取Iterator方法、差異不大、不再比較。

ArrayList與LinkedList

a）ArrayList的随機通路效率高于LinkedList：

随機通路是通過索引去查找元素的、LinkedList關于擷取指定索引處值的源碼：

/** 擷取index處的元素*/
    public E get(int index) {
        return entry(index).element;
    }
    /**  擷取雙向連結清單LinkedList中指定位置的節點、是LinkedList實作List中通過index操作元素的關鍵*/
    private Entry<E> entry(int index) {
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size);
        Entry<E> e = header;
        if (index < (size >> 1)) {
            for (int i = 0; i <= index; i++)
                e = e.next;
        } else {
            for (int i = size; i > index; i--)
                e = e.previous;
        }
        return e;
    }

關于擷取指定索引處的值的源碼：

/** 檢測下标是否越界*/
    private void RangeCheck(int index) {
	if (index >= size)
	    throw new IndexOutOfBoundsException(
		"Index: "+index+", Size: "+size);
    }
    /** 擷取ArrayList中索引為index位置的元素*/
    public E get(int index) {
    	RangeCheck(index);

    	return (E) elementData[index];
    }

對比兩者源碼可以看出、LinkedList擷取指定索引處的值是通過二分法先确定索引所在範圍之後、在逐個查找、直到找到指定索引處、并且對每個索引都是如此、相比于ArrayList直接定位到index處的值來講、無疑是非常浪費時間、消耗資源的、

b）ArrayList的插入、删除操作效率低于LinkedList的原因：

對于指定index處的插入、删除、ArrayList和LinkedList都是先通過索引查找到指定位置、然後進行下一步的插入删除操作、上面我們知道LinkedList是先通過二分法查找index範圍再确定index具體位置、但是ArrayList是直接定位到index處、為什麼LinkedList反而快？依然通過源碼找原因。

ArrayList關于指定位置的元素的插入：

/**
     * 確定此ArrayList的最小容量能容納下參數minCapacity指定的容量、
     * 1、minCapacity大于原來容量、則将原來的容量增加(oldCapacity * 3)/2 + 1;
     * 2、若minCapacity仍然大于增加後的容量、則使用minCapacity作為ArrayList容量
     * 3、若minCapacity不大于增加後的容量、則使用增加後的容量。
     */
    public void ensureCapacity(int minCapacity) {
		modCount++;
		int oldCapacity = elementData.length;
		if (minCapacity > oldCapacity) {
		    Object oldData[] = elementData;
		    int newCapacity = (oldCapacity * 3)/2 + 1;
	    	    if (newCapacity < minCapacity)
	    	    	newCapacity = minCapacity;
	            // minCapacity is usually close to size, so this is a win:
	            elementData = Arrays.copyOf(elementData, newCapacity);
		}
    }
    /** 将指定元素添加到指定的索引處 、
     *	注意：
     *	1、如果指定的index大于Object[] 的size或者小于0、則抛IndexOutOfBoundException
     *	2、檢測Object[]是否需要擴容
     *	3、 将從index開始到最後的元素後移一個位置、
     *	4、将新添加的元素添加到index去。
     */
    public void add(int index, E element) {
		if (index > size || index < 0)
		    throw new IndexOutOfBoundsException(
			"Index: "+index+", Size: "+size);
	
		ensureCapacity(size+1);  // Increments modCount!!
		System.arraycopy(elementData, index, elementData, index + 1,
				 size - index);
		elementData[index] = element;
		size++;
    }

LinkedList關于指定位置的元素的插入：

/** 在index前添加節點，且節點的值為element*/
    public void add(int index, E element) {
        addBefore(element, (index==size ? header : entry(index)));
    }
    /**  擷取雙向連結清單LinkedList中指定位置的節點、是LinkedList實作List中通過index操作元素的關鍵*/
    private Entry<E> entry(int index) {
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size);
        Entry<E> e = header;
        if (index < (size >> 1)) {
            for (int i = 0; i <= index; i++)
                e = e.next;
        } else {
            for (int i = size; i > index; i--)
                e = e.previous;
        }
        return e;
    }
  //建立節點、節點值是e、将建立的節點添加到entry之前
    private Entry<E> addBefore(E e, Entry<E> entry) {
    	//覺得難了解的可以先花個幾分鐘看一下鍊式結構資料、最好是圖檔形式的
    	//建立節點實體
		Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
		//将參照節點原來的上一個節點（即插在誰前面的）的下一個節點設定成newEntry
		newEntry.previous.next = newEntry;
		//将參照節點（即插在誰前面的）的前一個節點設定成newEntry
		newEntry.next.previous = newEntry;
		size++;
		modCount++;
		return newEntry;
    }

對比上面代碼可以看出來ArrayList每當插入一個元素時、都會調用System.arraycopy()将指定位置後面的所有元素後移一位、重新構造一個數組、這是比較消耗資源的、而LinkedList是直接改變index前後元素的上一個節點和下一個節點的引用、而不需要動其他的東西、是以效率很高。

ArrayList與Vector：

ArrayList、Vector都是繼承與AbstractList、并且在類結構上沒有多少差異、但是因為Vector要同步方法、是以在性能上不如ArrayList、從源碼也可以看出Vector許多方法都是使用關鍵字synchronized修飾的。不再貼源碼

總結：

學以緻用、最後總結下上述List集合體系的各個類的使用環境：

1、當需要對集合進行大量的查詢時、并且是單線程環境下使用ArrayList

2、當需要對集合進行大量添加、删除時、并且是單線程環境下使用LinkedList、

3、當多線程時、需要對集合進行大量的查詢時、可以考慮使用Vector或者Stack、但是不建議、我們可以使用多次提到的Collections類包裝。

java_集合體系之List體系總結、應用場景——07java_集合體系之List體系總結、應用場景——07

java_集合體系之List體系總結、應用場景——07

一：List的整體架構圖

二：LinkedList與ArrayList

1、相同之處

2、不同之處

三：ArrayList與Vector

1、相同之處：

2、不同之處：

四：LinkedList、ArrayList、Vector、Stack、Array

1、不同操作的效率對比

2、示例：

3、差異原因分析：

總結：

更多内容：java_集合體系之總體目錄——00

繼續閱讀

java.lang.UnsupportedOperationException——Collections.emptyList()和Arrays.asList 源碼分析

ArrayList 集合中怎麼插入元素的

Java中ArrayList集合

java集合之ArrayList詳解

java源碼分析：ArrayList的擴容機制

ArrayList自動擴容解析

JDK1.8 ArrayList詳解

JDK1.8源碼之ArrayList

ArrayList中modCount的作用

黑馬程式員_日記39_ArrayList字元串集合去重

JAVA學習.JAVA集合類型Collection.List.ArrayList&LinkedList

Java集合在JDK1.7和JDK1.8中的不同——JDK1.7和JDK1.8中集合的對比研究——java集合深入了解1、ArrayList

java 去除ArrayList中重複的元素

使用ArrayList集合，對其添加10個不同的元素，并使用Iterator周遊該集合

ArrayList數組主要方法純源碼分析-小白成神之路1.add(E e)方法和newCapacity()方法:2.構造方法：3.Get()方法：4.remove()方法：5.set(int index, E element)方法：6.Clear()方法：

一步一步解析集合架構ArrayList源碼（2）