前言

前面有很詳細的講過線性表(順序表和鏈表)，當時講的鏈表以單鏈表為主，但在實際應(yīng)用中雙鏈表有很多應(yīng)用場景，例如大家熟知的LinkedList。

創(chuàng)新互聯(lián)專業(yè)為企業(yè)提供容縣網(wǎng)站建設(shè)、容縣做網(wǎng)站、容縣網(wǎng)站設(shè)計、容縣網(wǎng)站制作等企業(yè)網(wǎng)站建設(shè)、網(wǎng)頁設(shè)計與制作、容縣企業(yè)網(wǎng)站模板建站服務(wù)，10余年容縣做網(wǎng)站經(jīng)驗，不只是建網(wǎng)站，更提供有價值的思路和整體網(wǎng)絡(luò)服務(wù)。

雙鏈表與單鏈表區(qū)別

單鏈表和雙鏈表都是線性表的鏈式實現(xiàn)，它們的主要區(qū)別在于節(jié)點結(jié)構(gòu)。單鏈表的節(jié)點包含數(shù)據(jù)字段 data 和一個指向下一個節(jié)點的指針 next，而雙鏈表的節(jié)點除了 data 和 next，還包含指向前一個節(jié)點的指針 pre。這個區(qū)別會導(dǎo)致它們在操作上有些差異。

單鏈表：

單鏈表的一個節(jié)點，有儲存數(shù)據(jù)的data，還有后驅(qū)節(jié)點next(指針)。單鏈表想要遍歷的操作都得從前節(jié)點—>后節(jié)點。

雙鏈表：

雙鏈表的一個節(jié)點，有存儲數(shù)據(jù)的data,也有后驅(qū)節(jié)點next(指針)，這和單鏈表是一樣的，但它還有一個前驅(qū)節(jié)點pre(指針)。

雙鏈表結(jié)構(gòu)的設(shè)計

上一篇講單鏈表的時候，當時設(shè)計一個帶頭結(jié)點的鏈表就錯過了不帶頭結(jié)點操作方式，這里雙鏈表就不帶頭結(jié)點設(shè)計實現(xiàn)。所以本文構(gòu)造的這個雙鏈表是：不帶頭節(jié)點、帶尾指針(tail)的雙向鏈表。

對于鏈表主體：

public class DoubleLinkedList {
    private Node head;
    private Node tail;
    private int size;
    public DoubleLinkedList(){
        this.head = null;
        this.tail = null;
        size = 0;
    }
    public void addHead(T data){}
    public void add(T data, int index){}
    public void addTail(T data){}
    public void deleteHead(){}
    public void delete(int index){}
    public void deleteTail(int index){}
    public T get(int index){}
    public int getSize() {
        return size;
    }
    private static class Node {
        T data;
        Node pre;
        Node next;
        public Node() {
        }
        public Node(T data) {
            this.data = data;
        }
    }
}

具體操作分析

對于一個鏈表主要的操作還是增刪，查詢的話不做詳細解釋。

剖析增刪其實可以發(fā)現(xiàn)大概有頭插入、編號插入、末尾插入、頭刪除、編號刪除、尾刪除幾種情況。然而這幾種關(guān)于頭尾操作的可能會遇到臨界點比如鏈表為空時插入刪除、或者刪除節(jié)點鏈表為空。

這個操作是不帶頭結(jié)點的操作，所以復(fù)雜性會高一些！

頭插入

頭插入?yún)^(qū)分頭為空和頭不為空兩種情況。

頭為空：這種情況head和tail都指向新節(jié)點。

頭不為空：

• 新節(jié)點的next指向head
• head的pre指向新節(jié)點
• head指向新節(jié)點(認新節(jié)點為head)

尾插入

尾插需要考慮tail為null和不為null的情況。流程和頭插類似，需要考慮tail指針最后的指向。

tail為null：此時head也為null，head和tail指向新節(jié)點。

tail不為null：

• 新節(jié)點的pre指向tail
• tail的next指向新節(jié)點
• tail指向新節(jié)點

編號插入

按編號插入分情況討論，如果是頭插或者尾插就直接調(diào)用對應(yīng)的方法。普通方法的實現(xiàn)方式比較靈活，可以找到前驅(qū)節(jié)點和后驅(qū)節(jié)點，然后進行指針插入，但是往往很多時候只用一個節(jié)點完成表示和相關(guān)操作，就非?？简瀸Ρ硎镜睦斫猓@里假設(shè)只找到preNode節(jié)點。 index為0：調(diào)用頭插。

index為size：調(diào)用尾插

index在(0,size):

• 找到前驅(qū)節(jié)點preNode。
• 新節(jié)點next指向nextNode(此時用preNode.next表示)。
• nextNode(此時新節(jié)點.next和preNode.next都可表示)的pre指向新節(jié)點。
• preNode的next指向新節(jié)點。
• 新節(jié)點的pre指向preNode。

頭刪除

頭刪除需要注意的就是刪除不為空時候頭刪除只和head節(jié)點有關(guān)

head不為null：

• head = head.next 表示頭指針指向下一個節(jié)點
• head 如果不為null(有可能就一個節(jié)點)，head.pre = null 斷掉與前一個節(jié)點聯(lián)系 ；head如果為null，說明之前就一個節(jié)點head和pre都指向第一個節(jié)點，此時需要設(shè)置tail為null。

尾刪除

尾刪除和頭刪除類似，考慮好tail節(jié)點情況

如果tail不為null：

• tail = tail.pre。
• 如果tail不為null，那么tail.next = null 表示刪除最后一個，如果tail為null，說明之前head和tail都指向一個唯一節(jié)點，這時候需要head = null。

編號刪除

編號刪除和編號插入類似，先考慮是否為頭尾操作，然后再進行正常操作。

index為0：調(diào)用頭刪

index為size：調(diào)用尾刪

index在(0,size):

• 找到待刪除節(jié)點current。
• 前驅(qū)節(jié)點(current.pre)的next指向后驅(qū)節(jié)點(current.next)。
• 后驅(qū)節(jié)點的pre指向前驅(qū)節(jié)點。

完整代碼

根據(jù)上面的流程，實現(xiàn)一個不帶頭結(jié)點的雙鏈表，在查找方面，可以根據(jù)靠頭近還是尾近，選擇從頭或者尾開始遍歷。

代碼：

/*
 * 不帶頭節(jié)點的
 */
package code.linearStructure;

/**
 * @date 2023.11.02
 * @author bigsai
 * @param 
 */
public class DoubleLinkedList {

    private Node head;
    private Node tail;
    private int size;

    public DoubleLinkedList() {
        this.head = null;
        this.tail = null;
        size = 0;
    }

    // 在鏈表頭部添加元素
    public void addHead(T data) {
        Node newNode = new Node<>(data);
        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            newNode.next = head;
            head.pre = newNode;
            head = newNode;
        }
        size++;
    }

    // 在指定位置插入元素
    public void add(T data, int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index is out of bounds");
        }

        if (index == 0) {
            addHead(data);
        } else if (index == size) {
            addTail(data);
        } else {
            Node newNode = new Node<>(data);
            Node preNode = getNode(index-1);
            //step 1 2 新節(jié)點與后驅(qū)節(jié)點建立聯(lián)系
            newNode.next = preNode;
            preNode.next.pre = newNode;
            //step 3 4 新節(jié)點與前驅(qū)節(jié)點建立聯(lián)系
            preNode.next = newNode;
            newNode.pre = preNode;
            size++;
        }
    }

    // 在鏈表尾部添加元素
    public void addTail(T data) {
        Node newNode = new Node<>(data);
        if (tail == null) {
            head = newNode;
            tail = newNode;
        } else {
            newNode.pre = tail;
            tail.next = newNode;
            tail = newNode;
        }
        size++;
    }

    // 刪除頭部元素
    public void deleteHead() {
        if (head != null) {
            head = head.next;
            if (head != null) {
                head.pre = null;
            } else { //此時說明之前head和tail都指向唯一節(jié)點，鏈表刪除之后head和tail都應(yīng)該指向null
                tail = null;
            }
            size--;
        }
    }

    // 刪除指定位置的元素
    public void delete(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index is out of bounds");
        }

        if (index == 0) {
            deleteHead();
        } else if (index == size - 1) {
            deleteTail();
        } else {
            Node current = getNode(index);
            current.pre.next = current.next;
            current.next.pre = current.pre;
            size--;
        }
    }

    // 刪除尾部元素
    public void deleteTail() {
        if (tail != null) {
            tail = tail.pre;
            if (tail != null) {
                tail.next = null;
            } else {//此時說明之前head和tail都指向唯一節(jié)點，鏈表刪除之后head和tail都應(yīng)該指向null
                head = null;
            }
            size--;
        }
    }

    // 獲取指定位置的元素
    public T get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index is out of bounds");
        }
        Node node = getNode(index);
        return node.data;
    }

    // 獲取鏈表的大小
    public int getSize() {
        return size;
    }

    private Node getNode(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index is out of bounds");
        }

        if (index < size / 2) {
            Node current = head;
            for (int i = 0; i < index; i++) {
                current = current.next;
            }
            return current;
        } else {
            Node current = tail;
            for (int i = size - 1; i > index; i--) {
                current = current.pre;
            }
            return current;
        }
    }

    private static class Node {
        T data;
        Node pre;
        Node next;

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

結(jié)語

在插入刪除的步驟，很多人可能因為繁瑣的過程而弄不明白，這個操作的寫法可能是多樣的，但本質(zhì)操作都是一致的，要保證能成功表示節(jié)點并操作，這個可以畫個圖一步一步捋一下，看到其他不同版本有差距也是正常的。

還有很多人可能對一堆next.next搞不清楚，那我教你一個技巧，如果在等號右側(cè)，那么它表示一個節(jié)點，如果在等號左側(cè)，那么除了最后一個.next其他的表示節(jié)點。例如node.next.next.next可以看成(node.next.next).next。

在做數(shù)據(jù)結(jié)構(gòu)與算法鏈表相關(guān)題的時候，不同題可能給不同節(jié)點去完成插入、刪除操作。這種情況操作時候要謹慎先后順序防止破壞鏈表結(jié)構(gòu)。

標題名稱：一文搞定雙鏈表，讓你徹底弄懂線性表的鏈式實現(xiàn)
瀏覽路徑：http://uogjgqi.cn/article/dpehjpj.html