List接口的三大实现类比较
生活随笔
收集整理的這篇文章主要介紹了
List接口的三大实现类比较
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
文章目錄
- 前言
- 一、ArrayList介紹：
- ArrayList源碼分析：
- 繼承關系：
- 屬性：
- 構造器：
- 無參構造器
- 帶參構造器
- 帶參構造器二：
- 擴容機制：
- 常用方法：
- boolean add(E e)
- void add(int index, E element)
- E remove(int index)
- boolean remove(Object o)
- E get(int index)
- E set(int index, E element)
- boolean equals(Object o)
- 總結:
- 二、Vector介紹：
- ArrayList源碼分析：
- 屬性
- 構造器：
- 雙參構造器：
- 帶參構造器：
- 無參構造器：
- 擴容機制
- 方法
- 線程安全
- 總結:
- Vector線程安全校驗：
- 多線程使用ArrayList
- 多線程使用Vector
- 三、LinkedList介紹：
- LinkedList源碼解析
- 繼承關系：
- 屬性：
- 構造器：
- 鏈表節點靜態類
- 方法：
- add(E e)：
- add(int index, E element)
- E remove()
- E remove(int index)
- boolean remove(Object o)
- E set(int index, E element)
- E get(int index)
- Node node(int index)
- 總結：
- 三大實現類異同總結：
前言
ArrayList、LinkedList、Vector 都是List接口的實現類但是他們之間的底層實現和優缺點都有不同，我們這篇文章將通過他們三者之間的異同進行研究！
提示：以下是本篇文章正文內容，下面案例可供參考
一、ArrayList介紹：
ArrayList基于數組實現 查改快，增刪慢，線程不安全。
ArrayList源碼分析：
繼承關系：
class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable AbstractList<E>：是List接口第一抽象類 RandomAccess：RandomAccess接口是一個標志接口（Marker）它支持快速隨機訪問 Cloneable：支持克隆 java.io.Serializable：RandomAccess接口也是是一個標志接口（Marker） 它支持序列化和反序列化屬性：
private static final long serialVersionUID = 8683452581122892189L;//序列化編號private static final int DEFAULT_CAPACITY = 10;//使用無參構造器時，第一次擴容的數組默認大小10private static final Object[] EMPTY_ELEMENTDATA = {};.//用于空實例的共享空數組實例。private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};//用于默認大小的空實例的共享空數組實例。//我們將其與EMPTY_ELEMENTDATA區分開來，以了解添加第一個元素時擴容多少。//MARK:無參構造函數 使用該數組初始化 與EMPTY_ELEMENTDATA的區別主要是區分作用，用來減少空數組的存在，優化內存使用 1.8后的優化transient Object[] elementData; //底層的數據結構Object類型的數組private int size;//記錄數組中元素的個數構造器：
無參構造器
構造一個初始容量為10的一個數組
public ArrayList() { //private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 這里其實是賦值了一個共享的空數組，數組在第一次添加元素時會判斷elementData是否等于DEFAULTCAPACITY_EMPTY_ELEMENTDATA，假如等于則會初始化容量為DEFAULT_CAPACITY 也就是10this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}帶參構造器
int initialCapacity為ArrayList底層數組初始的長度 構造一個指定長度的數組
public ArrayList(int initialCapacity) {//參數合法性檢驗if (initialCapacity > 0) {//創建一個長度為initialCapacity 的數this.elementData = new Object[initialCapacity];} else if (initialCapacity == 0) {//將原有的空數組EMPTY_ELEMENTDATA賦給底層數組elementDatathis.elementData = EMPTY_ELEMENTDATA;} else {//參數不合法拋出IllegalArgumentException異常throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);}}帶參構造器二：
Collection<? extends E> c c 為泛型E的子類，構造一個包含指定集合的元素的列表，按照它們由集合的迭代器返回的順序。
public ArrayList(Collection<? extends E> c) {Object[] a = c.toArray(); //將c集合中的數據拷貝到a數組中if ((size = a.length) != 0) { //判空并給size賦值if (c.getClass() == ArrayList.class) {//如果c是ArrayList類的對象之間將a數組地址賦值給elementData數組elementData = a; } else {//進行拷貝elementData = Arrays.copyOf(a, size, Object[].class);}} else {// 如果為c集合為空，則將原有的空數組EMPTY_ELEMENTDATA賦給底層數組elementDataelementData = EMPTY_ELEMENTDATA;}}擴容機制：
private Object[] grow() { //數組容量不足時直接調用的擴容方法 返回一個Object數組return grow(size + 1); }private Object[] grow(int minCapacity) { //數組拷貝的實現 newCapacity(minCapacity) 為實際的擴容大小return elementData = Arrays.copyOf(elementData,newCapacity(minCapacity));} private int newCapacity(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;//原來數組的長度int newCapacity = oldCapacity + (oldCapacity >> 1); //新數組的長度，在原來數組的長度上加原來數組的二分之一if (newCapacity - minCapacity <= 0) { //如果新數組的長度小于等于size+1 比如原來數組長度為0或者1,那么新數組長度也為0或者1無法體現擴容，則需要重新處理：處理如下if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)//判斷現在的數組是否為無參構造器創建的數組，如果是就返回DEFAULT_CAPACITY，即無參構造器第一次擴容為10return Math.max(DEFAULT_CAPACITY, minCapacity);if (minCapacity < 0) // 參數無效拋出異常throw new OutOfMemoryError();return minCapacity; //擴容+1;}//MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8return (newCapacity - MAX_ARRAY_SIZE <= 0)//如果新數組長度大于最大擴容邊界需要做特殊處理? newCapacity: hugeCapacity(minCapacity);//特殊處理}private static int hugeCapacity(int minCapacity) {//參數合法性檢驗if (minCapacity < 0) // overflowthrow new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) //如果size+1大于大于最大擴容邊界 則擴容到 Integer.MAX_VALUE(2 的 31 次方 - 1 ) 否則擴容到最大擴容邊界? Integer.MAX_VALUE: MAX_ARRAY_SIZE;}常用方法：
boolean add(E e)
往數組最后一位插入指定數據
public boolean add(E e) {modCount++;//集合的修改次數 保證迭代器的安全add(e, elementData, size); //具體實現方法如下 size既是記錄數組的多少，也是記錄最后一位插入的位置return true;//添加成功返回true} //ArrayList私有方法 add的具體實現方法： private void add(E e, Object[] elementData, int s) { .// e插入的數據 elementData插入到的指定數組 s 插入到數組的指定位置if (s == elementData.length) //數組容量已經滿需要進行擴容elementData = grow(); //擴容方法elementData[s] = e; //數據插入size = s + 1; //更新size}void add(int index, E element)
public void add(int index, E element) {rangeCheckForAdd(index);modCount++;final int s;Object[] elementData;if ((s = size) == (elementData = this.elementData).length)elementData = grow();System.arraycopy(elementData, index,elementData, index + 1,s - index);elementData[index] = element;size = s + 1;}E remove(int index)
刪除指定位置數據 返回一個泛型
public E remove(int index) {Objects.checkIndex(index, size); //參數合法性檢驗final Object[] es = elementData; //賦值地址 修改es實際就是修改 elementData//@SuppressWarnings(“unchecked”) 告訴編譯器忽略 unchecked 警告信息@SuppressWarnings("unchecked") E oldValue = (E) es[index]; //取出指定位置的數據fastRemove(es, index);return oldValue;}private void fastRemove(Object[] es, int i) {modCount++;//保證迭代器安全final int newSize; if ((newSize = size - 1) > i)//新數組長度賦值并檢查刪除數據的合法位置System.arraycopy(es, i + 1, es, i, newSize - i);//刪除最后指定位置的數然后數據前移es[size = newSize] = null; //更新size 并將數組末尾置為nuill}boolean remove(Object o)
刪除指定元素 如果此元素存在返回true并刪除 如果不存在 返回false
public boolean remove(Object o) {final Object[] es = elementData;//同上final int size = this.size; //int i = 0;found: { //遍歷數組查找O所在位置if (o == null) {for (; i < size; i++)if (es[i] == null)break found;} else {for (; i < size; i++)if (o.equals(es[i]))break found;}return false;//查找不到返回false}fastRemove(es, i); //刪除指定位置數據return true;}E get(int index)
查找指定位置的數據 返回該數據值
public E get(int index) {Objects.checkIndex(index, size);//參數合法性檢驗return elementData(index);//返回該位置的數據}E set(int index, E element)
將指定位置修改為指定值 返回該位置的原有值
public E set(int index, E element) {Objects.checkIndex(index, size);//參數合法性檢驗E oldValue = elementData(index); //獲取指定位置的數據elementData[index] = element;//將指定位置的數據修改為elementreturn oldValue;//返回該位置原有的數據}boolean equals(Object o)
數組內容比較如果相同返回true 不同返回false
public boolean equals(Object o) {if (o == this) { //判斷是否是本數組return true;}if (!(o instanceof List)) { //判斷是否是List子類return false;}final int expectedModCount = modCount; //modCount賦值// ArrayList can be subclassed and given arbitrary behavior, but we can// still deal with the common case where o is ArrayList preciselyboolean equal = (o.getClass() == ArrayList.class)//不同類型的數據使用不同方法進行比較? equalsArrayList((ArrayList<?>) o): equalsRange((List<?>) o, 0, size);checkForComodification(expectedModCount);//保證迭代器安全return equal;} boolean equalsRange(List<?> other, int from, int to) { //非ArrayList檢驗方法 other 需要比較的集合 from 起始位置 to 比較的長度final Object[] es = elementData; //數組底層位置賦值if (to > es.length) { //長度比較throw new ConcurrentModificationException();}var oit = other.iterator(); //調用迭代器for (; from < to; from++) {if (!oit.hasNext() || !Objects.equals(es[from], oit.next())) { //如果有數據不匹配直接返回falsereturn false;}}return !oit.hasNext();//判斷傳入的數據比較玩以后原集合是否還有數據如果有就返回false 沒有返回true}private boolean equalsArrayList(ArrayList<?> other) {//ArrayList檢驗方法 other需要比較的集合final int otherModCount = other.modCount;final int s = size;boolean equal;if (equal = (s == other.size)) { //判斷兩個數組長度是否相等final Object[] otherEs = other.elementData;//傳入的集合底層數組final Object[] es = elementData;//本身的底層數組if (s > es.length || s > otherEs.length) { //數據拷貝出現錯誤throw new ConcurrentModificationException();}for (int i = 0; i < s; i++) { //逐一比較如果不他給equal賦值為falseif (!Objects.equals(es[i], otherEs[i])) {equal = false;break;}}}other.checkForComodification(otherModCount);//數據安全檢驗。return equal;//返回判斷結果}總結:
ArrayList是我們常用的一種集合，我們在需要做一次性插入和多次查詢業務時可以使用此集合但是，ArrayList不保證線程安全，只能在單線程時候做使用。
二、Vector介紹：
Vector基于數組實現 查改快，增刪慢，線程安全。
ArrayList源碼分析：
雖然Vector和ArrayList有很多相似的地方，但是兩者之間也有比較明顯的差異第一個差異就是Vector是線程安全而ArrayList不是。第二個就是Vector能夠自定義數組增量。下面挑出部分和ArrayList不相同的源碼分析。
屬性
protected int elementCount; //和ArrayList的size相同記錄數據多少protected int capacityIncrement; //決定elementData數組擴增容量。構造器：
雙參構造器：
int initialCapacity, int capacityIncrement
初始化一個長度為initialCapacity的object數組和capacityIncrement。其中capacityIncrement是一個很重要的變量它后期決定了elementData數組擴增容量。
帶參構造器：
public Vector(int initialCapacity) {this(initialCapacity, 0);//調用了上面的雙參構造器 初始化一個長度為initialCapacity的object數組}無參構造器：
public Vector() {this(10);//調用了上面的帶參構造器 初始化一個長度為10的object數組}擴容機制
vector 和ArrList比較明顯不同就是grow方法數組容量的擴增算法
下面是具體有區別的方法 newCapacity中如下部分：
此代碼表示如果我們在選擇構造器時選擇無參構造器和一個參數構造器時，，此時capacityIncrement變量的值就會默認為0，那每次容量就只是擴增一倍（100%）而ArrList是增加50%
如果是通過Vector(int initialCapacity, int capacityIncrement)實例化Vector，只要你傳入的capacityIncrement不小于0，那么數組的容量就能按照你設置的值來擴增。其它代碼部分與ArrayList差不多。
方法
線程安全
如下Vector的add和remove方法前面都同過synchronized進行加鎖保證線程安全
synchronized boolean add(E e) synchronized E remove(int index)總結:
Vector相比較ArrayList而言保證了線程安全，也可以自定義擴容機制，一般我們需要進行多線程操作時候使用Vector
Vector線程安全校驗：
多線程使用ArrayList
CountDownLatch latch = new CountDownLatch(2);ArrayList<Integer> list = new ArrayList<>();new Thread(new Runnable() {@Overridepublic void run() {for (int i=0 ; i<100000;i++){list.add(i);}latch.countDown();}}).start();new Thread(new Runnable() {@Overridepublic void run() {for (int i=0 ; i<10000;i++){list.remove(0);System.out.println("刪除成功第：" + i + "次");}latch.countDown();}}).start();try {latch.await();} catch (InterruptedException e) {e.printStackTrace();}for (int i :list){System.out.println(i);}System.out.println("總數："+list.size());
拋出了空指針異常
多線程使用Vector
CountDownLatch latch = new CountDownLatch(2);Vector<Integer> vector = new Vector<>();new Thread(new Runnable() {@Overridepublic void run() {for (int i=0 ; i<100000;i++){vector.add(i);}latch.countDown();}}).start();new Thread(new Runnable() {@Overridepublic void run() {for (int i=0 ; i<10000;i++){vector.remove(0);System.out.println("刪除成功第：" + i + "次");}latch.countDown();}}).start();try {latch.await();} catch (InterruptedException e) {e.printStackTrace();}for (int i :vector){System.out.println(i);}System.out.println("總數："+vector.size());
成功刪除了前9999個數據
三、LinkedList介紹：
LinkedList 底層通過雙向鏈表的形式實現 增刪快 遍歷和查詢慢 線程不安全。
LinkedList源碼解析
繼承關系：
public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable與ArrayList不同的是LinkedList繼承的是AbstractSequentialList 但AbstractSequentialList也是繼承自AbstractList ，其他和ArrayList相同
屬性：
transient int size = 0; //記錄數據多少transient Node<E> first;//雙向鏈表的頭結點 transient Node<E> last;// 雙向鏈表的尾結點構造器：
public LinkedList() {} //LinkedList的構造方法是一個空方法，此時指針變量first和last的初始值都為null。public LinkedList(Collection<? extends E> c) {//拷貝的構造器this();addAll(c);//將所有c中的數據拷貝過來}鏈表節點靜態類
儲存的數據的實體Node
private static class Node<E> {E item; //需要儲存的數據Node<E> next;//后繼 連接下一個數據 如果她是最后一個則為nullNode<E> prev;//前驅 連接上一個數據 如果她是第一個則為nullNode(Node<E> prev, E element, Node<E> next) { //Node的構造器this.item = element;this.next = next;this.prev = prev;}//明顯看出這是一個雙向鏈表節點，item是用來存放節點值，next是尾指針指向下一個節點，prev是頭指針指向前一個節點。}方法：
add(E e)：
在鏈表末尾插入指定數據：
public boolean add(E e) {linkLast(e); //調用具體實現方法linkLast()如下return true;}void linkLast(E e) {final Node<E> l = last;//尾結點賦值給lfinal Node<E> newNode = new Node<>(l, e, null); //new 一個前綴為原鏈表尾部的 實體為e 后錐為null的實體newNodelast = newNode;//將newNode標記為尾結點if (l == null) //如果原來的尾結點為null說明是第一次插入數據first = newNode;//同時將newNode標記為頭結點elsel.next = newNode;//否則將原尾結點的后繼標記為newNodesize++; //鏈表長度+1modCount++;//鏈表修改次數+1}add(int index, E element)
在指定位置插入指定數據
public void add(int index, E element) {checkPositionIndex(index);//參數合法檢驗if (index == size)linkLast(element);//如果需要插入的數據正好是末尾同上面方法elselinkBefore(element, node(index));//否則調用linkBefore()如下：//node(index)為查詢指定位置的數據}void linkBefore(E e, Node<E> succ) {//e新數據 succ原數據// assert succ != null;final Node<E> pred = succ.prev;//標記原數據的前驅final Node<E> newNode = new Node<>(pred, e, succ);//創建一個前驅為原數據前驅 實體為 e 后繼為原數據新結點succ.prev = newNode;//將原數據的前驅設置為newNodeif (pred == null) //pred 為null說明源數據標記為頭結點first = newNode;//更新頭結點elsepred.next = newNode; //否則將原數據的前驅的后繼設置為newNodesize++;//鏈表長度+1modCount++;//鏈表修改次數+1；}E remove()
刪除第一個數據并返回這個數據
public E remove() {return removeFirst(); }public E removeFirst() {//刪除頭結點的數據final Node<E> f = first;//標記頭結點if (f == null) //頭結點為null 說明沒有數據 拋出異常throw new NoSuchElementException();return unlinkFirst(f);}private E unlinkFirst(Node<E> f) { //刪除頭結點所在位置的數據并返回該數據// assert f == first && f != null;final E element = f.item; //取出該頭結點所在數據實體 即為需要返回數據final Node<E> next = f.next;//標記原鏈表中第二個結點f.item = null; //頭結點實體設置為null方便垃圾回收f.next = null; // help GCfirst = next;//將原鏈表中第二個結點設置為頭結點if (next == null) //原來第二個數據不存在last = null;//頭結點設置為nullelsenext.prev = null; //否則將原鏈表中第二個結點的前驅設置為nullsize--; //鏈表總數-1modCount++; //鏈表操作次數+1return element;//返回原頭結點數據}E remove(int index)
刪除指定位置的數據 并返回該數據
public E remove(int index) {checkElementIndex(index);//參數合法性檢驗return unlink(node(index));//調用unlink()方法如下：}E unlink(Node<E> x) {// assert x != null;final E element = x.item;//標記原結點的實體 此為需要返回的數據final Node<E> next = x.next;final Node<E> prev = x.prev;if (prev == null) {//原數據前驅為null說明此數據為第一個數據first = next;//將原數據的后繼標記為頭結點} else {prev.next = next;//將原數據的后繼賦值為原數據前驅的后繼x.prev = null; //方便垃圾回收}if (next == null) {//原數據為尾部數據last = prev;//將原數據的前驅設置為尾結點} else {next.prev = prev;//否則將原數據的前驅賦值給原數據后繼的前驅x.next = null;//方便垃圾回收}x.item = null;//方便垃圾回收size--;modCount++;return element;}boolean remove(Object o)
刪除指定數據成功返回true 失敗返回false
public boolean remove(Object o) {if (o == null) { //需要操作的數據為nullfor (Node<E> x = first; x != null; x = x.next) { //遍歷查找 需要操作的數據if (x.item == null) { //找到了該數據然后進行刪除unlink(x);//上面已經講過return true;}}} else {for (Node<E> x = first; x != null; x = x.next) {if (o.equals(x.item)) {//非null形式同上只是通過equals方法來判斷需要操作的數據unlink(x);return true;}}}return false;}E set(int index, E element)
將指定位置的數據修改為指定數據
public E set(int index, E element) {checkElementIndex(index);//參數合法性檢驗Node<E> x = node(index); //找到此位置的原數據所在結點E oldVal = x.item;//需要返回的原數據x.item = element; //更新原數據為新數據return oldVal;//返回原數據}E get(int index)
返回指定位置的數據
public E get(int index) {checkElementIndex(index);//參數合法性檢驗return node(index).item;//返回指定位置結點的數據}Node node(int index)
查找指定位置的結點 此方法在進行指定位置的增刪改查都有用到
Node<E> node(int index) {// assert isElementIndex(index);//如下方法的優點是先判斷需要查詢的數組在鏈表的左端還是右端在進行后續操作使原來時間復雜度為n的操作變為n/2 膜拜！！！if (index < (size >> 1)) { //判斷index所在鏈表的左端從前向后遍歷查詢Node<E> x = first;for (int i = 0; i < index; i++)x = x.next;return x;} else {//如果在右邊 從鏈表的后面從后往前遍歷查詢Node<E> x = last;for (int i = size - 1; i > index; i--)x = x.prev;return x;}}總結：
LinkedList底層使用雙向鏈表的形式存儲數據 不用想ArrayList哪些存在地址浪費 并且在增刪時效率高 ，我們可以在需要經常增刪時使用此集合來提高我們的效率。
三大實現類異同總結：
1.從使用方法的角度分析。ArrayList屬于非線程安全，而Vector則屬于線程安全。如果是開發中沒有線程同步的需求，推薦優先使用ArrayList。因此其內部沒有synchronized，執行效率會比Vector快很多。
2.從數據結構的角度分析。ArrayList是一個數組結構（Vector同理），數組在內存中是一片連續存在的片段，在查找元素的時候數組能夠很方便的通過內存計算直接找到對應的元素內存。但是它也有很大的缺點。我們假設需要往數組插入或刪除數據的位置為i，數組元素長度為n，則需要搬運數據n-i次才能完成插入、刪除操作，導致其效率不如LinkedList。
3.LinkedList的底層是一個雙向鏈表結構，在進行查找操作的時候需要花費非常非常多的時間來遍歷整個鏈表（哪怕只遍歷一半），這就是LinkedList在查找效率不如ArrayList快的原因。但是由于其鏈表結構的特殊性，在插入、刪除數據的時候，只需要修改鏈表節點的前后指針就可以完成操作，其的效率遠遠高于ArrayList。
總結
以上是生活随笔為你收集整理的List接口的三大实现类比较的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： List接口介绍
- 下一篇： HashMap和Hashtable的区别