詳解Java集合類之List篇

2022-07-22 18:00:12

1.集合框架體系

集合框架被設計成要滿足以下幾個目標。

該框架必須是高效能的。基本集合（動態陣列，連結串列，樹，雜湊表）的實現也必須是高效的。
該框架允許不同型別的集合，以類似的方式工作，具有高度的互操作性。
對一個集合的擴充套件和適應必須是簡單的。

為此，整個集合框架就圍繞一組標準介面而設計。你可以直接使用這些介面的標準實現，諸如： LinkedList, HashSet, 和 TreeSet 等,除此之外你也可以通過這些介面實現自己的集合。

Collection介面的實現子類

Map介面的實現子類

體系圖

從上面的集合框架圖可以看到，Java 集合框架主要包括兩種型別的容器，一種是集合（Collection），儲存一個元素集合，另一種是圖（Map），儲存鍵/值對對映。Collection 介面又有 3 種子型別，List、Set 和 Queue，再下面是一些抽象類，最後是具體實現類，常用的有 ArrayList、LinkedList、HashSet、LinkedHashSet、HashMap、LinkedHashMap 等等。

2.Collection介面

該介面定義：

public interface Collection<E> extends Iterable<E>

Collection 是最基本的集合介面，一個 Collection 代表一組 Object，即 Collection 的元素, Java不提供直接繼承自Collection的類，只提供繼承於的子介面(如List和set)。

Collection 介面儲存一組不唯一，無序的物件。

Collection介面的常用方法：

import java.util.ArrayList;
import java.util.List;

/**
 * Collection介面的實現類
 * Java不提供直接繼承自Collection的類，只提供繼承於的子介面
 * 所以我們以ArrayList為例子演示Collection介面的抽象方法
 */
public class CollectionTest {
    @SuppressWarnings({"all"})
    public static void main(String[] args) {
        List list = new ArrayList();
        // 新增
        list.add("dahe");
        list.add(521);
        list.add(true);
        System.out.println(list);
        // 刪除
        // 刪除第一個元素
        list.remove(0);
        // 刪除指定的元素
        list.remove(true);
        System.out.println(list);
        // 查詢
        System.out.println(list.contains(521));
        // 元素個數
        System.out.println(list.size());
        // 判空
        System.out.println(list.isEmpty());
        // 清空
        list.clear();
        // 新增多個元素（可以新增另一個實現了Collection介面的物件）
        ArrayList arrayList = new ArrayList();
        arrayList.add("tiktok直播");
        arrayList.add("tiktok廣告投放");
        list.addAll(arrayList);
        System.out.println(list);
        // 查詢多個元素是否都存在
        System.out.println(list.containsAll(arrayList));
        // 刪除多個元素
        list.removeAll(arrayList);
        System.out.println(list);
    }
}

輸出：

[dahe, 521, true]
[521]
true
1
false
[tiktok直播, tiktok廣告投放]
true
[]

3.迭代器

Java Iterator（迭代器）不是一個集合，它是一種用於存取集合的方法，可用於迭代 ArrayList 和 HashSet 等集合。

Iterator 是 Java 迭代器最簡單的實現，ListIterator 是 Collection API 中的介面，它擴充套件了 Iterator 介面。

迭代器 it 的兩個基本操作是 next 、hasNext 和 remove。

呼叫 it.next() 會返回迭代器的下一個元素，並且更新迭代器的狀態。
呼叫 it.hasNext() 用於檢測集合中是否還有元素。
呼叫 it.remove() 將迭代器返回的元素刪除。

程式碼DEMO範例：

import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
/**
 * 迭代器
 */
public class IteratorTest {
    @SuppressWarnings({"all"})
    public static void main(String[] args) {
        Collection col = new ArrayList();
        col.add(new Book("三國演義","羅貫中",52.7));
        col.add(new Book("小李飛刀","古龍",10.2));
        col.add(new Book("紅樓夢","曹雪芹",34.6));
        System.out.println(col);
        // 使用迭代器
        Iterator iterator = col.iterator();
        while (iterator.hasNext()) {
            // 返回下一個元素，型別是Object
            Object obj = iterator.next();
            System.out.println(obj);
        }
    }
}

class Book {
    private String name;
    private String author;
    private Double price;

    public Book(String name, String author, Double price) {
        this.name = name;
        this.author = author;
        this.price = price;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public String getAuthor() {
        return author;
    }

    public void setAuthor(String author) {
        this.author = author;
    }

    public Double getPrice() {
        return price;
    }

    public void setPrice(Double price) {
        this.price = price;
    }

    @Override
    public String toString() {
        return "Book{" +
                "name='" + name + ''' +
                ", author='" + author + ''' +
                ", price=" + price +
                '}';
    }
}

輸出：

[Book{name='三國演義', author='羅貫中', price=52.7}, Book{name='小李飛刀', author='古龍', price=10.2}, Book{name='紅樓夢', author='曹雪芹', price=34.6}]
Book{name='三國演義', author='羅貫中', price=52.7}
Book{name='小李飛刀', author='古龍', price=10.2}
Book{name='紅樓夢', author='曹雪芹', price=34.6}

我們還可以使用增強型for迴圈來遍歷集合：（底層依然是迭代器，可以理解為簡化版的迭代器遍歷）

for (Object o : col) {
    System.out.println(o);
}

4.List介面

List介面是Collection介面的子介面

List集合中元素有序（新增順序和取出順序一致），元素可以重複

List中的每個元素都有其順序的索引

常用方法程式碼範例：

/**
 * List介面，Collection介面的子介面
 */

import java.util.ArrayList;
import java.util.List;


public class ListTest {
    @SuppressWarnings({"all"})
    public static void main(String[] args) {
        List list = new ArrayList();
        List list1 = new ArrayList();
        list1.add("ceshi");
        list1.add("tangseng");
        // 新增元素
        list.add("dahe");
        list.add("tom");
        list.add("dahe"); // 可以重複
        // 指定位置插入元素
        list.add(1,"qian");
        // 加入多個元素，傳入一個Collection物件
        list.addAll(1,list1);
        System.out.println(list);
        // 取出指定索引的元素
        System.out.println(list.get(0));
        // 查詢元素第一次出現的位置
        System.out.println(list.indexOf("dahe"));
        // 查詢元素最後一次出現的位置
        System.out.println(list.lastIndexOf("dahe"));
        // 刪除元素
        list.remove(1);
        System.out.println(list);
        // 元素替換
        list.set(1,"marry");
        System.out.println(list);
        // 返回子集合，0到1的元素集合
        List returnList = list.subList(0,2);
        System.out.println(returnList);
    }
}

輸出：

[dahe, ceshi, tangseng, qian, tom, dahe]
dahe
0
5
[dahe, tangseng, qian, tom, dahe]
[dahe, marry, qian, tom, dahe]
[dahe, marry]

5.ArrayList

ArrayList是由陣列來進行資料儲存的，為執行緒不安全，效率較高多執行緒場景建議使用vector

例如ArrayList add方法的原始碼：（並沒有synchronized進行修飾）

public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}

ArrayList擴容機制

使用無參構造器

當我們使用ArrayList的無參構造器的時候，進入原始碼分析：

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

這裡的elementData是ArrayList存放資料的陣列，可以看出當我們呼叫無參構造的時候，陣列初始化為DEFAULTCAPACITY_EMPTY_ELEMENTDATA，那這一長串代表什麼呢？

繼續步入

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
1
該值為空，那麼我們可以得出結論，當呼叫ArrayList的無參構造時，儲存陣列的預設空間大小為0，也就是空

同時，我們追入elementData陣列，可以發現他是Object陣列，這也就解釋了為什麼ArrayList可以加入任意型別的元素，因為Object是萬物之父！

transient Object[] elementData; // non-private to simplify nested class access

新增資料之前的準備

接下來，當我們使用add方法，比如操作下面這行程式碼：

arrayList.add(521);

首先，ArrayList會對521進行裝箱操作：

@IntrinsicCandidate
 public static Integer valueOf(int i) {
     if (i >= IntegerCache.low && i <= IntegerCache.high)
         return IntegerCache.cache[i + (-IntegerCache.low)];
     return new Integer(i);
 }

繼續步入，進入如下程式碼：

public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}

我們來仔細看一下這段程式碼，首先：

modCount++;

在所有的集合實現類中（Collection與Map中），都會有一個 modCount 的變數出現，它的作用就是記錄當前集合被修改的次數。此處將修改次數 + 1，防止多執行緒操作異常

隨後，進入真正新增資料的add過載方法：

add(e, elementData, size);

開始新增資料

在真正新增資料的部分，程式碼如下：

可以看到，首先需要判斷elementData陣列的容量是否充足，如果容量已經滿了的話，就執行grow方法進行擴容，否則就加入資料，size + 1

private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}

那他是怎麼進行擴容的呢？

我們進入grow方法看一下：

private Object[] grow() {
    return grow(size + 1);
}

繼續步入到grow的過載方法：

private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        int newCapacity = ArraysSupport.newLength(oldCapacity,
                minCapacity - oldCapacity, /* minimum growth */
                oldCapacity >> 1           /* preferred growth */);
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}

獲取老的容量

如果一次也沒有擴容過，則擴容大小為DEFAULT_CAPACITY和minCapacity較大的一個，DEFAULT_CAPACITY被定義為10，而我們此時的minCapacity為1，所以第一次擴容的大小為10

如果老的容量大於0或者elementData陣列不是初始化狀態的陣列（也就是已經第一次擴容過）

那麼通過位運算進行擴容到原容量的1.5倍

注意：IDEA在debug預設情況下顯示的資料是簡化的，如果需要看完整的資料，需要進行設定

使用指定大小的構造器

原理操作和上面類似，只不過它初始的容量為指定的容量，需要擴容時擴容為原容量的1.5倍

ArrayList使用範例

ArrayList arrayList = new ArrayList();
arrayList.add(521);
arrayList.add(null);
arrayList.add("武松");
arrayList.add(null);
System.out.println(arrayList);

輸出：

[521, null, 武松, null]

6.Vector

vector底層同樣是一個物件陣列

protected Object[] elementData;

和ArrayList不同的是，它是執行緒同步的，也就是執行緒安全的

Vector和ArrayList的區別：

7.LinkedList

連結串列（Linked list）是一種常見的基礎資料結構，是一種線性表，但是並不會按線性的順序儲存資料，而是在每一個節點裡存到下一個節點的地址。

連結串列可分為單向連結串列和雙向連結串列。

一個單向連結串列包含兩個值: 當前節點的值和一個指向下一個節點的連結。

一個雙向連結串列有三個整數值: 數值、向後的節點連結、向前的節點連結。

Java LinkedList（連結串列）類似於 ArrayList，是一種常用的資料容器。

與 ArrayList 相比，LinkedList 的增加和刪除的操作效率更高，而查詢和修改的操作效率較低。

LinkedList的底層是一個雙向連結串列

增加元素原始碼分析

在LinkedList連結串列中，存在幾個必知的概念 --> First：連結串列頭節點；Last：連結串列尾節點；next：該節點下一個節點地址；prev：該節點前一個節點地址

LinkedList linkedList = new LinkedList();
// 增
linkedList.add(521);
linkedList.add(1314);
System.out.println(linkedList);

首先：呼叫LinkedList的無參構造，這裡什麼也沒有捏

public LinkedList() {
}

隨後，和ArrayList和Vector一樣，進行裝箱操作

開始新增操作：

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

為了方便理解，我們需要知道一下Node的構造器內容：

Node(Node<E> prev, E element, Node<E> next) {
    this.item = element;
    this.next = next;
    this.prev = prev;
}

繼續步入：

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++;
}

這裡是關鍵，接下來我們來分析一下上面的這段程式碼：

首先，將last的值賦給l，新建一個Node節點，將last指向新建的Node節點，隨後進行分支判斷，將first也指向新建的Node節點

最後，連結串列大小 + 1 ，修改次數 + 1

經過了上面的修改，現在的first和last都指向新建的節點，該節點的next和prev都為null

以上是連結串列中只有一個元素的情況，那麼再次向連結串列新增元素呢？我們再來淺淺看一下

第二次新增節點，l被置為上一個節點的地址，隨後會被新增到新節點的prev屬性中：

還需要更新一下last的值為新新增進來的節點的地址：

隨後，將上一個節點的next值置為當前新加的節點地址：

最後，更新size和modCount即可！

刪除元素原始碼分析

// 刪除最後一個節點
linkedList.remove();

進行原始碼分析，步入：

public E remove() {
    return removeFirst();
}

繼續步入：

public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

Java的設計者在這裡獲取了連結串列頭節點的地址，以備後續進行刪除，隨後檢查了一個頭節點為空的異常，在unlinkFirst方法，將會真正執行刪除的操作！

繼續步入：

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;
    f.next = null; // help GC
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

開頭，獲取頭節點的值，以備在後續返回：

final E element = f.item;

先獲取一下頭節點後面的節點的地址，儲存下來，然後將頭節點的資料和next置空，請求GC進行回收：

final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC

頭節點更新為原頭節點的下一個節點，並作節點個數判斷：

first = next;
if (next == null)
    last = null;
else
    next.prev = null;

最後，更新size和modCount，返回element

LinkedList使用Demo

import java.util.LinkedList;

/**
 * LinkedList
 */
public class LinkedListTest {
    @SuppressWarnings({"all"})
    public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();
        // 增
        linkedList.add(521);
        linkedList.add(1314);
        System.out.println(linkedList);
        // 刪除頭節點
        linkedList.remove();
        System.out.println(linkedList);
        // 修改
        linkedList.set(0,999);
        System.out.println(linkedList);
        // 查詢
        System.out.println(linkedList.get(0));
    }
}

輸出：