java模擬實(shí)現(xiàn)雙向鏈表的方法

這篇文章主要介紹“java模擬實(shí)現(xiàn)雙向鏈表的方法”的相關(guān)知識(shí)，小編通過實(shí)際案例向大家展示操作過程，操作方法簡單快捷，實(shí)用性強(qiáng)，希望這篇“java模擬實(shí)現(xiàn)雙向鏈表的方法”文章能幫助大家解決問題。

雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個(gè)數(shù)據(jù)結(jié)點(diǎn)中都有兩個(gè)指針，分別指向直接后繼和直接前驅(qū)。所以，從雙向鏈表中的任意一個(gè)結(jié)點(diǎn)開始，都可以很方便地訪問它的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)

下圖是雙向鏈表的邏輯結(jié)構(gòu)圖，和單鏈表不同的是，雙向鏈表中每個(gè)節(jié)點(diǎn)包含兩個(gè)節(jié)點(diǎn)的指針引用，和一個(gè)數(shù)據(jù)域，這兩個(gè)節(jié)點(diǎn)分別指向前一個(gè)節(jié)點(diǎn)和后一個(gè)節(jié)點(diǎn)；

雙向鏈表的這種結(jié)構(gòu)比起單鏈表，其改進(jìn)之處正在于此，通過對(duì)前后節(jié)點(diǎn)的引用可以使得在整個(gè)鏈表中，通過給定的值，可以從前或者向后遍歷，大大提升了遍歷查詢的效率，一定程度上解決了單鏈表的性能問題，但與此同時(shí)，鏈表的存儲(chǔ)開銷也增大了，我們熟悉的linkedList，其底層就是這個(gè)原理實(shí)現(xiàn)的.

廢話不多說，相信通過上面的解釋大家已經(jīng)很明白了，下面直接上代碼，可以結(jié)合代碼和圖結(jié)構(gòu)理解雙向鏈表，

public class DoubleLinkTest<T> {

    /**
     * 內(nèi)部構(gòu)造節(jié)點(diǎn)類
     * 
     * @param <T>
     */
    private class Node<T> {
        private T data;
        private Node next; // 指向下一個(gè)節(jié)點(diǎn)的引用
        private Node prev; // 指向前一個(gè)節(jié)點(diǎn)的引用

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

    private Node<T> head; // 模擬頭結(jié)點(diǎn)
    private Node<T> last; // 模擬尾部節(jié)點(diǎn)
    private Node<T> other; // 暫定一個(gè)臨時(shí)節(jié)點(diǎn)，用作指針節(jié)點(diǎn)
    private int length;

    public void DoubleLinkTest() {
        head = new Node<T>(null);
        last = head;
        length = 0;
    }

    public void DoubleLinkTest(T data) {
        head = new Node<T>(data);
        last = head;
        length = 0;
    }

    /**
     * 鏈表是否為空
     * 
     * @return
     */
    public boolean isEmpty() {
        return length == 0;
    }

    /**
     * 普通添加，往鏈表尾部添加
     * 
     * @param data
     */
    public void add(T data) {
        if (isEmpty()) { // 鏈表為空，新創(chuàng)建一個(gè)鏈表
            head = new Node<T>(data);
            last = head;
            length++;
        } else {
            other = new Node<T>(data);
            other.prev = last;
            last.next = other; // 將新的節(jié)點(diǎn)與原來的尾部節(jié)點(diǎn)進(jìn)行結(jié)構(gòu)上的關(guān)聯(lián)
            last = other; // other將成為最后一個(gè)節(jié)點(diǎn)
            length++;
        }
    }

    /**
     * 在指定的數(shù)據(jù)后面添加數(shù)據(jù)
     * 
     * @param data
     * @param insertData
     */
    public void addAfter(T data, T insertData) {
        other = head;
        while (other != null) { // 我們假定這個(gè)head是不為空的。
            if (other.data.equals(data)) {
                Node<T> t = new Node<T>(insertData);
                t.prev = other;
                t.next = other.next;// 對(duì)新插入的數(shù)據(jù)進(jìn)行一個(gè)指向的定義
                other.next = t;

                if (t.next == null) {
                    last = t;
                }
                length++;
            }
            other = other.next;
        }
    }

    /**
     * 刪除，刪除指定的數(shù)據(jù)
     * 
     * @param data
     */
    public void remove(T data) {
        other = head;// 我們假定這個(gè)head是不為空的。
        while (other != null) {
            if (other.data.equals(data)) {
                other.prev.next = other.next;
                length--;
            }
            other = other.next;
        }

    }

    /**
     * 測試打印數(shù)據(jù)
     */
    public void printList() {
        other = head;
        for (int i = 0; i < length; i++) {
            System.out.println(other.data + "  ");
            other = other.next;
        }
    }

    public static void main(String[] args) {

        DoubleLinkTest<Integer> link = new DoubleLinkTest<Integer>();
        link.add(1);
        link.add(2);
        link.add(3);
        link.add(5);
        link.add(6);
        link.add(7);
        link.printList();

        System.out.println(" ============== ");

        System.out.println(" ==== 在3后面添加一個(gè)數(shù)據(jù)開始========== ");
        link.addAfter(3, 99);
        link.printList();

        System.out.println(" ==== 在3后面添加一個(gè)數(shù)據(jù)結(jié)束========== " + "\r\n");

        System.out.println(" ==== 移除一個(gè)數(shù)據(jù)開始========== ");
        link.remove(99);
        link.printList();
        System.out.println(" \r\n");

    }

}

運(yùn)行main函數(shù)，可以看到控制臺(tái)的打印輸出：

關(guān)于“java模擬實(shí)現(xiàn)雙向鏈表的方法”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)，可以關(guān)注億速云行業(yè)資訊頻道，小編每天都會(huì)為大家更新不同的知識(shí)點(diǎn)。