這將會使一篇非常長的文章，請做好戰(zhàn)斗準備

鏈表的特點是可以用任意存儲單元存儲數(shù)據(jù)元素，它不要求存儲單元連續(xù)。鏈表一般分為以下4種：

單向鏈表
雙向鏈表
單向循環(huán)鏈表
雙向循環(huán)鏈表

下面我們對這幾種鏈表一一介紹。

ADT

我們先來定義線性表的抽象數(shù)據(jù)類型。


/**
 * 線性表
 *
 * @author jaune
 * @since 1.0.0
 */
public interface List<E> {

    /**
     * 獲取列表的長度
     * @return 列表的長度
     */
    int size();

    /**
     * 判斷是否為空
     * @return true - 空； false - 非空
     */
    boolean isEmpty();

    /**
     * 添加元素
     */
    void add(E item);

    /**
     * 將元素插入到指定位置，插入位置所在的元素及其后面的元素后移。
     * @param index 元素位置，從0開始。0 ≤ index < length
     * @param item 數(shù)據(jù)元素
     * @throws IndexOutOfBoundsException 超出列表長度
     */
    void add(int index, E item);

    /**
     * 替換指定位置的元素
     * @param index 元素位置，從0開始。0 ≤ index < length
     * @param item 數(shù)據(jù)元素
     * @throws IndexOutOfBoundsException 超出列表長度
     */
    void set(int index, E item);

    /**
     * 刪除指定位置的元素，后面的元素前移。
     * @param index 元素位置
     * @return 刪除的元素
     */
    E remove(int index);

    /**
     * 獲取指定位置的元素，如果超出列表長度，拋出異常
     * @param index 元素位置
     * @throws IndexOutOfBoundsException 超出列表長度
     */
    E get(int index);

    /**
     * 清空列表
     */
    void clear();
}

由于Java是面向?qū)ο蟮模耘cC語言相比，ADT會有很大的差異。

單向鏈表

單向鏈表的數(shù)據(jù)元素包含兩個域，一個是存儲數(shù)據(jù)元素信息的數(shù)據(jù)域，一個是存儲后繼存儲位置的指針域。這兩部分組成的數(shù)據(jù)元素 $a_i$ 的存儲映像，稱為結(jié)點。指針域中存儲的信息稱做指針或鏈。由于每個結(jié)點只包含一個指針域，故又稱線性鏈表或單鏈表。

在單向鏈表中，除頭元素外，每個元素的存儲位置都包含在其直接前驅(qū)結(jié)點的信息中。

在單向鏈表中插入和刪除一個元素如下圖所示，紅色的線表示要刪除的關(guān)系。

下面我們來實現(xiàn)單向鏈表，并分析其中這些方法的時間復雜度。

單向線性表的實現(xiàn)


/**
 * 單向鏈表
 *
 * @author jaune
 * @since 1.0.0
 */
public class SingleLinkedList<E> implements List<E> {

    private Node<E> first;
    private Node<E> last;
    private int size;

    @Override
    public int size() {
        return this.size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void add(E item) {
        if (this.first == null) {
            this.first = new Node<>(item);
            this.last = this.first;
        } else {
            Node<E> node = new Node<>(item);
            this.last.next = node;
            this.last = node;
        }
        this.size ++;
    }

    @Override
    public void add(int index, E item) {
        if (index == 0) {
            this.addFirst(item);
        } else {
            // 或者前驅(qū)數(shù)據(jù)節(jié)點
            Node<E> preNode = this.getNode(index - 1);
            Node<E> node = new Node<>(item);
            node.next = preNode.next;
            preNode.next = node;
        }
        this.size++;
    }

    @Override
    public void set(int index, E item) {
        if (index == 0) {
            Node<E> node = new Node<>(item);
            node.next = this.first.next;
            // 注意清除引用關(guān)系
            this.first.next = null;
            this.first = node;
        } else {
            Node<E> preNode = this.getNode(index - 1);
            Node<E> node = new Node<>(item);
            node.next = preNode.next.next;
            preNode.next.next = null;
            preNode.next = node;
        }
    }

    @Override
    public E remove(int index) {
        Node<E> removeNode;
        if (index == 0) {
            removeNode = this.first;
            Node<E> newFirst = this.first.next;
            removeNode.next = null;
            this.first = newFirst;
        } else {
            Node<E> preNode = this.getNode(index - 1);
            removeNode = preNode.next;
            preNode.next = removeNode.next;
            removeNode.next = null;
        }
        this.size--;
        return removeNode.item;
    }

    @Override
    public E get(int index) {
        return this.getNode(index).item;
    }

    @Override
    public void clear() {
        Node<E> item = this.first;
        while (item != null) {
            Node<E> next = item.next;
            item.next = null;
            item = next;
        }
        this.first = null;
        this.last = null;
        this.size = 0;
    }

    private void addFirst(E item) {
        Node<E> node = new Node<>(item);
        node.next = this.first;
        this.first = node;
    }

    private Node<E> getNode(int index) {
        if (index >= 0 && index < this.size) {
            int p = 0;
            Node<E> item = this.first;
            while (item != null) {
                if (p == index) {
                    return item;
                } else {
                    item = item.next;
                    p++;
                }
            }
            throw new IndexOutOfBoundsException(this.outOfBoundsMsg(index));
        } else {
            throw new IndexOutOfBoundsException(this.outOfBoundsMsg(index));
        }
    }

    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+size;
    }

    private static class Node<T> {
        T item;
        Node<T> next;

        public Node(T item) {
            this.item = item;
        }
    }
}

時間復雜度分析

這里我們只考慮最壞的情況

size(): $O(1)$
isEmpty(): $O(1)$
add(E item): $O(1)$
add(int index, E item): $O(n)$
set(int index, E item): $O(n)$
remove(int index): $O(n)$
get(int index): $O(n)$

在采用數(shù)組實現(xiàn)的線性表中get(int index)方法的時間復雜度為 $O(1)$ 。java中的java.util.ArrayList就是采用數(shù)組實現(xiàn)的線性表。set(int index, E item)也是 $O(1)$ 。

add(int index, E item)和remove(int index)會涉及到數(shù)組中元素的整體后移或前移，所以在最壞情況下也是 $O(n)$ 。add(E item)會遇到數(shù)組擴容的問題，所以最快情況下是 $O(n)$ 。

雙向鏈表

在雙向鏈表的結(jié)點中有兩個指針域，其一指向直接后繼，另一指向直接前驅(qū)。

在雙向鏈表中插入和刪除時與單向表有著較大的區(qū)別，在雙向鏈表中需要同時修改兩個方向上的指針。如下圖所示。

雙向鏈表數(shù)據(jù)結(jié)點的定義如下

private static class Node<T> {
    T item;
    Node<T> next;
    Node<T> prev;

    public Node(T item) {
        this.item = item;
    }
    public Node(T item, Node<T> next, Node<T> prev) {
        this.item = item;
        this.next = next;
        this.prev = prev;
    }
}

Java中的java.util.LinkedList就是使用雙向鏈表實現(xiàn)的。具體代碼限于篇幅原因，這里就不再實現(xiàn)。只介紹兩者中的差異。

雙向鏈表與單向鏈表最大的差異之一就是節(jié)點可以從兩個方向進行遍歷，即可以從前往后也可以從后忘前。請看下面的代碼：

Node<E> node(int index) {
    // assert isElementIndex(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;
    }
}

這是JDK中的java.util.LinkedList這段代碼的意思就是當要查找的數(shù)據(jù)元素的索引小于于鏈表總長度的一半時，就從前往后遍歷，否則從后往前遍歷。

size >> 1等價于size/2。如00001101 >> 1 = 00000110即13 >> 1 = 6。這里之所以不用除法是因為位運算的計算速度更快。

JDK中有很多優(yōu)秀的算法和編程思想，讀JDK的源碼也能對自己的編程能力有很大的提升

除了節(jié)點的查找外，另外一個區(qū)別就是雙向鏈表可以實現(xiàn)自我刪除。我們在刪除單向鏈表的節(jié)點時需要找到上一個節(jié)點。而在雙向鏈表中我們只需要找到要刪除的節(jié)點即可。當然還要考慮要刪除的節(jié)點時頭結(jié)點或尾節(jié)點的問題。

    // jdk中刪除節(jié)點
    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;

        // 頭節(jié)點處理
        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }
        // 尾節(jié)點處理
        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }

        x.item = null;
        size--;
        modCount++;
        return element;
    }

其他代碼與單鏈表類似。讀者可以嘗試自己實現(xiàn)。

單向循環(huán)鏈表

單向循環(huán)鏈表的特點是最后一個結(jié)點的后繼結(jié)點指向頭結(jié)點，整體形成一個環(huán)。因此從表中任意一結(jié)點出發(fā)均可找到表中的其他結(jié)點。

如果只有一個節(jié)點，則其后繼指向自己。

image.png

單向鏈表的遍歷需要尤其的注意，因為不能再通過判斷最后一個結(jié)點的后繼結(jié)點為null來確定已達到鏈表的尾部。一種方法是記錄鏈表的長度，然后遍歷的時候遍歷到鏈表的長度后停止。另一種方法是判斷后繼結(jié)點是否為頭結(jié)點，如果是頭結(jié)點說明已達到鏈表尾部。

雙向循環(huán)鏈表

雙向循環(huán)鏈表的特點與單向循環(huán)鏈表類似，只是雙向循環(huán)鏈表可以從兩個方向遍歷結(jié)點。雙向循環(huán)鏈表的尾結(jié)點的后繼指向頭結(jié)點，頭結(jié)點的前驅(qū)指向尾結(jié)點。

如果只有一個數(shù)據(jù)元素，則其前驅(qū)和后繼都指向自己。

循環(huán)鏈表的代碼在此不再實現(xiàn)，有興趣的讀者可以自行實現(xiàn)。

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

數(shù)據(jù)結(jié)構(gòu)--鏈表

數(shù)據(jù)結(jié)構(gòu)--鏈表

ADT

單向鏈表

單向線性表的實現(xiàn)

時間復雜度分析

雙向鏈表

單向循環(huán)鏈表

雙向循環(huán)鏈表

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

數(shù)據(jù)結(jié)構(gòu)--鏈表

ADT

單向鏈表

單向線性表的實現(xiàn)

時間復雜度分析

雙向鏈表

單向循環(huán)鏈表

雙向循環(huán)鏈表

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av