一文搞定雙鏈表，讓你徹底弄懂線性表的鏈?zhǔn)綄?shí)現(xiàn)
前言
前面有很詳細(xì)的講過(guò)線性表(順序表和鏈表)，當(dāng)時(shí)講的鏈表以單鏈表為主，但在實(shí)際應(yīng)用中雙鏈表有很多應(yīng)用場(chǎng)景，例如大家熟知的LinkedList。
雙鏈表與單鏈表區(qū)別
單鏈表和雙鏈表都是線性表的鏈?zhǔn)綄?shí)現(xiàn)，它們的主要區(qū)別在于節(jié)點(diǎn)結(jié)構(gòu)。單鏈表的節(jié)點(diǎn)包含數(shù)據(jù)字段 data 和一個(gè)指向下一個(gè)節(jié)點(diǎn)的指針 next，而雙鏈表的節(jié)點(diǎn)除了 data 和 next，還包含指向前一個(gè)節(jié)點(diǎn)的指針 pre。這個(gè)區(qū)別會(huì)導(dǎo)致它們?cè)诓僮魃嫌行┎町悺?/p>
單鏈表：
單鏈表的一個(gè)節(jié)點(diǎn)，有儲(chǔ)存數(shù)據(jù)的data，還有后驅(qū)節(jié)點(diǎn)next(指針)。單鏈表想要遍歷的操作都得從前節(jié)點(diǎn)—>后節(jié)點(diǎn)。
雙鏈表：
雙鏈表的一個(gè)節(jié)點(diǎn)，有存儲(chǔ)數(shù)據(jù)的data,也有后驅(qū)節(jié)點(diǎn)next(指針)，這和單鏈表是一樣的，但它還有一個(gè)前驅(qū)節(jié)點(diǎn)pre(指針)。
雙鏈表結(jié)構(gòu)的設(shè)計(jì)
上一篇講單鏈表的時(shí)候，當(dāng)時(shí)設(shè)計(jì)一個(gè)帶頭結(jié)點(diǎn)的鏈表就錯(cuò)過(guò)了不帶頭結(jié)點(diǎn)操作方式，這里雙鏈表就不帶頭結(jié)點(diǎn)設(shè)計(jì)實(shí)現(xiàn)。所以本文構(gòu)造的這個(gè)雙鏈表是：不帶頭節(jié)點(diǎn)、帶尾指針(tail)的雙向鏈表。
對(duì)于鏈表主體：
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;
}
}
}具體操作分析
對(duì)于一個(gè)鏈表主要的操作還是增刪，查詢的話不做詳細(xì)解釋。
剖析增刪其實(shí)可以發(fā)現(xiàn)大概有頭插入、編號(hào)插入、末尾插入、頭刪除、編號(hào)刪除、尾刪除幾種情況。然而這幾種關(guān)于頭尾操作的可能會(huì)遇到臨界點(diǎn)比如鏈表為空時(shí)插入刪除、或者刪除節(jié)點(diǎn)鏈表為空。
這個(gè)操作是不帶頭結(jié)點(diǎn)的操作，所以復(fù)雜性會(huì)高一些！
頭插入
頭插入?yún)^(qū)分頭為空和頭不為空兩種情況。
頭為空：這種情況head和tail都指向新節(jié)點(diǎn)。
頭不為空：
- 新節(jié)點(diǎn)的next指向head
- head的pre指向新節(jié)點(diǎn)
- head指向新節(jié)點(diǎn)(認(rèn)新節(jié)點(diǎn)為head)
尾插入
尾插需要考慮tail為null和不為null的情況。流程和頭插類似，需要考慮tail指針最后的指向。
tail為null：此時(shí)head也為null，head和tail指向新節(jié)點(diǎn)。
tail不為null：
- 新節(jié)點(diǎn)的pre指向tail
- tail的next指向新節(jié)點(diǎn)
- tail指向新節(jié)點(diǎn)
編號(hào)插入
按編號(hào)插入分情況討論，如果是頭插或者尾插就直接調(diào)用對(duì)應(yīng)的方法。普通方法的實(shí)現(xiàn)方式比較靈活，可以找到前驅(qū)節(jié)點(diǎn)和后驅(qū)節(jié)點(diǎn)，然后進(jìn)行指針插入，但是往往很多時(shí)候只用一個(gè)節(jié)點(diǎn)完成表示和相關(guān)操作，就非?？简?yàn)對(duì)表示的理解，這里假設(shè)只找到preNode節(jié)點(diǎn)。 index為0：調(diào)用頭插。
index為size：調(diào)用尾插
index在(0,size):
- 找到前驅(qū)節(jié)點(diǎn)preNode。
- 新節(jié)點(diǎn)next指向nextNode(此時(shí)用preNode.next表示)。
- nextNode(此時(shí)新節(jié)點(diǎn).next和preNode.next都可表示)的pre指向新節(jié)點(diǎn)。
- preNode的next指向新節(jié)點(diǎn)。
- 新節(jié)點(diǎn)的pre指向preNode。
頭刪除
頭刪除需要注意的就是刪除不為空時(shí)候頭刪除只和head節(jié)點(diǎn)有關(guān)
head不為null：
- head = head.next 表示頭指針指向下一個(gè)節(jié)點(diǎn)
- head 如果不為null(有可能就一個(gè)節(jié)點(diǎn))，head.pre = null 斷掉與前一個(gè)節(jié)點(diǎn)聯(lián)系 ；head如果為null，說(shuō)明之前就一個(gè)節(jié)點(diǎn)head和pre都指向第一個(gè)節(jié)點(diǎn)，此時(shí)需要設(shè)置tail為null。
尾刪除
尾刪除和頭刪除類似，考慮好tail節(jié)點(diǎn)情況
如果tail不為null：
- tail = tail.pre。
- 如果tail不為null，那么tail.next = null 表示刪除最后一個(gè)，如果tail為null，說(shuō)明之前head和tail都指向一個(gè)唯一節(jié)點(diǎn)，這時(shí)候需要head = null。
編號(hào)刪除
編號(hào)刪除和編號(hào)插入類似，先考慮是否為頭尾操作，然后再進(jìn)行正常操作。
index為0：調(diào)用頭刪
index為size：調(diào)用尾刪
index在(0,size):
- 找到待刪除節(jié)點(diǎn)current。
- 前驅(qū)節(jié)點(diǎn)(current.pre)的next指向后驅(qū)節(jié)點(diǎn)(current.next)。
- 后驅(qū)節(jié)點(diǎn)的pre指向前驅(qū)節(jié)點(diǎn)。
完整代碼
根據(jù)上面的流程，實(shí)現(xiàn)一個(gè)不帶頭結(jié)點(diǎn)的雙鏈表，在查找方面，可以根據(jù)靠頭近還是尾近，選擇從頭或者尾開(kāi)始遍歷。
代碼：
/*
* 不帶頭節(jié)點(diǎn)的
*/
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 新節(jié)點(diǎn)與后驅(qū)節(jié)點(diǎn)建立聯(lián)系
newNode.next = preNode;
preNode.next.pre = newNode;
//step 3 4 新節(jié)點(diǎn)與前驅(qū)節(jié)點(diǎn)建立聯(lián)系
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 { //此時(shí)說(shuō)明之前head和tail都指向唯一節(jié)點(diǎn)，鏈表刪除之后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<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 {//此時(shí)說(shuō)明之前head和tail都指向唯一節(jié)點(diǎn)，鏈表刪除之后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<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;
}
}
}結(jié)語(yǔ)
在插入刪除的步驟，很多人可能因?yàn)榉爆嵉倪^(guò)程而弄不明白，這個(gè)操作的寫(xiě)法可能是多樣的，但本質(zhì)操作都是一致的，要保證能成功表示節(jié)點(diǎn)并操作，這個(gè)可以畫(huà)個(gè)圖一步一步捋一下，看到其他不同版本有差距也是正常的。
還有很多人可能對(duì)一堆next.next搞不清楚，那我教你一個(gè)技巧，如果在等號(hào)右側(cè)，那么它表示一個(gè)節(jié)點(diǎn)，如果在等號(hào)左側(cè)，那么除了最后一個(gè).next其他的表示節(jié)點(diǎn)。例如node.next.next.next可以看成(node.next.next).next。
在做數(shù)據(jù)結(jié)構(gòu)與算法鏈表相關(guān)題的時(shí)候，不同題可能給不同節(jié)點(diǎn)去完成插入、刪除操作。這種情況操作時(shí)候要謹(jǐn)慎先后順序防止破壞鏈表結(jié)構(gòu)。
分享到微信 
分享到微博
