pQ728資訊網——每日最新資訊28at.com

前言

前面有很詳細的講過線性表(順序表和鏈表)，當時講的鏈表以單鏈表為主，但在實際應用中雙鏈表有很多應用場景，例如大家熟知的LinkedList。pQ728資訊網——每日最新資訊28at.com

雙鏈表與單鏈表區別

單鏈表和雙鏈表都是線性表的鏈式實現，它們的主要區別在于節點結構。單鏈表的節點包含數據字段 data 和一個指向下一個節點的指針 next，而雙鏈表的節點除了 data 和 next，還包含指向前一個節點的指針 pre。這個區別會導致它們在操作上有些差異。pQ728資訊網——每日最新資訊28at.com

單鏈表：

單鏈表的一個節點，有儲存數據的data，還有后驅節點next(指針)。單鏈表想要遍歷的操作都得從前節點—>后節點。pQ728資訊網——每日最新資訊28at.com

pQ728資訊網——每日最新資訊28at.com

雙鏈表：

雙鏈表的一個節點，有存儲數據的data,也有后驅節點next(指針)，這和單鏈表是一樣的，但它還有一個前驅節點pre(指針)。pQ728資訊網——每日最新資訊28at.com

pQ728資訊網——每日最新資訊28at.com

雙鏈表結構的設計

上一篇講單鏈表的時候，當時設計一個帶頭結點的鏈表就錯過了不帶頭結點操作方式，這里雙鏈表就不帶頭結點設計實現。所以本文構造的這個雙鏈表是：不帶頭節點、帶尾指針(tail)的雙向鏈表。pQ728資訊網——每日最新資訊28at.com

對于鏈表主體：

public class DoubleLinkedList<T> {    private Node<T> head;    private Node<T> 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> {        T data;        Node<T> pre;        Node<T> next;        public Node() {        }        public Node(T data) {            this.data = data;        }    }}

具體操作分析

對于一個鏈表主要的操作還是增刪，查詢的話不做詳細解釋。pQ728資訊網——每日最新資訊28at.com

剖析增刪其實可以發現大概有頭插入、編號插入、末尾插入、頭刪除、編號刪除、尾刪除幾種情況。然而這幾種關于頭尾操作的可能會遇到臨界點比如鏈表為空時插入刪除、或者刪除節點鏈表為空。pQ728資訊網——每日最新資訊28at.com

這個操作是不帶頭結點的操作，所以復雜性會高一些！pQ728資訊網——每日最新資訊28at.com

頭插入

頭插入區分頭為空和頭不為空兩種情況。pQ728資訊網——每日最新資訊28at.com

頭為空：這種情況head和tail都指向新節點。pQ728資訊網——每日最新資訊28at.com

頭不為空：pQ728資訊網——每日最新資訊28at.com

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

pQ728資訊網——每日最新資訊28at.com

尾插入

尾插需要考慮tail為null和不為null的情況。流程和頭插類似，需要考慮tail指針最后的指向。pQ728資訊網——每日最新資訊28at.com

tail為null：此時head也為null，head和tail指向新節點。pQ728資訊網——每日最新資訊28at.com

tail不為null：pQ728資訊網——每日最新資訊28at.com

• 新節點的pre指向tail
• tail的next指向新節點
• tail指向新節點

編號插入

按編號插入分情況討論，如果是頭插或者尾插就直接調用對應的方法。普通方法的實現方式比較靈活，可以找到前驅節點和后驅節點，然后進行指針插入，但是往往很多時候只用一個節點完成表示和相關操作，就非常考驗對表示的理解，這里假設只找到preNode節點。 index為0：調用頭插。pQ728資訊網——每日最新資訊28at.com

index為size：調用尾插pQ728資訊網——每日最新資訊28at.com

index在(0,size):pQ728資訊網——每日最新資訊28at.com

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

pQ728資訊網——每日最新資訊28at.com

頭刪除

頭刪除需要注意的就是刪除不為空時候頭刪除只和head節點有關pQ728資訊網——每日最新資訊28at.com

head不為null：pQ728資訊網——每日最新資訊28at.com

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

pQ728資訊網——每日最新資訊28at.com

尾刪除

尾刪除和頭刪除類似，考慮好tail節點情況pQ728資訊網——每日最新資訊28at.com

如果tail不為null：pQ728資訊網——每日最新資訊28at.com

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

編號刪除

編號刪除和編號插入類似，先考慮是否為頭尾操作，然后再進行正常操作。pQ728資訊網——每日最新資訊28at.com

index為0：調用頭刪pQ728資訊網——每日最新資訊28at.com

index為size：調用尾刪pQ728資訊網——每日最新資訊28at.com

index在(0,size):pQ728資訊網——每日最新資訊28at.com

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

pQ728資訊網——每日最新資訊28at.com

完整代碼

根據上面的流程，實現一個不帶頭結點的雙鏈表，在查找方面，可以根據靠頭近還是尾近，選擇從頭或者尾開始遍歷。pQ728資訊網——每日最新資訊28at.com

代碼：pQ728資訊網——每日最新資訊28at.com

/* * 不帶頭節點的 */package code.linearStructure;/** * @date 2023.11.02 * @author bigsai * @param <T> */public class DoubleLinkedList<T> {    private Node<T> head;    private Node<T> tail;    private int size;    public DoubleLinkedList() {        this.head = null;        this.tail = null;        size = 0;    }    // 在鏈表頭部添加元素    public void addHead(T data) {        Node<T> 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<T> newNode = new Node<>(data);            Node<T> preNode = getNode(index-1);            //step 1 2 新節點與后驅節點建立聯系            newNode.next = preNode;            preNode.next.pre = newNode;            //step 3 4 新節點與前驅節點建立聯系            preNode.next = newNode;            newNode.pre = preNode;            size++;        }    }    // 在鏈表尾部添加元素    public void addTail(T data) {        Node<T> 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都指向唯一節點，鏈表刪除之后head和tail都應該指向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<T> 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都指向唯一節點，鏈表刪除之后head和tail都應該指向null                head = null;            }            size--;        }    }    // 獲取指定位置的元素    public T get(int index) {        if (index < 0 || index >= size) {            throw new IndexOutOfBoundsException("Index is out of bounds");        }        Node<T> node = getNode(index);        return node.data;    }    // 獲取鏈表的大小    public int getSize() {        return size;    }    private Node<T> getNode(int index) {        if (index < 0 || index >= size) {            throw new IndexOutOfBoundsException("Index is out of bounds");        }        if (index < size / 2) {            Node<T> current = head;            for (int i = 0; i < index; i++) {                current = current.next;            }            return current;        } else {            Node<T> current = tail;            for (int i = size - 1; i > index; i--) {                current = current.pre;            }            return current;        }    }    private static class Node<T> {        T data;        Node<T> pre;        Node<T> next;        public Node(T data) {            this.data = data;        }    }}

結語

在插入刪除的步驟，很多人可能因為繁瑣的過程而弄不明白，這個操作的寫法可能是多樣的，但本質操作都是一致的，要保證能成功表示節點并操作，這個可以畫個圖一步一步捋一下，看到其他不同版本有差距也是正常的。pQ728資訊網——每日最新資訊28at.com

還有很多人可能對一堆next.next搞不清楚，那我教你一個技巧，如果在等號右側，那么它表示一個節點，如果在等號左側，那么除了最后一個.next其他的表示節點。例如node.next.next.next可以看成(node.next.next).next。pQ728資訊網——每日最新資訊28at.com

在做數據結構與算法鏈表相關題的時候，不同題可能給不同節點去完成插入、刪除操作。這種情況操作時候要謹慎先后順序防止破壞鏈表結構。pQ728資訊網——每日最新資訊28at.com

本文鏈接：http://www.www897cc.com/showinfo-26-17665-0.html一文搞定雙鏈表，讓你徹底弄懂線性表的鏈式實現

聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。郵件：2376512515@qq.com

上一篇： Spring Boot中實現購物車相關邏輯及示例代碼

下一篇： RabbitMQ發送和接收消息的幾種方式