一、雙向連結清單與單連結清單對比
1、單向連結清單,查找的方向隻能是一個方向,而雙向連結清單可以向前或者向後查找。
2、單向連結清單不能自我删除,需要靠輔助節點 ,而雙向連結清單,則可以自我删除。是以前面我們單連結清單删除節點時,總是找到 temp, temp 是待删除節點的前一個節點。
二、雙向連結清單圖示
三、編寫java代碼實作雙向連結清單的增删改查
3.1 應用案例
使用雙向連結清單實作 – 水浒英雄排行榜管理完成對英雄人物的增删改查操作。
3.2 編寫HeroNode2類
package point6;
/**
* @description: 定義節點類,每一個對象就是一個節點
* @author: hyr
* @time: 2020/1/19 9:44
*/
public class HeroNode2 {
public int no;
public String name;
public String nickname;
public HeroNode2 next; // 指向下一個節點,預設為null
public HeroNode2 pre; // 指向上一個節點,預設為null
// 構造器
public HeroNode2(int no, String name, String nickname) {
this.no = no;
this.name = name;
this.nickname = nickname;
}
// 為了顯示方法,重寫toString方法
@Override
public String toString() {
return "HeroNode2{" +
"no=" + no +
", name='" + name + '\'' +
", nickname='" + nickname + '\'' +
'}';
}
}
3.3 編寫DoubleLinkedList類
package point6;
/**
* @description: 建立一個雙向連結清單的類
* @author: hyr
* @time: 2020/1/19 9:48
*/
public class DoubleLinkedList {
// 先初始化一個頭節點,頭節點不要動,不存放具體的資料
private HeroNode2 head = new HeroNode2(0, "", "");
// 傳回頭節點
public HeroNode2 getHead() {
return head;
}
// 顯示連結清單
public void list() {
// 判斷連結清單是否為空
if (head.next == null) {
System.out.println("連結清單為空");
return;
}
// 因為頭節點,不能動,是以我們需要一個輔助變量來周遊
HeroNode2 temp = head.next;
while (true) {
// 判斷是否到連結清單最後
if (temp == null) {
break;
}
// 輸出節點的資訊
System.out.println(temp);
// 将temp後移
temp = temp.next;
}
}
// 添加一個節點到雙向連結清單的最後
public void add(HeroNode2 heroNode) {
// 因為頭節點不能動,是以我們需要一個輔助變量temp
HeroNode2 temp = head;
// 周遊連結清單,找到最後
while (true) {
// 找到連結清單的最後
if (temp.next == null) {
break;
}
// 如果沒有找到,将temp後移
temp = temp.next;
}
// 當退出循環時,temp就指向了連結清單的最後
// 形成一個雙向連結清單
temp.next = heroNode;
heroNode.pre = temp;
}
// 按照順序添加
public void add1(HeroNode2 heroNode) {
// 因為頭節點不能動,是以我們仍然通過一個輔助指針(變量)來幫助找到添加的位置
// 因為單連結清單,因為我們找的 temp 是位于添加位置的前一個節點,否則插入不了
HeroNode2 temp = head;
// 标志添加的編号是否存在,預設為false
boolean flag = false;
while (true) {
// 說明 temp 已經在連結清單的最後
if (temp.next == null) {
break;
}
// 位置找到,就在 temp 的後面插入
if (temp.next.no > heroNode.no) {
break;
}
// 說明希望添加的 heroNode 的編号已然存在
else if (temp.next.no == heroNode.no) {
//說明編号存在
flag = true;
break;
}
// 後移,周遊目前連結清單
temp = temp.next;
}
// 判斷 flag 的值
// 不能添加,說明編号存在
if (flag) {
System.out.printf("準備插入的英雄的編号%d已經存在了,不能加入\n", heroNode.no);
} else {
// 插入到連結清單中,temp的後面
// 這裡需要判斷一下是不是最後一個節點,需要不同的操作。
if (temp.next != null) {
heroNode.next = temp.next;
heroNode.next.pre = heroNode;
}
temp.next = heroNode;
heroNode.pre = temp;
}
}
// 修改一個節點的内容,可以看到雙向連結清單的節點内容修改和單向連結清單一樣
// 隻是節點類型修改為HeroNode2
public void update(HeroNode2 newHeroNode) {
// 判斷是否為空
if (head.next == null) {
System.out.println("連結清單為空");
return;
}
// 找到需要修改的節點,根據no編号
// 定義一個輔助變量
HeroNode2 temp = head.next;
boolean flag = false; // 表示是否找到該節點
while (true) {
if (temp == null) {
break; // 已經周遊完連結清單
}
if (temp.no == newHeroNode.no) {
// 找到
flag = true;
break;
}
temp = temp.next;
}
// 根據flag判斷是否找到要修改的節點
if (flag) {
temp.name = newHeroNode.name;
temp.nickname = newHeroNode.nickname;
} else {
System.out.printf("沒有找到編号為%d的節點,不能修改\n", newHeroNode.no);
}
}
// 從雙向連結清單中删除一個節點
// 說明
// 1、對于雙向連結清單,我們可以直接找到要删除的這個節點
// 2、找到後,自我删除即可
public void del(int no) {
// 判斷目前連結清單是否為空
if (head.next == null) {
System.out.println("連結清單為空,無法删除");
return;
}
HeroNode2 temp = head.next; // 輔助變量
boolean flag = false; // 标志是否找到待删除節點
while (true) {
if (temp == null) {
// 已經到了連結清單的最後
break;
}
if (temp.no == no) {
// 找到的待删除節點的前一個節點temp
flag = true;
break;
}
temp = temp.next; // temp後移,周遊
}
// 判斷flag
if (flag) { // 找到
// 可以删除
temp.pre.next = temp.next;
// 如果是最後一個節點,就不需要執行下面這句話,否則出現空指針
if (temp.next != null) {
temp.next.pre = temp.pre;
}
} else {
System.out.printf("要删除的%d節點不存在\n", no);
}
}
}
3.4 編寫測試類DoubleLinkedDemo
package point6;
/**
* @description: 使用雙向連結清單完成對水浒英雄榜的增删改查
* @author: hyr
* @time: 2020/1/19 18:25
*/
public class DoubleLinkedDemo {
public static void main(String[] args) {
// 先建立節點
HeroNode2 hero1 = new HeroNode2(1, "宋江", "及時雨");
HeroNode2 hero2 = new HeroNode2(2, "盧俊義", "玉麒麟");
HeroNode2 hero3 = new HeroNode2(3, "吳用", "智多星");
HeroNode2 hero4 = new HeroNode2(4, "林沖", "豹子頭");
// 建立一個雙向連結清單
DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
// // 1、按照no順序向雙向連結清單中增添資料
// doubleLinkedList.add1(hero1);
// doubleLinkedList.add1(hero2);
// doubleLinkedList.add1(hero3);
// doubleLinkedList.add1(hero4);
// // 檢視一下雙向連結清單中的資料
// System.out.println("增添完資料後的雙向連結清單為:");
// doubleLinkedList.list();
// System.out.println();
// 2、按照no順序向雙向連結清單中增添資料
doubleLinkedList.add1(hero1);
doubleLinkedList.add1(hero3);
doubleLinkedList.add1(hero2);
doubleLinkedList.add1(hero4);
// 檢視一下雙向連結清單中的資料
System.out.println("增添完資料後的雙向連結清單為:");
doubleLinkedList.list();
System.out.println();
// 3、修改
HeroNode2 newHeroNode = new HeroNode2(4,"魯智深", "花和尚");
doubleLinkedList.update(newHeroNode);
System.out.println("修改後的雙向連結清單為:");
doubleLinkedList.list();
System.out.println();
// 4、删除
doubleLinkedList.del(3);
System.out.println("删除後的連結清單情況為:");
doubleLinkedList.list();
}
}
3.5 運作結果
增添完資料後的雙向連結清單為:
HeroNode2{no=1, name='宋江', nickname='及時雨'}
HeroNode2{no=2, name='盧俊義', nickname='玉麒麟'}
HeroNode2{no=3, name='吳用', nickname='智多星'}
HeroNode2{no=4, name='林沖', nickname='豹子頭'}
修改後的雙向連結清單為:
HeroNode2{no=1, name='宋江', nickname='及時雨'}
HeroNode2{no=2, name='盧俊義', nickname='玉麒麟'}
HeroNode2{no=3, name='吳用', nickname='智多星'}
HeroNode2{no=4, name='魯智深', nickname='花和尚'}
删除後的連結清單情況為:
HeroNode2{no=1, name='宋江', nickname='及時雨'}
HeroNode2{no=2, name='盧俊義', nickname='玉麒麟'}
HeroNode2{no=4, name='魯智深', nickname='花和尚'}