詳解Java集合類之List篇

更新時間：2022年07月22日 15:03:54 作者：世界盡頭與你

這篇文章主要為大家詳細(xì)介紹一下Java集合類中List的用法，文中的示例代碼講解詳細(xì)，對我們學(xué)習(xí)Java有一定幫助，感興趣的可以了解一下

1.集合框架體系

集合框架被設(shè)計成要滿足以下幾個目標(biāo)。

該框架必須是高性能的?；炯希▌討B(tài)數(shù)組，鏈表，樹，哈希表）的實現(xiàn)也必須是高效的。
該框架允許不同類型的集合，以類似的方式工作，具有高度的互操作性。
對一個集合的擴展和適應(yīng)必須是簡單的。

為此，整個集合框架就圍繞一組標(biāo)準(zhǔn)接口而設(shè)計。你可以直接使用這些接口的標(biāo)準(zhǔn)實現(xiàn)，諸如： LinkedList, HashSet, 和 TreeSet 等,除此之外你也可以通過這些接口實現(xiàn)自己的集合。

Collection接口的實現(xiàn)子類

Map接口的實現(xiàn)子類

體系圖

從上面的集合框架圖可以看到，Java 集合框架主要包括兩種類型的容器，一種是集合（Collection），存儲一個元素集合，另一種是圖（Map），存儲鍵/值對映射。Collection 接口又有 3 種子類型，List、Set 和 Queue，再下面是一些抽象類，最后是具體實現(xiàn)類，常用的有 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接口的實現(xiàn)類
 * 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));
        // 元素個數(shù)
        System.out.println(list.size());
        // 判空
        System.out.println(list.isEmpty());
        // 清空
        list.clear();
        // 添加多個元素（可以添加另一個實現(xiàn)了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 迭代器最簡單的實現(xiàn)，ListIterator 是 Collection API 中的接口，它擴展了 Iterator 接口。

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

調(diào)用 it.next() 會返回迭代器的下一個元素，并且更新迭代器的狀態(tài)。
調(diào)用 it.hasNext() 用于檢測集合中是否還有元素。
調(diào)用 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循環(huán)來遍歷集合：（底層依然是迭代器，可以理解為簡化版的迭代器遍歷）

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

4.List接口

List接口是Collection接口的子接口

List集合中元素有序（添加順序和取出順序一致），元素可以重復(fù)

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"); // 可以重復(fù)
        // 指定位置插入元素
        list.add(1,"qian");
        // 加入多個元素，傳入一個Collection對象
        list.addAll(1,list1);
        System.out.println(list);
        // 取出指定索引的元素
        System.out.println(list.get(0));
        // 查找元素第一次出現(xiàn)的位置
        System.out.println(list.indexOf("dahe"));
        // 查找元素最后一次出現(xiàn)的位置
        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是由數(shù)組來進(jìn)行數(shù)據(jù)存儲的，為線程不安全，效率較高多線程場景建議使用vector

例如ArrayList add方法的源碼：（并沒有synchronized進(jìn)行修飾）

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

ArrayList擴容機制

使用無參構(gòu)造器

當(dāng)我們使用ArrayList的無參構(gòu)造器的時候，進(jìn)入源碼分析：

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

這里的elementData是ArrayList存放數(shù)據(jù)的數(shù)組，可以看出當(dāng)我們調(diào)用無參構(gòu)造的時候，數(shù)組初始化為DEFAULTCAPACITY_EMPTY_ELEMENTDATA，那這一長串代表什么呢？

繼續(xù)步入

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
1
該值為空，那么我們可以得出結(jié)論，當(dāng)調(diào)用ArrayList的無參構(gòu)造時，存儲數(shù)組的默認(rèn)空間大小為0，也就是空

同時，我們追入elementData數(shù)組，可以發(fā)現(xiàn)他是Object數(shù)組，這也就解釋了為什么ArrayList可以加入任意類型的元素，因為Object是萬物之父！

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

添加數(shù)據(jù)之前的準(zhǔn)備

接下來，當(dāng)我們使用add方法，比如操作下面這行代碼：

arrayList.add(521);

首先，ArrayList會對521進(jìn)行裝箱操作：

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

繼續(xù)步入，進(jìn)入如下代碼：

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

我們來仔細(xì)看一下這段代碼，首先：

modCount++;

在所有的集合實現(xiàn)類中（Collection與Map中），都會有一個 modCount 的變量出現(xiàn)，它的作用就是記錄當(dāng)前集合被修改的次數(shù)。此處將修改次數(shù) + 1，防止多線程操作異常

隨后，進(jìn)入真正添加數(shù)據(jù)的add重載方法：

add(e, elementData, size);

開始添加數(shù)據(jù)

在真正添加數(shù)據(jù)的部分，代碼如下：

可以看到，首先需要判斷elementData數(shù)組的容量是否充足，如果容量已經(jīng)滿了的話，就執(zhí)行g(shù)row方法進(jìn)行擴容，否則就加入數(shù)據(jù)，size + 1

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

那他是怎么進(jìn)行擴容的呢？

我們進(jìn)入grow方法看一下：

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

繼續(xù)步入到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數(shù)組不是初始化狀態(tài)的數(shù)組（也就是已經(jīng)第一次擴容過）

那么通過位運算進(jìn)行擴容到原容量的1.5倍

注意：IDEA在debug默認(rèn)情況下顯示的數(shù)據(jù)是簡化的，如果需要看完整的數(shù)據(jù)，需要進(jìn)行設(shè)置

使用指定大小的構(gòu)造器

原理操作和上面類似，只不過它初始的容量為指定的容量，需要擴容時擴容為原容量的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底層同樣是一個對象數(shù)組

protected Object[] elementData;

和ArrayList不同的是，它是線程同步的，也就是線程安全的

Vector和ArrayList的區(qū)別：

7.LinkedList

鏈表（Linked list）是一種常見的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，是一種線性表，但是并不會按線性的順序存儲數(shù)據(jù)，而是在每一個節(jié)點里存到下一個節(jié)點的地址。

鏈表可分為單向鏈表和雙向鏈表。

一個單向鏈表包含兩個值: 當(dāng)前節(jié)點的值和一個指向下一個節(jié)點的鏈接。

一個雙向鏈表有三個整數(shù)值: 數(shù)值、向后的節(jié)點鏈接、向前的節(jié)點鏈接。

Java LinkedList（鏈表）類似于 ArrayList，是一種常用的數(shù)據(jù)容器。

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

LinkedList的底層是一個雙向鏈表

增加元素源碼分析

在LinkedList鏈表中，存在幾個必知的概念 --> First：鏈表頭節(jié)點；Last：鏈表尾節(jié)點；next：該節(jié)點下一個節(jié)點地址；prev：該節(jié)點前一個節(jié)點地址

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

首先：調(diào)用LinkedList的無參構(gòu)造，這里什么也沒有捏

public LinkedList() {
}

隨后，和ArrayList和Vector一樣，進(jìn)行裝箱操作

開始添加操作：

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

為了方便理解，我們需要知道一下Node的構(gòu)造器內(nèi)容：

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

繼續(xù)步入：

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

這里是關(guān)鍵，接下來我們來分析一下上面的這段代碼：

首先，將last的值賦給l，新建一個Node節(jié)點，將last指向新建的Node節(jié)點，隨后進(jìn)行分支判斷，將first也指向新建的Node節(jié)點

最后，鏈表大小 + 1 ，修改次數(shù) + 1

經(jīng)過了上面的修改，現(xiàn)在的first和last都指向新建的節(jié)點，該節(jié)點的next和prev都為null

以上是鏈表中只有一個元素的情況，那么再次向鏈表添加元素呢？我們再來淺淺看一下

第二次添加節(jié)點，l被置為上一個節(jié)點的地址，隨后會被添加到新節(jié)點的prev屬性中：

還需要更新一下last的值為新添加進(jìn)來的節(jié)點的地址：

隨后，將上一個節(jié)點的next值置為當(dāng)前新加的節(jié)點地址：

最后，更新size和modCount即可！

刪除元素源碼分析

// 刪除最后一個節(jié)點
linkedList.remove();

進(jìn)行源碼分析，步入：

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

繼續(xù)步入：

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

Java的設(shè)計者在這里獲取了鏈表頭節(jié)點的地址，以備后續(xù)進(jìn)行刪除，隨后檢查了一個頭節(jié)點為空的異常，在unlinkFirst方法，將會真正執(zhí)行刪除的操作！

繼續(xù)步入：

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

開頭，獲取頭節(jié)點的值，以備在后續(xù)返回：

final E element = f.item;

先獲取一下頭節(jié)點后面的節(jié)點的地址，保存下來，然后將頭節(jié)點的數(shù)據(jù)和next置空，請求GC進(jìn)行回收：

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

頭節(jié)點更新為原頭節(jié)點的下一個節(jié)點，并作節(jié)點個數(shù)判斷：

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);
        // 刪除頭節(jié)點
        linkedList.remove();
        System.out.println(linkedList);
        // 修改
        linkedList.set(0,999);
        System.out.println(linkedList);
        // 查找
        System.out.println(linkedList.get(0));
    }
}

輸出：