雙向鏈表應用實例

使用帶head頭的雙向鏈表實現 –水滸英雄排行榜

管理單向鏈表的缺點分析:

單向鏈表，查找的方向只能是一個方向，而雙向鏈表可以向前或者向后查找。

單向鏈表不能自我刪除，需要靠輔助節點 ，而雙向鏈表，則可以自我刪除，所以前面我們單鏈表刪除時節點，總是找到temp,temp是待刪除節點的前一個節點(認真體會).

示意圖幫助理解刪除

課堂作業和思路提示:雙向鏈表的第二種添加方式,按照編號順序 [示意圖] 按照單鏈表的順序添加，稍作修改即可.

分析 雙向鏈表的遍歷，添加，修改，刪除的操作思路 ===》代碼實現

1. 遍歷 方和 單鏈表一樣，只是可以向前，也可以向后查找 2) 添加 (默認添加到雙向鏈表的最后)

- (1) 先找到雙向鏈表的最后這個節點
- (2) temp.next = newHeroNode
- (3) newHeroNode.pre = temp;

3. 修改 思路和 原來的單向鏈表一樣. 4) 刪除

- (1) 因為是雙向鏈表，因此，我們可以實現自我刪除某個節點
- (2) 直接找到要刪除的這個節點，比如temp
- (3)  temp.pre.next = temp.next
- (4) temp.next.pre = temp.pre;

代碼實現

package com.atguigu.linkedlist;/*** ClassName:  <br/>* Description:  <br/>* Date: 2021-02-19 14:32 <br/>* @project data_algorithm* @package com.atguigu.linkedlist*/
public class DoubleLinkedListDemo {public static void main(String[] args) {// 測試System.out.println("雙向鏈表的測試");// 先創建節點HeroNode2 hero1 = new HeroNode2(1, "宋江", "及時雨");HeroNode2 hero2 = new HeroNode2(2, "盧俊義", "玉麒麟");HeroNode2 hero3 = new HeroNode2(3, "吳用", "智多星");HeroNode2 hero4 = new HeroNode2(4, "林沖", "豹子頭");// 創建一個雙向鏈表DoubleLinkedList doubleLinkedList = new DoubleLinkedList();doubleLinkedList.add(hero1);doubleLinkedList.add(hero2);doubleLinkedList.add(hero3);doubleLinkedList.add(hero4);doubleLinkedList.list();// 修改HeroNode2 newHeroNode = new HeroNode2(4, "公孫勝", "入云龍");doubleLinkedList.update(newHeroNode);System.out.println("修改后的鏈表情況");doubleLinkedList.list();// 刪除doubleLinkedList.del(3);System.out.println("刪除后的鏈表情況~~");doubleLinkedList.list();}}// 創建一個雙向鏈表的類
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) {// 因為head節點不能動，因此我們需要一個輔助遍歷 tempHeroNode2 temp = head;// 遍歷鏈表，找到最后while (true) {// 找到鏈表的最后if (temp.next == null) {//break;}// 如果沒有找到最后, 將將temp后移temp = temp.next;}// 當退出while循環時，temp就指向了鏈表的最后// 形成一個雙向鏈表temp.next = heroNode;heroNode.pre = temp;}// 修改一個節點的內容, 可以看到雙向鏈表的節點內容修改和單向鏈表一樣// 只是 節點類型改成 HeroNode2public 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) {// 找到的待刪除節點的前一個節點tempflag = true;break;}temp = temp.next; // temp后移，遍歷}// 判斷flagif (flag) { // 找到// 可以刪除// temp.next = temp.next.next;[單向鏈表]temp.pre.next = temp.next;// 這里我們的代碼有問題?// 如果是最后一個節點，就不需要執行下面這句話，否則出現空指針if (temp.next != null) {temp.next.pre = temp.pre;}} else {System.out.printf("要刪除的 %d 節點不存在\n", no);}}}// 定義HeroNode2 ， 每個HeroNode 對象就是一個節點
class HeroNode2 {public int no;public String name;public String nickname;public HeroNode2 next; // 指向下一個節點, 默認為nullpublic HeroNode2 pre; // 指向前一個節點, 默認為null// 構造器public HeroNode2(int no, String name, String nickname) {this.no = no;this.name = name;this.nickname = nickname;}// 為了顯示方法，我們重新toString@Overridepublic String toString() {return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";}}

原文鏈接:傳送門