【集合系列】- 深入淺出分析Collection中的List介面

来源:https://www.cnblogs.com/dxflqm/archive/2019/11/16/11867924.html
-Advertisement-
Play Games

在上一章《初探java集合框架圖》中，我相信大部分朋友對java容器整體架構都有了初步的瞭解，那麼本章主要是想詳細的介紹以下 List 介面實現類之間的區別！ ...


一、List簡介

List 的數據結構就是一個序列，存儲內容時直接在記憶體中開闢一塊連續的空間，然後將空間地址與索引對應。

以下是List集合簡易架構圖

由圖中的繼承關係，可以知道，ArrayList、LinkedList、Vector、Stack都是List的四個實現類。

  • AbstractCollection 是一個抽象類，它唯一實現Collection介面的類。AbstractCollection主要實現了toArray()、toArray(T[] a)、remove()等方法。
  • AbstractList 也是一個抽象類，它繼承於AbstractCollection。AbstractList實現List介面中除size()、get(int location)之外的函數，比如特定迭代器ListIterator。
  • AbstractSequentialList 是一個抽象類，它繼承於AbstractList。AbstractSequentialList 實現了“鏈表中，根據index索引值操作鏈表的全部函數”。
  • ArrayList 是一個動態數組，它由數組實現。隨機訪問效率高，隨機插入、隨機刪除效率低。
  • LinkedList 是一個雙向鏈表。它也可以被當作堆棧、隊列或雙端隊列進行操作。LinkedList隨機訪問效率低，但隨機插入、隨機刪除效率高。
  • Vector 也是一個動態數組，和ArrayList一樣，也是由數組實現。但是ArrayList是非線程安全的，而Vector是線程安全的。
  • Stack 是棧，它繼承於Vector。它的特性是：先進後出(FILO, First In Last Out)。

下麵對各個實現類進行方法剖析！

二、ArrayList

ArrayList實現了List介面，也是順序容器，即元素存放的數據與放進去的順序相同，允許放入null元素，底層通過數組實現。
除該類未實現同步外，其餘跟Vector大致相同。

在Java1.5之後，集合還提供了泛型，泛型只是編譯器提供的語法糖，方便編程，對程式不會有實質的影響。因為所有的類都預設繼承至Object，所以這裡的數組是一個Object數組，以便能夠容納任何類型的對象。

常用方法介紹

2.1、get方法

get()方法同樣很簡單，先判斷傳入的下標是否越界，再獲取指定元素。

public E get(int index) {
        rangeCheck(index);
        return elementData(index);
}

/**
 * 檢查傳入的index是否越界
 */
private void rangeCheck(int index) {
        if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

2.2、set方法

set()方法也非常簡單，直接對數組的指定位置賦值即可。

public E set(int index, E element) {
        rangeCheck(index);
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
}

2.3、add方法

ArrayList添加元素有兩個方法，一個是add(E e)，另一個是add(int index, E e)。
這兩個方法都是向容器中添加新元素，可能會出現容量（capacity）不足，因此在添加元素之前，都需要進行剩餘空間檢查，如果需要則自動擴容。擴容操作最終是通過grow()方法完成的。

grow方法實現

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);//原來的1.5倍
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
}

添加元素還有另外一個addAll()方法，addAll()方法能夠一次添加多個元素，根據位置不同也有兩個方法，一個是在末尾添加的addAll(Collection<? extends E> c)方法，一個是從指定位置開始插入的addAll(int index, Collection<? extends E> c)方法。

不同點：addAll()的時間複雜度不僅跟插入元素的多少有關，也跟插入的位置相關，時間複雜度是線性增長！

2.4、remove方法

remove()方法也有兩個版本，一個是remove(int index)刪除指定位置的元素；另一個是remove(Object o)，通過o.equals(elementData[index])來刪除第一個滿足的元素。

需要將刪除點之後的元素向前移動一個位置。需要註意的是為了讓GC起作用，必須顯式的為最後一個位置賦null值。

  • remove(int index)方法
public E remove(int index) {
        rangeCheck(index);
        modCount++;
        E oldValue = elementData(index);
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; //賦null值，方便GC回收
        return oldValue;
}
  • remove(Object o)方法
public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
}

三、LinkedList

在上篇文章中，我們知道LinkedList同時實現了List介面和Deque介面，也就是說它既可以看作一個順序容器，又可以看作一個隊列（Queue），同時又可以看作一個棧（Stack）。

LinkedList底層通過雙向鏈表實現，通過first和last引用分別指向鏈表的第一個和最後一個元素，註意這裡沒有所謂的啞元（某個參數如果在子程式或函數中沒有用到，那就被稱為啞元），當鏈表為空的時候first和last都指向null。

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
     /**容量*/
    transient int size = 0;

    /**鏈表第一個元素*/
    transient Node<E> first;

     /**鏈表最後一個元素*/
    transient Node<E> last;
    
    ......
}
/**
 * 內部類Node
 */
private static class Node<E> {
    E item;//元素
    Node<E> next;//後繼
    Node<E> prev;//前驅
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

常用方法介紹

3.1、get方法

get()方法同樣很簡單，先判斷傳入的下標是否越界，再獲取指定元素。

public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
}

/**
 * 檢查傳入的index是否越界
 */
private void checkElementIndex(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

3.2、set方法

set(int index, E element)方法將指定下標處的元素修改成指定值，也是先通過node(int index)找到對應下表元素的引用，然後修改Node中item的值。

public E set(int index, E element) {
        checkElementIndex(index);
        Node<E> x = node(index);
        E oldVal = x.item;
        x.item = element;
        return oldVal;
}

3.3、add方法

同樣的，add()方法有兩方法，一個是add(E e)，另一個是add(int index, E element)。

  • add(E e)方法

該方法在LinkedList的末尾插入元素，因為有last指向鏈表末尾，在末尾插入元素的花費是常數時間，只需要簡單修改幾個相關引用即可。

public boolean add(E e) {
        linkLast(e);
        return true;
}

/**
 * 添加元素
 */
void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            //原來鏈表為空，這是插入的第一個元素
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
}
  • add(int index, E element)方法

該方法是在指定下表處插入元素，需要先通過線性查找找到具體位置，然後修改相關引用完成插入操作。

具體分成兩步，1.先根據index找到要插入的位置；2.修改引用，完成插入操作。

public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            //調用add方法，直接在末尾添加元素
            linkLast(element);
        else
            //根據index找到要插入的位置
            linkBefore(element, node(index));
}

/**
 * 插入位置
 */
void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
}

同樣的，添加元素還有另外一個addAll()方法，addAll()方法能夠一次添加多個元素，根據位置不同也有兩個方法，一個是在末尾添加的addAll(Collection<? extends E> c)方法，另一個是從指定位置開始插入的addAll(int index, Collection<? extends E> c)方法。

裡面也for迴圈添加元素，addAll()的時間複雜度不僅跟插入元素的多少有關，也跟插入的位置相關，時間複雜度是線性增長！

3.4、remove方法

同樣的，remove()方法也有兩個方法，一個是刪除指定下標處的元素remove(int index)，另一個是刪除跟指定元素相等的第一個元素remove(Object o)。

兩個刪除操作都是，1.先找到要刪除元素的引用；2.修改相關引用，完成刪除操作。

  • remove(int index)方法

通過下表，找到對應的節點，然後將其刪除

public E remove(int index) {
        checkElementIndex(index);
        return unlink(node(index));
}
  • remove(Object o)方法

通過equals判斷找到對應的節點，然後將其刪除

public boolean remove(Object o) {
        if (o == null) {
            for (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)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
}

刪除操作都是通過unlink(Node<E> x)方法完成的。這裡需要考慮刪除元素是第一個或者最後一個時的邊界情況。

/**
 * 刪除一個Node節點方法
 */
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) {
            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;
}

四、Vector

Vector類屬於一個輓救的子類，早在jdk1.0的時候，就已經存在此類，但是到了jdk1.2之後重點強調了集合的概念，所以，先後定義了很多新的介面，比如ArrayList、LinkedList，但考慮到早期大部分已經習慣使用Vector類，所以，為了相容性，java的設計者，就讓Vector多實現了一個List介面，這才將其保留下來。

在使用方面，Vector的get、set、add、remove方法實現，與ArrayList基本相同，不同的是Vector在方法上加了線程同步鎖synchronized，所以，執行效率方面，會比較慢！

4.1、get方法

public synchronized E get(int index) {
        if (index >= elementCount)
            throw new ArrayIndexOutOfBoundsException(index);

        return elementData(index);
}

4.2、set方法

public synchronized E set(int index, E element) {
        if (index >= elementCount)
            throw new ArrayIndexOutOfBoundsException(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
}

4.3、add方法

public synchronized boolean add(E e) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = e;
        return true;
}

4.4、remove方法

public synchronized boolean removeElement(Object obj) {
        modCount++;
        int i = indexOf(obj);
        if (i >= 0) {
            removeElementAt(i);
            return true;
        }
        return false;
}

五、Stack

在 Java 中 Stack 類表示後進先出（LIFO）的對象堆棧。棧是一種非常常見的數據結構，它採用典型的先進後出的操作方式完成的；在現實生活中，手槍彈夾的子彈就是一個典型的後進先出的結構。

在使用方面，主要方法有push、peek、pop。

5.1、push方法

push方法表示，向棧中添加元素

public E push(E item) {
        addElement(item);
        return item;
}

5.2、peek方法

peek方法表示，查看棧頂部的對象，但不從棧中移除它

public synchronized E peek() {
        int     len = size();
        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);
}

5.3、pop方法

pop方法表示，移除元素，並將要移除的元素方法

  public synchronized E pop() {
        E       obj;
        int     len = size();
        obj = peek();
        removeElementAt(len - 1);
        return obj;
}

關於 Java 中 Stack 類，有很多的質疑聲，棧更適合用隊列結構來實現，這使得Stack在設計上不嚴謹，因此，官方推薦使用Deque下的類來是實現棧！

六、總結

  • ArrayList(動態數組結構)，查詢快（隨意訪問或順序訪問），增刪慢，但在末尾插入，速度與LinkedList相差無幾！
  • LinkedList（雙向鏈表結構），查詢慢，增刪快！
  • Vector（動態數組結構），相比ArrayList都慢，被ArrayList替代，基本不在使用。優勢是線程安全（函數都是synchronized），如果需要在多線程下使用，推薦使用併發容器中的工具類來操作，效率高！
  • Stack（棧結構）繼承於Vector，數據是先進後出，基本不在使用，如果要實現棧，推薦使用Deque下的ArrayDeque，效率比Stack高！

七、參考

1、JDK1.7&JDK1.8 源碼
2、CarpenterLee - Java集合分析
3、博客園 - 朽木 - ArrayList、LinkedList、Vector、Stack的比較

作者：炸雞可樂
出處：www.pzblog.cn


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • IDEA中新建SpringBoot項目時提示:Artifact contains illegal characters
    場景 一步一步教你在IEDA中快速搭建SpringBoot項目： https://blog.csdn.net/BADAO_LIUMANG_QIZHI/article/details/87688277 在使用IDEA新建SpringBoot的Web項目時，在輸入Artifact時提示： Artifac ...
  • JVM原理速記複習Java虛擬機總結思維導圖面試必備
    良心製作，JVM原理速記複習Java虛擬機總結思維導圖面試必備。 一、運行時數據區域 線程私有 程式計數器 記錄正在執行的虛擬機位元組碼指令的地址（如果正在執行的是Native方法則為空），是唯一一個沒有規定OOM（OutOfMemoryError）的區域。 Java虛擬機棧 每個Java方法在執... ...
  • Python讀位元組某一位的值，設置某一位的值，二進位位操作
    Python讀位元組某一位的值，設置某一位的值，二進位位操作 在物聯網實際應用項目開發中，為了提升性能，與設備端配合，往往最終使用的是二進位位元組串方式進行的通信協議封裝，更會把0和1、True和False、Yes和No這樣的布爾值每8個只占用一個位元組，用位元組中的位來表示。減少傳輸量，減少對網路穩定性的 ...
  • 二、工廠模式
    工廠模式 前言 工廠模式又稱為創建模式，它是建對象的一種最佳方式。工廠模式的本質就是用工廠方法代替new操作創建一種實例化對象的方式。 在之前，如果我們想實例化一個對象Simple，一般會想到的方法就是通過構造器來創建Simple simple = new Simple(參數)。但是，如果創建sim ...
  • MySQL系列：MySQL的基本使用
    資料庫的基本操作 在MySQL資料庫中，對於一個MySQL示例，是可以包含多個資料庫的。 在連接MySQL後，我們可以通過 show databases; 來進行查看有那麼資料庫。這裡已經存在一些庫了，其中information_schema、auth、mysql、performance_schem ...
  • python基礎(32):進程(二)
    1. multiprocess模塊 仔細說來，multiprocess不是一個模塊而是python中一個操作、管理進程的包。 之所以叫multi是取自multiple的多功能的意思,在這個包中幾乎包含了和進程有關的所有子模塊。由於提供的子模塊非常多，為了方便大家歸類記憶，我將這部分大致分為四個部分： ...
  • 分享學習 PHP 源碼的方法
    ​每天抽一點時間來看看 PHP 源碼方面的書，說實話，無法在調試器下觀察 PHP 運行狀態的上下文實在是一件痛苦的事情。不過還好不是一無所獲，雖然內容比較多，但是掌握方法挨著看下去還是可以看一些代碼的。而且本身 PHP 源碼講解就有書，所以學習起來還是較為方便的。想要調試源碼，我覺得我最好應該找一個 ...
  • git 刪除誤上傳的.idea文件
    1.解決git誤上傳文件(如.idea)的問題 2. 常用的.gitignore文件 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類