ArrayList和LinkedList

這篇具有很好參考價值的文章主要介紹了ArrayList和LinkedList。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

ArrayList

1.ArrayList簡介

2.ArrayList使用

2.1ArrayList的構(gòu)造?

?2.2ArrayList常見操作

2.3ArrayList的遍歷

2.4ArrayList的擴容機制

3.ArrayList的具體使用

4.ArrayList的問題

5.ArrayList的缺陷

LinkedList

1.LinkedList的模擬實現(xiàn)

2.LinkedList的使用

2.1什么是LinkedList

2.2LinkedList的使用

ArrayList和LinkedList的區(qū)別

ArrayList

1.ArrayList簡介

在集合框架中， ArrayList 是一個普通的類，實現(xiàn)了 List 接口，具體框架圖如下：

【說明】

1. ArrayList 是以泛型方式實現(xiàn)的，使用時必須要先實例化

2. ArrayList 實現(xiàn)了 RandomAccess 接口，表明 ArrayList 支持隨機訪問

3. ArrayList 實現(xiàn)了 Cloneable 接口，表明 ArrayList 是可以 clone 的

4. ArrayList 實現(xiàn)了 Serializable 接口，表明 ArrayList 是支持序列化的

5. 和 Vector 不同， ArrayList 不是線程安全的，在單線程下可以使用，在多線程中可以選擇 Vector 或者

CopyOnWriteArrayList

6. ArrayList 底層是一段連續(xù)的空間，并且可以動態(tài)擴容，是一個動態(tài)類型的順序表

2.ArrayList使用

2.1ArrayList的構(gòu)造?

ArrayList和LinkedList

public static void main(String[] args) {
    // ArrayList創(chuàng)建，推薦寫法
    // 構(gòu)造一個空的列表
    List<Integer> list1 = new ArrayList<>();
    // 構(gòu)造一個具有10個容量的列表
    List<Integer> list2 = new ArrayList<>(10);
    list2.add(1);
    list2.add(2);
    list2.add(3);
    // list2.add("hello"); // 編譯失敗，List<Integer>已經(jīng)限定了，list2中只能存儲整形元素
    // list3構(gòu)造好之后，與list中的元素一致
    ArrayList<Integer> list3 = new ArrayList<>(list2);
    // 避免省略類型，否則：任意類型的元素都可以存放，使用時將是一場災(zāi)難
    List list4 = new ArrayList();
    list4.add("111");
    list4.add(100);
}

?2.2ArrayList常見操作

ArrayList 雖然提供的方法比較多，但是常用方法如下所示，需要用到其他方法時，同學們自行查看 ArrayList 的幫助文檔。

方法	解釋
boolean add (E e)	尾插 e
void add (int index, E element)	將 e 插入到 index 位置
boolean addAll (Collection<? extends E> c)	尾插 c 中的元素
E remove (int index)	刪除 index 位置元素
boolean remove (Object o)	刪除遇到的第一個 o
E get (int index)	獲取下標 index 位置元素
E set (int index, E element)	將下標 index 位置元素設(shè)置為 element
void clear ()	清空
boolean contains (Object o)	判斷 o 是否在線性表中
int indexOf (Object o)	返回第一個 o 所在下標
int lastIndexOf (Object o)	返回最后一個 o 的下標
List<E> subList (int fromIndex, int toIndex)	截取部分 list

public static void main(String[] args) {
    List<String> list = new ArrayList<>();
    list.add("JavaSE");
    list.add("JavaWeb");
    list.add("JavaEE");
    list.add("JVM");
    list.add("測試課程");
    System.out.println(list);
    // 獲取list中有效元素個數(shù)
    System.out.println(list.size());
    // 獲取和設(shè)置index位置上的元素，注意index必須介于[0, size)間
    System.out.println(list.get(1));
    list.set(1, "JavaWEB");
    System.out.println(list.get(1));
    // 在list的index位置插入指定元素，index及后續(xù)的元素統(tǒng)一往后搬移一個位置
    list.add(1, "Java數(shù)據(jù)結(jié)構(gòu)");
    System.out.println(list);
    // 刪除指定元素，找到了就刪除，該元素之后的元素統(tǒng)一往前搬移一個位置
    list.remove("JVM");
    System.out.println(list);
    // 刪除list中index位置上的元素，注意index不要超過list中有效元素個數(shù),否則會拋出下標越界異常
    list.remove(list.size()-1);
    System.out.println(list);
    // 檢測list中是否包含指定元素，包含返回true，否則返回false
    if(list.contains("測試課程")){
    list.add("測試課程");
    }
    // 查找指定元素第一次出現(xiàn)的位置：indexOf從前往后找，lastIndexOf從后往前找
    list.add("JavaSE");
    System.out.println(list.indexOf("JavaSE"));
    System.out.println(list.lastIndexOf("JavaSE"));
    // 使用list中[0, 4)之間的元素構(gòu)成一個新的SubList返回,但是和ArrayList共用一個elementData數(shù)組
    List<String> ret = list.subList(0, 4);
    System.out.println(ret);
    list.clear();
    System.out.println(list.size());
}

2.3ArrayList的遍歷

ArrayList 可以使用三方方式遍歷： for 循環(huán) + 下標、 foreach 、使用迭代器

public static void main(String[] args) {
    List<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(4);
    list.add(5);
    // 使用下標+for遍歷
    for (int i = 0; i < list.size(); i++) {
    System.out.print(list.get(i) + " ");
    }
    System.out.println();
    // 借助foreach遍歷
    for (Integer integer : list) {
    System.out.print(integer + " ");
    }
    System.out.println();
    Iterator<Integer> it = list.listIterator();
    while(it.hasNext()){
    System.out.print(it.next() + " ");
    }
    System.out.println();
}

注意：

1. ArrayList 最長使用的遍歷方式是： for 循環(huán) + 下標以及 foreach

2. 迭代器是設(shè)計模式的一種，后序容器接觸多了再給大家鋪墊

2.4ArrayList的擴容機制

ArrayList 是一個動態(tài)類型的順序表，即：在插入元素的過程中會自動擴容。以下是 ArrayList 源碼中擴容方式：

Object[] elementData; // 存放元素的空間
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 默認空間
private static final int DEFAULT_CAPACITY = 10; // 默認容量大小
public boolean add(E e) {
    ensureCapacityInternal(size + 1); // Increments modCount!!
    elementData[size++] = e;
    return true;
}
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
    grow(minCapacity);
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
    // 獲取舊空間大小
    int oldCapacity = elementData.length;
    // 預(yù)計按照1.5倍方式擴容
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果用戶需要擴容大小 超過 原空間1.5倍，按照用戶所需大小擴容
    if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;
    // 如果需要擴容大小超過MAX_ARRAY_SIZE，重新計算容量大小
    if (newCapacity - MAX_ARRAY_SIZE > 0)
    newCapacity = hugeCapacity(minCapacity);
    // 調(diào)用copyOf擴容
    elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
    // 如果minCapacity小于0，拋出OutOfMemoryError異常
    if (minCapacity < 0)
    throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

【 總結(jié) 】

1. 檢測是否真正需要擴容，如果是調(diào)用 grow 準備擴容

2. 預(yù)估需要庫容的大小

初步預(yù)估按照1.5倍大小擴容
如果用戶所需大小超過預(yù)估1.5倍大小，則按照用戶所需大小擴容
真正擴容之前檢測是否能擴容成功，防止太大導致擴容失敗

3. 使用 copyOf 進行擴容

3.ArrayList的具體使用

簡單的洗牌算法

public class Card {
    public int rank; // 牌面值
    public String suit; // 花色
    @Override
    public String toString() {
    return String.format("[%s %d]", suit, rank);
    }
}

import java.util.List;
import java.util.ArrayList;
import java.util.Random;
public class CardDemo {
    public static final String[] SUITS = {"?", "?", "?", "?"};
    // 買一副牌
    private static List<Card> buyDeck() {
        List<Card> deck = new ArrayList<>(52);
        for (int i = 0; i < 4; i++) {
            for (int j = 1; j <= 13; j++) {
            String suit = SUITS[i];
            int rank = j;
            Card card = new Card();
            card.rank = rank;
            card.suit = suit;
            deck.add(card);
            }
        }
        return deck;
    }
    private static void swap(List<Card> deck, int i, int j) {
        Card t = deck.get(i);
        deck.set(i, deck.get(j));
        deck.set(j, t);
    }
    private static void shuffle(List<Card> deck) {
        Random random = new Random(20190905);
        for (int i = deck.size() - 1; i > 0; i--) {
        int r = random.nextInt(i);
        swap(deck, i, r);
        }
    }
    public static void main(String[] args) {
        List<Card> deck = buyDeck();
        System.out.println("剛買回來的牌:");
        System.out.println(deck);
        shuffle(deck);
        System.out.println("洗過的牌:");
        System.out.println(deck);
        // 三個人，每個人輪流抓 5 張牌
        List<List<Card>> hands = new ArrayList<>();
        hands.add(new ArrayList<>());
        hands.add(new ArrayList<>());
        hands.add(new ArrayList<>());
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 3; j++) {
            hands.get(j).add(deck.remove(0));
            }
        }
        System.out.println("剩余的牌:");
        System.out.println(deck);
        System.out.println("A 手中的牌:");
        System.out.println(hands.get(0));
        System.out.println("B 手中的牌:");
        System.out.println(hands.get(1));
        System.out.println("C 手中的牌:");
        System.out.println(hands.get(2));
    }
}

運行結(jié)果

剛買回來的牌:
[[? 1], [? 2], [? 3], [? 4], [? 5], [? 6], [? 7], [? 8], [? 9], [? 10], [? 11], [? 12], [? 13], [? 1], [? 2], [? 3], [? 4], [? 5], [? 6], [? 7],
[? 8], [? 9], [? 10], [? 11], [? 12], [? 13], [? 1], [? 2], [? 3], [? 4], [? 5], [? 6], [? 7], [? 8], [? 9], [? 10], [? 11], [? 12], [?
13], [? 1], [? 2], [? 3], [? 4], [? 5], [? 6], [? 7], [? 8], [? 9], [? 10], [? 11], [? 12], [? 13]]
洗過的牌:
[[? 11], [? 6], [? 13], [? 10], [? 13], [? 2], [? 1], [? 9], [? 12], [? 5], [? 8], [? 6], [? 3], [? 5], [? 1], [? 6], [? 13], [? 12], [? 12],
[? 5], [? 4], [? 3], [? 7], [? 3], [? 2], [? 1], [? 2], [? 4], [? 8], [? 10], [? 11], [? 10], [? 7], [? 9], [? 4], [? 8], [? 7], [? 8], [? 9], [?
12], [? 11], [? 11], [? 10], [? 5], [? 13], [? 9], [? 7], [? 6], [? 4], [? 2], [? 1], [? 3]]
剩余的牌:
[[? 6], [? 13], [? 12], [? 12], [? 5], [? 4], [? 3], [? 7], [? 3], [? 2], [? 1], [? 2], [? 4], [? 8], [? 10], [? 11], [? 10], [? 7], [? 9], [?
4], [? 8], [? 7], [? 8], [? 9], [? 12], [? 11], [? 11], [? 10], [? 5], [? 13], [? 9], [? 7], [? 6], [? 4], [? 2], [? 1], [? 3]]
A 手中的牌:
[[? 11], [? 10], [? 1], [? 5], [? 3]]
B 手中的牌:
[[? 6], [? 13], [? 9], [? 8], [? 5]]
C 手中的牌:
[[? 13], [? 2], [? 12], [? 6], [? 1]]

4.ArrayList的問題

1. ArrayList 底層使用連續(xù)的空間，任意位置插入或刪除元素時，需要將該位置后序元素整體往前或者往后搬移，故時間復雜度為O(N)

2. 增容需要申請新空間，拷貝數(shù)據(jù)，釋放舊空間。會有不小的消耗。

3. 增容一般是呈 2 倍的增長，勢必會有一定的空間浪費。例如當前容量為 100 ，滿了以后增容到 200 ，我們再繼續(xù)插入了5 個數(shù)據(jù)，后面沒有數(shù)據(jù)插入了，那么就浪費了 95 個數(shù)據(jù)空間。

5.ArrayList的缺陷

通過源碼知道， ArrayList 底層使用數(shù)組來存儲元素：

由于其底層是一段連續(xù)空間，當在 ArrayList 任意位置插入或者刪除元素時，就需要將后序元素整體往前或者往后 搬移，時間復雜度為 O(n) ，效率比較低，因此 ArrayList 不適合做任意位置插入和刪除比較多的場景 。因此： java集合中又引入了LinkedList ，即鏈表結(jié)構(gòu)。

LinkedList

1.LinkedList的模擬實現(xiàn)

// 2、無頭雙向鏈表實現(xiàn)
public class MyLinkedList {
    //頭插法
    public void addFirst(int data){ }
    //尾插法
    public void addLast(int data){}
    //任意位置插入,第一個數(shù)據(jù)節(jié)點為0號下標
    public void addIndex(int index,int data){}
    //查找是否包含關(guān)鍵字key是否在單鏈表當中
    public boolean contains(int key){}
    //刪除第一次出現(xiàn)關(guān)鍵字為key的節(jié)點
    public void remove(int key){}
    //刪除所有值為key的節(jié)點
    public void removeAllKey(int key){}
    //得到單鏈表的長度
    public int size(){}
    public void display(){}
    public void clear(){}
}

2.LinkedList的使用

2.1什么是LinkedList

LinkedList 的底層是雙向鏈表結(jié)構(gòu) ( 鏈表后面介紹 ) ，由于鏈表沒有將元素存儲在連續(xù)的空間中，元素存儲在單獨的節(jié)點中，然后通過引用將節(jié)點連接起來了，因此在在任意位置插入或者刪除元素時，不需要搬移元素，效率比較高。

ArrayList和LinkedList

?在集合框架中，LinkedList也實現(xiàn)了List接口，具體如下：

ArrayList和LinkedList

【說明】

????????1. LinkedList實現(xiàn)了 List 接口

????????2. LinkedList的底層使用了雙向鏈表

????????3. LinkedList沒有實現(xiàn) RandomAccess 接口，因此 LinkedList 不支持隨機訪問

????????4. LinkedList的任意位置插入和刪除元素時效率比較高，時間復雜度為 O(1)

????????5. LinkedList比較適合任意位置插入的場景

2.2LinkedList的使用

LinkedList 的構(gòu)造

ArrayList和LinkedList

public static void main(String[] args) {
    // 構(gòu)造一個空的LinkedList
    List<Integer> list1 = new LinkedList<>();
    List<String> list2 = new java.util.ArrayList<>();
    list2.add("JavaSE");
    list2.add("JavaWeb");
    list2.add("JavaEE");
    // 使用ArrayList構(gòu)造LinkedList
    List<String> list3 = new LinkedList<>(list2);
}

?LinkedList的其他常用方法介紹

方法	解釋
boolean add (E e)	尾插 e
void add (int index, E element)	將 e 插入到 index 位置
boolean addAll (Collection<? extends E> c)	尾插 c 中的元素
E remove (int index)	刪除 index 位置元素
boolean remove (Object o)	刪除遇到的第一個 o
E get (int index)	獲取下標 index 位置元素
E set (int index, E element)	將下標 index 位置元素設(shè)置為 element
void clear ()	清空
boolean contains (Object o)	判斷 o 是否在線性表中
int indexOf (Object o)	返回第一個 o 所在下標
int lastIndexOf (Object o)	返回最后一個 o 的下標
List<E> subList (int fromIndex, int toIndex)	截取部分 list

public static void main(String[] args) {
    LinkedList<Integer> list = new LinkedList<>();
    list.add(1); // add(elem): 表示尾插
    list.add(2);
    list.add(3);
    list.add(4);
    list.add(5);
    list.add(6);
    list.add(7);
    System.out.println(list.size());
    System.out.println(list);
    // 在起始位置插入0
    list.add(0, 0); // add(index, elem): 在index位置插入元素elem
    System.out.println(list);
    list.remove(); // remove(): 刪除第一個元素，內(nèi)部調(diào)用的是removeFirst()
    list.removeFirst(); // removeFirst(): 刪除第一個元素
    list.removeLast(); // removeLast(): 刪除最后元素
    list.remove(1); // remove(index): 刪除index位置的元素
    System.out.println(list);
    // contains(elem): 檢測elem元素是否存在，如果存在返回true，否則返回false
    if(!list.contains(1)){
        list.add(0, 1);
    }
    list.add(1);
    System.out.println(list);
    System.out.println(list.indexOf(1)); // indexOf(elem): 從前往后找到第一個elem的位置
    System.out.println(list.lastIndexOf(1)); // lastIndexOf(elem): 從后往前找第一個1的位置
    int elem = list.get(0); // get(index): 獲取指定位置元素
    list.set(0, 100); // set(index, elem): 將index位置的元素設(shè)置為elem
    System.out.println(list);
    // subList(from, to): 用list中[from, to)之間的元素構(gòu)造一個新的LinkedList返回
    List<Integer> copy = list.subList(0, 3); 
    System.out.println(list);
    System.out.println(copy);
    list.clear(); // 將list中元素清空
    System.out.println(list.size());
}

LinkedList 的遍歷

public static void main(String[] args) {
    LinkedList<Integer> list = new LinkedList<>();
    list.add(1); // add(elem): 表示尾插
    list.add(2);
    list.add(3);
    list.add(4);
    list.add(5);
    list.add(6);
    list.add(7);
    System.out.println(list.size());
    // foreach遍歷
    for (int e:list) {
        System.out.print(e + " ");
    }
    System.out.println();
    // 使用迭代器遍歷---正向遍歷
    ListIterator<Integer> it = list.listIterator();
    while(it.hasNext()){
        System.out.print(it.next()+ " ");
    }
    System.out.println();
    // 使用反向迭代器---反向遍歷
    ListIterator<Integer> rit = list.listIterator(list.size());
    while (rit.hasPrevious()){
        System.out.print(rit.previous() +" ");
    }
    System.out.println();
}