List總結(jié)

2019-11-11 01:35:21

字體：大中小

供稿：網(wǎng)友

前面LZ已經(jīng)充分介紹了有關(guān)于List接口的大部分知識，如ArrayList、LinkedList、Vector、Stack，通過這幾個(gè)知識點(diǎn)可以對List接口有了比較深的了解了。只有通過歸納總結(jié)的知識才是你的知識。所以下面LZ就List接口做一個(gè)總結(jié)。推薦閱讀：

java提高篇（二一）-----ArrayList

java提高篇（二二）-----LinkedList

java提高篇（二九）-----Vector

Java提高篇（三一）-----Stack

一、List接口概述

List接口，成為有序的Collection也就是序列。該接口可以對列表中的每一個(gè)元素的插入位置進(jìn)行精確的控制，同時(shí)用戶可以根據(jù)元素的整數(shù)索引（在列表中的位置）訪問元素，并搜索列表中的元素。下圖是List接口的框架圖：

通過上面的框架圖，可以對List的結(jié)構(gòu)了然于心，其各個(gè)類、接口如下：

Collection：Collection 層次結(jié)構(gòu) 中的根接口。它表示一組對象，這些對象也稱為 collection 的元素。對于Collection而言，它不提供任何直接的實(shí)現(xiàn)，所有的實(shí)現(xiàn)全部由它的子類負(fù)責(zé)。

AbstractCollection：提供 Collection 接口的骨干實(shí)現(xiàn)，以最大限度地減少了實(shí)現(xiàn)此接口所需的工作。對于我們而言要實(shí)現(xiàn)一個(gè)不可修改的 collection，只需擴(kuò)展此類，并提供 iterator 和 size 方法的實(shí)現(xiàn)。但要實(shí)現(xiàn)可修改的 collection，就必須另外重寫此類的 add 方法（否則，會(huì)拋出 UnsupportedOperationException），iterator 方法返回的迭代器還必須另外實(shí)現(xiàn)其 remove 方法。

terator：迭代器。

ListIterator：系列表迭代器，允許程序員按任一方向遍歷列表、迭代期間修改列表，并獲得迭代器在列表中的當(dāng)前位置。

List：繼承于Collection的接口。它代表著有序的隊(duì)列。

AbstractList：List 接口的骨干實(shí)現(xiàn)，以最大限度地減少實(shí)現(xiàn)“隨機(jī)訪問”數(shù)據(jù)存儲(chǔ)（如數(shù)組）支持的該接口所需的工作。

Queue：隊(duì)列。提供隊(duì)列基本的插入、獲取、檢查操作。

Deque：一個(gè)線性 collection，支持在兩端插入和移除元素。大多數(shù) Deque 實(shí)現(xiàn)對于它們能夠包含的元素?cái)?shù)沒有固定限制，但此接口既支持有容量限制的雙端隊(duì)列，也支持沒有固定大小限制的雙端隊(duì)列。

AbstractSequentialList：提供了 List 接口的骨干實(shí)現(xiàn)，從而最大限度地減少了實(shí)現(xiàn)受“連續(xù)訪問”數(shù)據(jù)存儲(chǔ)（如鏈接列表）支持的此接口所需的工作。從某種意義上說，此類與在列表的列表迭代器上實(shí)現(xiàn)“隨機(jī)訪問”方法。

LinkedList：List 接口的鏈接列表實(shí)現(xiàn)。它實(shí)現(xiàn)所有可選的列表操作。

ArrayList：List 接口的大小可變數(shù)組的實(shí)現(xiàn)。它實(shí)現(xiàn)了所有可選列表操作，并允許包括 null 在內(nèi)的所有元素。除了實(shí)現(xiàn) List 接口外，此類還提供一些方法來操作內(nèi)部用來存儲(chǔ)列表的數(shù)組的大小。

Vector：實(shí)現(xiàn)可增長的對象數(shù)組。與數(shù)組一樣，它包含可以使用整數(shù)索引進(jìn)行訪問的組件。

Stack：后進(jìn)先出（LIFO）的對象堆棧。它通過五個(gè)操作對類 Vector 進(jìn)行了擴(kuò)展，允許將向量視為堆棧。

Enumeration：枚舉，實(shí)現(xiàn)了該接口的對象，它生成一系列元素，一次生成一個(gè)。連續(xù)調(diào)用 nextElement 方法將返回一系列的連續(xù)元素。

二、使用場景

學(xué)習(xí)知識的根本目的就是使用它。每個(gè)知識點(diǎn)都有它的使用范圍。集合也是如此，在Java中集合的家族非常龐大，每個(gè)成員都有最適合的使用場景。在剛剛接觸List時(shí)，LZ就說過如果涉及到“棧”、“隊(duì)列”、“鏈表”等操作，請優(yōu)先考慮用List。至于是那個(gè)List則分如下：

1、對于需要快速插入、刪除元素，則需使用LinkedList。

2、對于需要快速訪問元素，則需使用ArrayList。

3、對于“單線程環(huán)境”或者“多線程環(huán)境，但是List僅被一個(gè)線程操作”，需要考慮使用非同步的類，如果是“多線程環(huán)境，切List可能同時(shí)被多個(gè)線程操作”，考慮使用同步的類（如Vector）。

2.1ArrayList、LinkedList性能分析

在List中我們使用最普遍的就是LinkedList和ArrayList，同時(shí)我們也了解了他們兩者之間的使用場景和區(qū)別。

[java] view plain copypublic class ListTest { PRivate static final int COUNT = 100000; private static ArrayList arrayList = new ArrayList<>(); private static LinkedList linkedList = new LinkedList<>(); private static Vector vector = new Vector<>(); public static void insertToList(List list){ long startTime = System.currentTimeMillis(); for(int i = 0 ; i < COUNT ; i++){ list.add(0,i); } long endTime = System.currentTimeMillis(); System.out.println("插入 " + COUNT + "元素" + getName(list) + "花費(fèi) " + (endTime - startTime) + " 毫秒"); } public static void deleteFromList(List list){ long startTime = System.currentTimeMillis(); for(int i = 0 ; i < COUNT ; i++){ list.remove(0); } long endTime = System.currentTimeMillis(); System.out.println("刪除" + COUNT + "元素" + getName(list) + "花費(fèi) " + (endTime - startTime) + " 毫秒"); } public static void readList(List list){ long startTime = System.currentTimeMillis(); for(int i = 0 ; i < COUNT ; i++){ list.get(i); } long endTime = System.currentTimeMillis(); System.out.println("讀取" + COUNT + "元素" + getName(list) + "花費(fèi) " + (endTime - startTime) + " 毫秒"); } private static String getName(List list) { String name = ""; if(list instanceof ArrayList){ name = "ArrayList"; } else if(list instanceof LinkedList){ name = "LinkedList"; } else if(list instanceof Vector){ name = "Vector"; } return name; } public static void main(String[] args) { insertToList(arrayList); insertToList(linkedList); insertToList(vector); System.out.println("--------------------------------------"); readList(arrayList); readList(linkedList); readList(vector); System.out.println("--------------------------------------"); deleteFromList(arrayList); deleteFromList(linkedList); deleteFromList(vector); } }

運(yùn)行結(jié)果:

[java] view plain copy插入 100000元素ArrayList花費(fèi) 3900 毫秒插入 100000元素LinkedList花費(fèi) 15 毫秒插入 100000元素Vector花費(fèi) 3933 毫秒 -------------------------------------- 讀取100000元素ArrayList花費(fèi) 0 毫秒讀取100000元素LinkedList花費(fèi) 8877 毫秒讀取100000元素Vector花費(fèi) 16 毫秒 -------------------------------------- 刪除100000元素ArrayList花費(fèi) 4618 毫秒刪除100000元素LinkedList花費(fèi) 16 毫秒刪除100000元素Vector花費(fèi) 4759 毫秒

從上面的運(yùn)行結(jié)果我們可以清晰的看出ArrayList、LinkedList、Vector增加、刪除、遍歷的效率問題。下面我就插入方法add(int index, E element),delete、get方法各位如有興趣可以研究研究。

首先我們先看三者之間的源碼：

ArrayList

[java] view plain copypublic void add(int index, E element) { rangeCheckForAdd(index); //檢查是否index是否合法 ensureCapacityInternal(size + 1); //擴(kuò)容操作 System.arraycopy(elementData, index, elementData, index + 1, size - index); //數(shù)組拷貝 elementData[index] = element; //插入 size++; }

rangeCheckForAdd、ensureCapacityInternal兩個(gè)方法沒有什么影響，真正產(chǎn)生影響的是System.arraycopy方法，該方法是個(gè)JNI函數(shù)，是在JVM中實(shí)現(xiàn)的。聲明如下：

[java] view plain copypublic static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);

目前LZ無法看到源碼，具體的實(shí)現(xiàn)不是很清楚，不過System.arraycopy源碼分析對其進(jìn)行了比較清晰的分析。但事實(shí)上我們只需要了解該方法會(huì)移動(dòng)index后面的所有元素即可，這就意味著ArrayList的add(int index, E element)方法會(huì)引起index位置之后所有元素的改變，這真是牽一處而動(dòng)全身。

LinkedList

[java] view plain copypublic void add(int index, E element) { checkPositionIndex(index); if (index == size) //插入位置在末尾 linkLast(element); else linkBefore(element, node(index)); }

該方法比較簡單，插入位置在末尾則調(diào)用linkLast方法，否則調(diào)用linkBefore方法，其實(shí)linkLast、linkBefore都是非常簡單的實(shí)現(xiàn)，就是在index位置插入元素，至于index具體為知?jiǎng)t有node方法來解決，同時(shí)node對index位置檢索還有一個(gè)加速作用，如下：

[java] view plain copyNode<E> node(int index) { if (index < (size >> 1)) { //如果index 小于 size/2 則從頭開始查找 Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { //如果index 大于 size/2 則從尾部開始查找 Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }

所以linkedList的插入動(dòng)作比ArrayList動(dòng)作快就在于兩個(gè)方面。1：linkedList不需要執(zhí)行元素拷貝動(dòng)作，沒有牽一發(fā)而動(dòng)全身的大動(dòng)作。2:查找插入位置有加速動(dòng)作即：若index < 雙向鏈表長度的1/2，則從前向后查找; 否則，從后向前查找。

Vector

Vector的實(shí)現(xiàn)機(jī)制和ArrayList一樣，同樣是使用動(dòng)態(tài)數(shù)組來實(shí)現(xiàn)的，所以他們兩者之間的效率差不多，add的源碼也一樣，如下：

[java] view plain copypublic void add(int index, E element) { insertElementAt(element, index); } public synchronized void insertElementAt(E obj, int index) { modCount++; if (index > elementCount) { throw new ArrayIndexOutOfBoundsException(index + " > " + elementCount); } ensureCapacityHelper(elementCount + 1); System.arraycopy(elementData, index, elementData, index + 1, elementCount - index); elementData[index] = obj; elementCount++; }

上面是針對ArrayList、LinkedList、Vector三者之間的add（int index,E element)方法的解釋，解釋了LinkedList的插入動(dòng)作要比ArrayList、Vector的插入動(dòng)作效率為什么要高出這么多！至于delete、get兩個(gè)方法LZ就不多解釋了。

同時(shí)LZ在寫上面那個(gè)例子時(shí)發(fā)現(xiàn)了一個(gè)非常有趣的現(xiàn)象，就是linkedList在某些時(shí)候執(zhí)行add方法時(shí)比ArrayList方法會(huì)更慢！至于在什么情況？為什么會(huì)慢LZ下篇博客解釋，當(dāng)然不知道這個(gè)情況各位是否也遇到過？？