數(shù)據(jù)結(jié)構(gòu)是編程的起點(diǎn)屈芜，理解數(shù)據(jù)結(jié)構(gòu)可以從三方面入手：

1. 邏輯結(jié)構(gòu)郊愧。邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系，可分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)井佑，線性表是典型的線性結(jié)構(gòu)属铁，非線性結(jié)構(gòu)包括集合、樹(shù)和圖躬翁。
2. 存儲(chǔ)結(jié)構(gòu)焦蘑。存儲(chǔ)結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)中的物理表示，可分為順序存儲(chǔ)盒发、鏈?zhǔn)酱鎯?chǔ)例嘱、索引存儲(chǔ)和散列存儲(chǔ)。數(shù)組是典型的順序存儲(chǔ)結(jié)構(gòu)宁舰；鏈表采用鏈?zhǔn)酱鎯?chǔ)拼卵；索引存儲(chǔ)的優(yōu)點(diǎn)是檢索速度快，但需要增加附加的索引表蛮艰，會(huì)占用較多的存儲(chǔ)空間腋腮；散列存儲(chǔ)使得檢索、增加和刪除結(jié)點(diǎn)的操作都很快壤蚜，缺點(diǎn)是解決散列沖突會(huì)增加時(shí)間和空間開(kāi)銷即寡。
3. 數(shù)據(jù)運(yùn)算。施加在數(shù)據(jù)上的運(yùn)算包括運(yùn)算的定義和實(shí)現(xiàn)仍律。運(yùn)算的定義是針對(duì)邏輯結(jié)構(gòu)的嘿悬，指出運(yùn)算的功能；運(yùn)算的實(shí)現(xiàn)是針對(duì)存儲(chǔ)結(jié)構(gòu)的水泉，指出運(yùn)算的具體操作步驟善涨。

因此，本章將以邏輯結(jié)構(gòu)（線性表草则、樹(shù)钢拧、散列、優(yōu)先隊(duì)列和圖）為縱軸炕横，以存儲(chǔ)結(jié)構(gòu)和運(yùn)算為橫軸源内，分析常見(jiàn)數(shù)據(jù)結(jié)構(gòu)的定義和實(shí)現(xiàn)。

在Java中談到數(shù)據(jù)結(jié)構(gòu)時(shí)份殿，首先想到的便是下面這張Java集合框架圖：

Java 集合框架圖

從圖中可以看出膜钓，Java集合類大致可分為L(zhǎng)ist嗽交、Set、Queue和Map四種體系颂斜，其中：

• List代表有序夫壁、重復(fù)的集合；
• Set代表無(wú)序沃疮、不可重復(fù)的集合盒让；
• Queue代表一種隊(duì)列集合實(shí)現(xiàn)；
• Map代表具有映射關(guān)系的集合司蔬。

在實(shí)現(xiàn)上邑茄，List、Set和Queue均繼承自Collection俊啼，因此肺缕，Java集合框架主要由Collection和Map兩個(gè)根接口及其子接口、實(shí)現(xiàn)類組成授帕。

本文將重點(diǎn)探討線性表的定義和實(shí)現(xiàn)搓谆，首先梳理Collection接口及其子接口的關(guān)系，其次從存儲(chǔ)結(jié)構(gòu)（順序表和鏈表）維度分析線性表的實(shí)現(xiàn)豪墅，最后通過(guò)線性表結(jié)構(gòu)導(dǎo)出棧泉手、隊(duì)列的模型與實(shí)現(xiàn)原理。主要內(nèi)容如下：

1. Iterator偶器、Collection及List接口
2. ArrayList / LinkedList實(shí)現(xiàn)原理
3. Stack / Queue模型與實(shí)現(xiàn)

一斩萌、Iterator、Collection及List接口

Collection接口是List屏轰、Set和Queue的根接口颊郎，抽象了集合類所能提供的公共方法，包含size()霎苗、isEmpty()姆吭、add(E e)、remove(Object o)唁盏、contains(Object o)等把将，iterator()返回集合類迭代器娃闲。

public interface Collection<E> extends Iterable<E> {
    int size();
    boolean isEmpty();
    Iterator<E> iterator();
    boolean add(E e);
    boolean addAll(Collection<? extends E> c);
    boolean remove(Object o);
    boolean removeAll(Collection<?> c);
    boolean contains(Object o);
    boolean containsAll(Collection<?> c);
    void clear();
    boolean equals(Object o);
    int hashCode();
}

Collection接口繼承自Iterable接口俯逾，實(shí)現(xiàn)Iterable接口的集合類可以通過(guò)迭代器對(duì)元素進(jìn)行安全嚼吞、高效的遍歷，比如for-each刽严，Iterable的iterator方法負(fù)責(zé)返回Iterator迭代器昂灵。

public interface Iterable<T> {
    Iterator<T> iterator();
}

Iterator迭代器包含集合迭代時(shí)兩個(gè)最常用的方法：hasNext和next。hasNext用于查詢集合是否存在下一項(xiàng)，next方法用于獲取下一項(xiàng)眨补。

public interface Iterator<E> {
    boolean hasNext();
    E next();
}

List接口繼承自Collection接口管削，相比于Collection接口已有的增刪改查的方法，List主要增加了index屬性和ListIterator接口撑螺。因此佩谣，除Collection接口方法，List接口的主要方法如下：

public interface List<E> extends Collection<E> {
    public E get(int location);
    public int indexOf(Object object);
    public int lastIndexOf(Object object);
    public ListIterator<E> listIterator();
    // ……
}

ListIterator接口繼承Iterator接口实蓬，因此，在正向遍歷方法hasNext和next的基礎(chǔ)上吊履，ListIterator接口增加了實(shí)現(xiàn)逆序遍歷的方法hasPrevious和previous安皱，使其具有雙向遍歷的特性。如下所示：

public interface ListIterator<E> extends Iterator<E> {
    public boolean hasPrevious();
    public E previous();
    public int previousIndex();
    // ……
}

下面舉個(gè)栗子說(shuō)明采用ListIterator進(jìn)行雙向遍歷艇炎。

List<String> list = new ArrayList<>();
list.add("aaa");
list.add("bbb");
list.add("ccc");

ListIterator<String> listIterator = list.listIterator();
while(listIterator.hasNext()) {
    System.out.print(listIterator.next());
}
while (listIterator.hasPrevious()) {
    System.out.print(listIterator.previous());
}

ArrayList通過(guò)內(nèi)部類Itr實(shí)現(xiàn)了ListIterator接口酌伊，Itr包含指示迭代器當(dāng)前位置的域cursor，next()方法會(huì)把cursor向后推動(dòng)缀踪，相反居砖，previous()方法則把cursor向前推動(dòng)，所以上述代碼能對(duì)該List的元素進(jìn)行雙向遍歷驴娃。

另外奏候，在List上使用for-each語(yǔ)法遍歷集合時(shí)，編譯器判斷List實(shí)現(xiàn)了Iterable接口唇敞，會(huì)調(diào)用iterator的方法來(lái)代替for循環(huán)蔗草。

// 程序版本
private void traversalA() {
    for (String s : list) {
        Log.d("TraversalA Test:", s);
    }
}
// 編譯器版本
private void traversalB() {
    Iterator<String> iterator = list.iterator();
    while (iterator.hasNext()) {
        String s = iterator.next();
        Log.d("TraversalB:", s);
    }
}

二、ArrayList / LinkedList實(shí)現(xiàn)原理

Java程序員都知道ArrayList 基于數(shù)組疆柔、LinkedList基于鏈表實(shí)現(xiàn)咒精，因此，這里不再對(duì)基本原理進(jìn)行贅述旷档，下面主要從數(shù)據(jù)結(jié)構(gòu)模叙、添加/刪除方法和迭代器三個(gè)方面分別說(shuō)明ArrayList和LinkedList實(shí)現(xiàn)原理：

2.1 ArrayList實(shí)現(xiàn)原理

ArrayList是可改變大小的、基于索引的數(shù)組鞋屈，使用索引讀取數(shù)組中的元素的時(shí)間復(fù)雜度是O(1)范咨，但通過(guò)索引插入和刪除元素卻需要重排該索引后所有的元素，因此消耗較大厂庇。但相比于LinkedList湖蜕，其內(nèi)存占用是連續(xù)的，空間利用效率更高宋列。

2.1.1 擴(kuò)容

擴(kuò)容是ArrayList能夠改變?cè)卮鎯?chǔ)數(shù)組大小的保證昭抒。在JDK1.8中，ArrayList存放元素的數(shù)組的默認(rèn)容量是10，當(dāng)集合中元素?cái)?shù)量超過(guò)它時(shí)灭返，就需要擴(kuò)容盗迟。另外，ArrayList最大的存儲(chǔ)長(zhǎng)度為Integer.MAX_VALUE - 8（虛擬機(jī)可能會(huì)在數(shù)組中添加一些頭信息熙含，這樣避免內(nèi)存溢出）罚缕。

private static final int DEFAULT_CAPACITY = 10;
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

擴(kuò)容方法主要通過(guò)三步實(shí)現(xiàn)：1）保存舊數(shù)組；2）擴(kuò)展新數(shù)組怎静；3）把舊數(shù)據(jù)拷貝回新數(shù)組邮弹。

// 擴(kuò)容方法
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    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);
}
// Arrays拷貝
public static <T> T[] copyOf(T[] original, int newLength) {
    return (T[]) copyOf(original, newLength, original.getClass());
}
// 調(diào)用System.arraycopy實(shí)現(xiàn)
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    T[] copy = ((Object)newType == (Object)Object[].class) ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));
    return copy;
}

由于oldCapacity >> 1等于oldCapacity / 2，所以擴(kuò)容后的數(shù)組大小為舊數(shù)組大小的1.5倍蚓聘。另外腌乡，Arrays中的靜態(tài)方法是通過(guò)調(diào)用Native方法System.arraycopy來(lái)實(shí)現(xiàn)的。

2.1.2 add / remove方法

當(dāng)在ArrayList末尾添加/刪除元素時(shí)夜牡，由于對(duì)其他元素沒(méi)有影響与纽，所以時(shí)間負(fù)責(zé)度仍為O(1)。這里忽略這種情況塘装，以通過(guò)索引插入/刪除數(shù)據(jù)為例說(shuō)明add / remove方法的實(shí)現(xiàn)：

public void add(int index, E element) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    elementData[index] = element;
    size++;
}

public E remove(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    modCount++;
    E oldValue = (E) elementData[index];

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

public static native void arraycopy(Object src,  int  srcPos, 
                            Object dest, int destPos, int length);

添加元素時(shí)急迂，首先確保數(shù)組容量足夠存放size+1個(gè)元素，然后將index后的size-index個(gè)元素依次后移一位蹦肴，在index處保存新加入的元素element僚碎，同時(shí)增加元素總量；與添加元素相反阴幌，刪除元素時(shí)將index后的size-(index+1)個(gè)元素依次前移動(dòng)一位听盖，同時(shí)減小元素總量×哑撸可見(jiàn)皆看，添加/刪除元素均通過(guò)調(diào)用System.arraycopy方法來(lái)實(shí)現(xiàn)數(shù)據(jù)的移動(dòng)，效率較高背零。但另一方面腰吟，從上述實(shí)現(xiàn)可以看出，ArrayList并非線程安全徙瓶，在并發(fā)環(huán)境下需要使用線程安全的容器類毛雇。

2.1.3 Iterator和ListIterator

如前所述，ArrayList實(shí)現(xiàn)了List接口侦镇，其包含兩種迭代器：Iterator和ListIterator灵疮，ListIterator相比于Iterator能實(shí)現(xiàn)前向遍歷。在ArrayList中壳繁，通過(guò)內(nèi)部類Itr實(shí)現(xiàn)了Iterator接口震捣，內(nèi)部類ListItr繼承自Itr并且實(shí)現(xiàn)了ListIterator荔棉，因此，ArrayList的iterator()方法放回的是Itr對(duì)象蒿赢，listIterator()方法反回ListIterator對(duì)象润樱。

private class Itr implements Iterator<E> {
    int cursor;
    int lastRet = -1;
    int expectedModCount = modCount;
    // ……
}

private class ListItr extends Itr implements ListIterator<E> {
    ListItr(int index) {
        super();
        cursor = index;
    }
    
    // ……
}

public Iterator<E> iterator() {
    return new Itr();
}

public ListIterator<E> listIterator() {
    return new ListItr(0);
}

Itr的成員變量中，cursor表示下一個(gè)訪問(wèn)對(duì)象的索引羡棵，lastRet表示上一個(gè)訪問(wèn)對(duì)象的索引壹若，expectedModCount表示對(duì)ArrayList修改次數(shù)的期望值，初始值為modCount皂冰，而modCount是ArrayList父類AbstractList中定義的成員變量店展，初始值為0，在上述add()和remove()方法中秃流，都會(huì)對(duì)modCount加1赂蕴，增加修改次數(shù)。

在使用ArrayList的remove()方法進(jìn)行對(duì)象刪除時(shí)剔应，一種常見(jiàn)的運(yùn)行時(shí)異常是ConcurrentModificationException，雖名為并發(fā)修改異常语御，但實(shí)際上單線程環(huán)境中也可能報(bào)出峻贮，原因就是上述expectedModCount與modCount不相等的問(wèn)題。

一種常見(jiàn)的使用場(chǎng)景是通過(guò)for-each語(yǔ)法刪除元素：

public void removeElement(List<Integer> list) {
    for (Integer x : list) {
        if (x % 2 == 0) {
            list.remove(x); // 調(diào)用ArrayList的remove方法
        }
    }
}

上節(jié)提到应闯，for-each是一種語(yǔ)法糖纤控，編譯之后依然調(diào)用了迭代器實(shí)現(xiàn)。而迭代器的next()方法會(huì)首先調(diào)用checkForComodification()方法檢查expectedModCount與modCount碉纺，如果不等就拋出ConcurrentModificationException船万。

final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

所以，當(dāng)上述代碼中調(diào)用ArrayList的remove刪除元素后骨田，modCount自增耿导，而迭代器中expectedModCount保持不變，就會(huì)拋出ConcurrentModificationException态贤，但是舱呻，如果使用迭代器的remove()方法則不會(huì)拋出異常，為什么呢悠汽？

public void removeElement2(List<Integer> list) {
    Iterator<Integer> itr = list.iterator();
    while (itr.hasNext()) {
        if (itr.next() % 2 == 0) {
            itr.remove(); // 調(diào)用迭代器的remove方法
        }
    }
}

public void remove() {
    if (lastRet < 0)
        throw new IllegalStateException();
    checkForComodification();

    try {
        ArrayList.this.remove(lastRet); // 調(diào)用ArrayList的remove方法
        cursor = lastRet;
        lastRet = -1;
        expectedModCount = modCount; // 設(shè)置expectedModCount 為modCount
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}

從代碼中可以看出箱吕，其實(shí)迭代的remove方法也是調(diào)用了ArrayList的remove方法實(shí)現(xiàn)元素刪除，只不過(guò)在刪除元素之后設(shè)置了expectedModCount為modCount柿冲，避免checkForComodification時(shí)拋出異常茬高。

2.2 LinkedList實(shí)現(xiàn)原理

鏈表按照鏈接形式可分為：?jiǎn)捂湵怼㈦p鏈表和循環(huán)鏈表假抄。單鏈表節(jié)點(diǎn)包含兩個(gè)域：信息域和指針域怎栽，信息域存放元素丽猬，指針域指向下一個(gè)節(jié)點(diǎn)，因此只支持單向遍歷婚瓜。其結(jié)構(gòu)如下圖所示：

單鏈表存儲(chǔ)結(jié)構(gòu)

相比于單鏈表宝鼓，雙鏈表節(jié)點(diǎn)包含三個(gè)域：信息域、前向指針域和后向指針域巴刻，前向指針指向前一個(gè)節(jié)點(diǎn)地址愚铡，后向指針指向后一個(gè)節(jié)點(diǎn)地址，因此可以實(shí)現(xiàn)雙向的遍歷胡陪。其結(jié)構(gòu)如下圖所示：

雙鏈表存儲(chǔ)結(jié)構(gòu)

循環(huán)鏈表分為單循環(huán)鏈表和雙循環(huán)鏈表沥寥。即在普通單鏈表和雙鏈表的基礎(chǔ)上增加了鏈表頭節(jié)點(diǎn)和尾節(jié)點(diǎn)的相互指向。頭節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)是尾節(jié)點(diǎn)柠座，尾節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)是頭節(jié)點(diǎn)邑雅。其結(jié)構(gòu)如下圖所示：

循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)

LinkedList基于雙鏈表實(shí)現(xiàn)，插入和刪除元素的時(shí)間復(fù)雜度是O(1)妈经，支持這種實(shí)現(xiàn)的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)是LinkedList中定義的靜態(tài)內(nèi)部類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;
    }
}

Node有三個(gè)成員變量：item負(fù)責(zé)存儲(chǔ)元素淮野，next和prev分別指向下一個(gè)節(jié)點(diǎn)和前一個(gè)節(jié)點(diǎn)，因此可實(shí)現(xiàn)雙向的元素訪問(wèn)吹泡，LinkedList的操作方法都是基于Node節(jié)點(diǎn)特性設(shè)計(jì)的骤星。

2.2.1 插入/刪除元素

在實(shí)現(xiàn)上，由于Deque接口同時(shí)具有隊(duì)列（雙向）和棧的特性爆哑，LinkedList實(shí)現(xiàn)了Deque接口洞难，使得LinkedList能同時(shí)支持鏈表、隊(duì)列（雙向）和棧的操作揭朝。其插入/刪除方法如下表所示：

三者的差別在于队贱，offer在鏈表末尾插入元素，調(diào)用linkLast實(shí)現(xiàn)潭袱；push在鏈表頭部插入元素柱嫌，調(diào)用linkFirst實(shí)現(xiàn)；而add在指定位置插入元素屯换，根據(jù)位置判斷調(diào)用linkLast或linkBefore方法慎式。這里重點(diǎn)關(guān)注linkLast、linkFirst和linkBefore的實(shí)現(xiàn)趟径。

private void linkFirst(E e) {
    final Node<E> f = first;
    // 創(chuàng)建新節(jié)點(diǎn)瘪吏，其prev節(jié)點(diǎn)為null，元素值為e蜗巧，next結(jié)點(diǎn)為之前的first節(jié)點(diǎn)
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    // 如果初始列表為空掌眠，則將尾結(jié)點(diǎn)設(shè)置為當(dāng)前新節(jié)點(diǎn)
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    // 增加鏈表數(shù)量及修改次數(shù)
    size++;
    modCount++;
}

void linkLast(E e) {
    final Node<E> l = last;
    // 創(chuàng)建新節(jié)點(diǎn)，其prev結(jié)點(diǎn)為之前的尾節(jié)點(diǎn)幕屹，元素值為e蓝丙，next節(jié)點(diǎn)為null
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    // 如果初始列表為空级遭，則將頭結(jié)點(diǎn)設(shè)置為當(dāng)前新節(jié)點(diǎn)
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    // 增加鏈表數(shù)量及修改次數(shù)
    size++;
    modCount++;
}

void linkBefore(E e, Node<E> succ) {
    // 創(chuàng)建succ的prev節(jié)點(diǎn)引用
    final Node<E> pred = succ.prev;
    // 創(chuàng)建新節(jié)點(diǎn)，其prev節(jié)點(diǎn)為succ的prev節(jié)點(diǎn)渺尘，元素值為e挫鸽，next節(jié)點(diǎn)為succ
    final Node<E> newNode = new Node<>(pred, e, succ);
    // 修改原succ節(jié)點(diǎn)的prev指向
    succ.prev = newNode;
    // 如果succ為頭節(jié)點(diǎn)，則設(shè)置新節(jié)點(diǎn)為頭節(jié)點(diǎn)
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    // 增加鏈表數(shù)量及修改次數(shù)
    size++;
    modCount++;
}

以上代碼中的注釋對(duì)linkLast鸥跟、linkFirst和linkBefore的實(shí)現(xiàn)進(jìn)行了詳細(xì)的說(shuō)明丢郊，其核心原理便是初始化新節(jié)點(diǎn)，并重新鏈接與原鏈表中元素的關(guān)系医咨。remove枫匾、poll和pop在刪除元素時(shí)調(diào)用了與插入操作相反的方法unlinkFirst、unlinkLast和unlink拟淮，由于實(shí)現(xiàn)原理類似干茉，這里不再贅述。

2.2.2 查找及迭代器

從上節(jié)分析可以看出很泊，LinkedList的插入/刪除操作只需要改變節(jié)點(diǎn)元素的鏈接指向角虫，因此效率較高。但其查找元素需要從頭節(jié)點(diǎn)或尾節(jié)點(diǎn)開(kāi)始對(duì)集合進(jìn)行遍歷委造，相比于ArrayList基于數(shù)組索引戳鹅，效率較低。

Node<E> node(int index) {
    if (index < (size >> 1)) {
        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通過(guò)比較index與size/2（size >> 1）判斷是從頭節(jié)點(diǎn)還是尾節(jié)點(diǎn)開(kāi)始遍歷争涌，然后通過(guò)分別獲取該節(jié)點(diǎn)的next節(jié)點(diǎn)或prev節(jié)點(diǎn)來(lái)實(shí)現(xiàn)粉楚。另外辣恋，由于LinkedList本身就同時(shí)支持前向/后向移動(dòng)亮垫，所以其iterator方法直接返回ListIterator實(shí)現(xiàn)。

public Iterator<E> iterator() {
    return listIterator();
}

三伟骨、Stack / Queue模型饮潦、實(shí)現(xiàn)及應(yīng)用

Stack和Queue在模型設(shè)計(jì)上具有相似性，其核心方法對(duì)比如下：

兩者的核心區(qū)別在于Stack是先進(jìn)后出（FILO）携狭，數(shù)據(jù)操作在一端進(jìn)行继蜡；而Queue是先進(jìn)先出（FIFO），在一端存儲(chǔ)逛腿，另一端取出（Deque繼承自Queue稀并，支持雙向存儲(chǔ)/取出）。

從上節(jié)可知单默，LinkedList是Queue（Deque）模型最常見(jiàn)的一種實(shí)現(xiàn)碘举。下面通過(guò)一個(gè)實(shí)例，說(shuō)明如何利用LinkedList的隊(duì)列特征來(lái)模擬單向循環(huán)鏈表搁廓。比如有一個(gè)任務(wù)集合引颈，任務(wù)有是否完成兩種狀態(tài)耕皮，初始狀態(tài)均為未完成，需要實(shí)現(xiàn)從第一個(gè)任務(wù)開(kāi)始的單向循環(huán)遍歷蝙场，如果當(dāng)前任務(wù)完成凌停，則不再參與遍歷，直到所有任務(wù)完成售滤。

private Task getNextUnCompleteTask(LinkedList<Task> taskList) {
    Task task = taskList.peek(); 
    if (task == null) {
        return null;
    }
    if (task.isComplete()) {
        taskList.poll();
    } else {
        taskList.offer(taskList.poll());
    }
    return taskList.peek();
}

上述代碼通過(guò)將未完成的任務(wù)重新添加至隊(duì)尾罚拟，從而在循環(huán)調(diào)用getNextUnCompleteTask方法時(shí)，實(shí)現(xiàn)對(duì)未完成任務(wù)的循環(huán)遍歷趴泌。