目錄
一.雙向鏈表的概念
二.雙向鏈表的數(shù)據(jù)結構
三.雙向鏈表的實現(xiàn)
節(jié)點的插入
頭插法
尾插法
任意位置插入
節(jié)點的刪除
刪除鏈表中第一次出現(xiàn)的目標節(jié)點
刪除鏈表中所有與關鍵字相同的節(jié)點
節(jié)點的查找
鏈表的清空
鏈表的長度
四.模擬實現(xiàn)鏈表的完整代碼
前言：在上一篇文章中，我們認識了鏈表中的單鏈表，而本篇文章則是介紹線鏈表中的另一個結構雙向鏈表，有興趣的朋友們可以點擊了解：圖文詳解單鏈表的各種操作
一.雙向鏈表的概念
雙向鏈表（Doubly Linked List）是一種數(shù)據(jù)結構，它與單向鏈表相似，但每個節(jié)點不僅包含指向下一個節(jié)點的指針，還包含指向上一個節(jié)點的指針。
雙向鏈表的每個節(jié)點通常包含以下兩個指針：
- prev：指向上一個節(jié)點
- next：指向下一個節(jié)點
通過這兩個指針，可以在雙向鏈表中沿著兩個方向遍歷。
相比于單向鏈表，雙向鏈表能夠更方便地進行插入和刪除操作。因為每個節(jié)點包含指向前一個節(jié)點的指針，所以在刪除或插入一個節(jié)點時，只需要修改該節(jié)點前后節(jié)點的指針即可。而在單向鏈表中，則需要在刪除或插入節(jié)點時，找到該節(jié)點的前一個節(jié)點，以便進行指針修改，顯得相對麻煩。
二.雙向鏈表的數(shù)據(jù)結構
雙向倆表有倆個指針，分別存放前驅(qū)節(jié)點的地址和后繼節(jié)點的地址，如圖所示
對于其中每一個節(jié)點，我們可以如下存儲
public class Node{
public int data;
public Node prev;
public Node next;
//構造方法，給每個節(jié)點賦值
public Node(int data) {
this.data = data;
}
}而我們的鏈表則是需要將所有的節(jié)點封裝起來，放進一個數(shù)據(jù)結構中，因此將剛才定義的節(jié)點類作為鏈表的內(nèi)部類即可，而鏈表又需要實現(xiàn)各種各樣的功能，我們可以將所有的鏈表的功能抽象出一個接口，然后通過鏈表去具體的實現(xiàn)那些功能
public class MyLinkList implements Ilst{
//節(jié)點的數(shù)據(jù)結構
public class Node{
public int data;
public Node prev;
public Node next;
//構造方法
public Node(int data) {
this.data = data;
}
}
public Node head;//頭節(jié)點
public Node last;//尾節(jié)點
}接口：
public interface Ilst {
//頭插法
public void addFirst(int data);
//尾插法
public void addLast(int data);
//任意位置插入
public void addIndex(int index,int data);
//查找是否包含關鍵字key是否在鏈表當中
public boolean contains(int key);
//刪除第一次出現(xiàn)關鍵字為key的節(jié)點
public void remove(int key);
//刪除所有值為key的節(jié)點
public void removeAllKey(int key);
//得到鏈表的長度
public int size();
//展示鏈表
public void display();
//清空鏈表
public void clear();
}
三.雙向鏈表的實現(xiàn)
節(jié)點的插入
節(jié)點的插入分為三種情況，一是在鏈表最前面進行插入也就是頭插法，二是在鏈表末尾進行插入，也就是尾插法，三是在鏈表中間位置插入
頭插法
如圖所示有一個新的節(jié)點，我們需要將其插入頭節(jié)點的位置
第一步：將目標節(jié)點的后繼指針指向頭節(jié)點位置的節(jié)點
第二步，將頭節(jié)點的前驅(qū)指針指向目標節(jié)點
在使用代碼具體實現(xiàn)的時候，需要對異常做出判斷，假如頭節(jié)點為空，也就是鏈表里面沒有節(jié)點的時候，我們就直接讓我們要新加的節(jié)點既是頭節(jié)點，又是尾節(jié)點；在做出異常處理后，我們就可以按照剛才圖示的過程進行頭插了，但是需要注意的是，在完成頭插后需要更新頭節(jié)點的位置?
@Override//頭插法
public void addFirst(int data) {
Node newNode = new Node(data);
if (head == null){
head = newNode;
last = newNode;
}else {
newNode.next = head;
head.prev = newNode;
//更新頭節(jié)點
head = newNode;
}
}尾插法
如圖所示有一個新的節(jié)點，我們需要將其插入鏈表的末尾
第一步：將目標節(jié)點的前驅(qū)指針指向尾部節(jié)點
第二步：將尾部節(jié)點的后繼指針指向目標節(jié)點
在使用代碼具體實現(xiàn)的時候，需要對異常做出判斷，假如頭節(jié)點為空，也就是鏈表里面沒有節(jié)點的時候，我們就直接讓我們要新加的節(jié)點既是頭節(jié)點，又是尾節(jié)點；在做出異常處理后，我們就可以按照剛才圖示的過程進行尾插了，但是需要注意的是，在完成頭插后需要更新尾部節(jié)點的位置
@Override//尾插法
public void addLast(int data) {
Node newNode = new Node(data);
if (head == null){
head = newNode;
last = newNode;
}else {
newNode.prev = last;
last.next = newNode;
//更新尾部節(jié)點
last = newNode;
}
}任意位置插入
如圖，假如想讓新節(jié)點插入第三個節(jié)點的位置，該如何做呢？
第一步：先將目標節(jié)點的后繼指針指向要插入節(jié)點的后一個節(jié)點
?
第二步：將目標節(jié)點的前驅(qū)指針指向插入節(jié)點?
?
第三步：將插入節(jié)點的后繼指針指向目標節(jié)點
第四步：將插入節(jié)點的后一個節(jié)點的前驅(qū)指針指向目標節(jié)點?
對于節(jié)點的插入，最難的一點便是這4個步驟的順序，順序不是一成不變也不必死背，只需要記住一個原則——保證鏈表不斷，在這個原則的基礎上進行操作就不會出現(xiàn)問題了，也就是說在我們插入的時候，不要因為先去處理前面的節(jié)點導致找不到后面的節(jié)點就可以，因此我們在對鏈表進行插入操作的時候，一般都習慣先對后面的節(jié)點進行操作。
對于輸入的位置我們要進行合法性的判斷，如果在最前面就剛好使用頭插法，如果是最后面就使用尾插法，之后遍歷找到我們要插入的位置
@Override//任意位置插入
public void addIndex(int index, int data) {
//對輸入位置進行判斷
if (index < 0 || index > size()) {
System.out.println("輸入位置不合法");
return;
}
if (index == 0) {
//如果插入位置在最前面就使用頭插
addFirst(data);
return;
}
if (index == size()) {//這里的size方法在后文中有定義
//如果插入位置在最后面就使用尾插
addLast(data);
return;
}
//在中間插入
Node newNode = new Node(data);
//找到要插入的位置
Node cur = head;
while (index != 1) {
cur = cur.next;
index--;
}
//將新節(jié)點插入到cur之前
newNode.next = cur;
newNode.prev = cur.prev;
cur.prev.next = newNode;
cur.prev = newNode;
// //將新節(jié)點插入到cur之后
// newNode.next = cur.next;
// newNode.prev = cur;
// cur.next = newNode;
// newNode.next.prev = newNode;
}節(jié)點的刪除
對于節(jié)點的刪除我們分為倆種，一種的將單個節(jié)點進行刪除，一種是將所有與目標值相同的節(jié)點進行刪除
刪除鏈表中第一次出現(xiàn)的目標節(jié)點
如圖，我們假定我們要刪除鏈表中第三個節(jié)點
第一步：將刪除節(jié)點的前驅(qū)節(jié)點的后繼指針指向刪除節(jié)點的后繼節(jié)點?
第二步：將刪除節(jié)點的后繼節(jié)點的前驅(qū)指針指向刪除節(jié)點的前驅(qū)節(jié)點
對于上面?zhèn)z個過程只是倆行代碼就可以解決：
cur.next.prev = cur.prev;
cur.prev.next = cur.next;刪除的過程非常簡單，但是要找到正確的位置并不是一件容易事，就算找到后也要進行合法性的判斷，具體代碼如下：
@Override//刪除第一次出現(xiàn)關鍵字為key的節(jié)點
public void remove(int key) {
Node cur = head;
while (cur != null) {
if(cur.data == key) {
if(cur == head) {
head = head.next;
if(head != null) {
head.prev = null;
}else {
//只有一個節(jié)點 且是需要刪除的節(jié)點
last = null;
}
}else {
if(cur.next != null) {
//刪除中間節(jié)點
cur.next.prev = cur.prev;
cur.prev.next = cur.next;
}else {
//刪除尾巴節(jié)點
cur.prev.next = cur.next;
last = last.prev;
}
}
return;
}
cur = cur.next;
}
}刪除鏈表中所有與關鍵字相同的節(jié)點
對于和剛才唯一不同的點就是我們在刪除一個點后不需要停止返回，繼續(xù)遍歷整個鏈表進行刪除即可，這里就不再贅述
@Override//刪除所有值為key的節(jié)點
public void removeAllKey(int key) {
Node cur = head;
while (cur != null) {
if(cur.data == key) {
if(cur == head) {
head = head.next;
if(head != null) {
head.prev = null;
}else {
//只有一個節(jié)點 且是需要刪除的節(jié)點
last = null;
}
}else {
if(cur.next != null) {
//刪除中間節(jié)點
cur.next.prev = cur.prev;
cur.prev.next = cur.next;
}else {
//刪除尾巴節(jié)點
cur.prev.next = cur.next;
last = last.prev;
}
}
}
cur = cur.next;
}
}節(jié)點的查找
對于節(jié)點的查找，只需要挨個遍歷判斷就可以
@Override//查找是否包含關鍵字key是否在鏈表當中
public boolean contains(int key) {
Node cur = head;
while (cur != null){
if (cur.data == key){
return true;
}else {
cur = cur.next;
}
}
return false;
}鏈表的清空
清空鏈表需要對每個節(jié)點進行清空，因此我們遍歷整個鏈表然后進行賦值為空就可以，但是有一點需要注意，我們在刪除每一個節(jié)點的后繼指針之前得先做臨時的記錄，不然我們刪除了一個節(jié)點的后繼指針后就無法通過它訪問后一個節(jié)點了
@Override//清空鏈表
public void clear() {
Node cur = head;
while (cur != null){
Node tempNode = cur.next;//記錄當前節(jié)點的下一個節(jié)點的地址
cur.prev = null;
cur.next = null;
cur = tempNode;
}
this.head = null;
this.last = null;
}鏈表的長度
求鏈表的長度只需要使用計數(shù)器遍歷累加就可以文章來源：http://www.zghlxwxcb.cn/news/detail-753995.html
@Override//得到單鏈表的長度
public int size() {
int count = 0;
Node cur = head;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}四.模擬實現(xiàn)鏈表的完整代碼
package MyLinkList;
public class MyLinkList implements Ilst {
public class Node {
public int data;
public Node prev;
public Node next;
//構造方法
public Node(int data) {
this.data = data;
}
}
public Node head;
public Node last;
@Override//頭插法
public void addFirst(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
last = newNode;
} else {
newNode.next = head;
head.prev = newNode;
//更新頭節(jié)點
head = newNode;
}
}
@Override//尾插法
public void addLast(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
last = newNode;
} else {
newNode.prev = last;
last.next = newNode;
//更新尾部節(jié)點
last = newNode;
}
}
@Override//任意位置插入
public void addIndex(int index, int data) {
//對輸入位置進行判斷
if (index < 0 || index > size()) {
System.out.println("輸入位置不合法");
return;
}
if (index == 0) {
//如果插入位置在最前面就使用頭插
addFirst(data);
return;
}
if (index == size()) {
//如果插入位置在最后面就使用尾插
addLast(data);
return;
}
//在中間插入
Node newNode = new Node(data);
//找到要插入的位置
Node cur = head;
while (index != 1) {
cur = cur.next;
index--;
}
//將新節(jié)點插入到cur之前
newNode.next = cur;
newNode.prev = cur.prev;
cur.prev.next = newNode;
cur.prev = newNode;
// //將新節(jié)點插入到cur之后
// newNode.next = cur.next;
// newNode.prev = cur;
// cur.next = newNode;
// newNode.next.prev = newNode;
}
@Override//查找是否包含關鍵字key是否在鏈表當中
public boolean contains(int key) {
Node cur = head;
while (cur != null){
if (cur.data == key){
return true;
}else {
cur = cur.next;
}
}
return false;
}
@Override//刪除第一次出現(xiàn)關鍵字為key的節(jié)點
public void remove(int key) {
Node cur = head;
while (cur != null) {
if(cur.data == key) {
if(cur == head) {
head = head.next;
if(head != null) {
head.prev = null;
}else {
//只有一個節(jié)點 且是需要刪除的節(jié)點
last = null;
}
}else {
if(cur.next != null) {
//刪除中間節(jié)點
cur.next.prev = cur.prev;
cur.prev.next = cur.next;
}else {
//刪除尾巴節(jié)點
cur.prev.next = cur.next;
last = last.prev;
}
}
return;
}
cur = cur.next;
}
}
@Override//刪除所有值為key的節(jié)點
public void removeAllKey(int key) {
Node cur = head;
while (cur != null) {
if(cur.data == key) {
if(cur == head) {
head = head.next;
if(head != null) {
head.prev = null;
}else {
//只有一個節(jié)點 且是需要刪除的節(jié)點
last = null;
}
}else {
if(cur.next != null) {
//刪除中間節(jié)點
cur.next.prev = cur.prev;
cur.prev.next = cur.next;
}else {
//刪除尾巴節(jié)點
cur.prev.next = cur.next;
last = last.prev;
}
}
}
cur = cur.next;
}
}
@Override//得到單鏈表的長度
public int size() {
int count = 0;
Node cur = head;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
@Override//展示鏈表
public void display() {
Node cur = head;
while (cur != null) {
System.out.print(cur.data + " ");
cur = cur.next;
}
System.out.println();
}
@Override//清空鏈表
public void clear() {
Node cur = head;
while (cur != null){
Node tempNode = cur.next;
cur.prev = null;
cur.next = null;
cur = tempNode;
}
this.head = null;
this.last = null;
}
}
?
?本次的分享就到此為止了，希望我的分享能給您帶來幫助，也歡迎大家三連支持，你們的點贊就是博主更新最大的動力！
如有不同意見，歡迎評論區(qū)積極討論交流，讓我們一起學習進步！
有相關問題也可以私信博主，評論區(qū)和私信都會認真查看的，我們下次再見文章來源地址http://www.zghlxwxcb.cn/news/detail-753995.html
到了這里，關于數(shù)據(jù)結構：圖文詳解雙向鏈表的各種操作（頭插法，尾插法，任意位置插入，查詢節(jié)點，刪除節(jié)點，求鏈表的長度... ...）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
