04--链表之-->双链表

本文主要是介绍04--链表之-->双链表，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

单链表管理的缺点：

1. 单项链表，查找的方向只能是一个方向，而双链表可以向前或者向后查找节点
2. 单链表不能自我删除，而要借助辅助节点进行遍历，而双链表则可以自我删除，之前用单链表删除节点时总会使用到辅助变量tmp，其实tmp就是待删除节点的前一个节点

单链表实现效果图：

 删除：

 1 //定义HeroNode类，每一个HeroNode对象都是双链表的一个节点
 2 class HeroNode{
 3     //节点-->数据域
 4     public int id;
 5     public String name;
 6     public String address;
 7     
 8     //创建构造器，用于初始化节点中的数据域
 9     public HeroNode(int id,String name,String address) {
10         this.id = id;
11         this.name = name;
12         this.address = address;
13     }
14     
15     //节点-->指针域
16     HeroNode pre; //指向前一个节点
17     HeroNode next; //指向下一个节点
18 
19     //重写toString()方法，有打印对象的地址 --> 打印对象的内容
20     @Override
21     public String toString() {
22         return "HeroNode [id=" + id + ", name=" + name + ", address=" + address + "]";
23     }
24 
25 }

  1 //创建DoubleLinkedkList类，用于管理生成的每一个链表 【带头节点的】
  2 class DoubleLinkedList{
  3     //创建头节点
  4     HeroNode head = new HeroNode(0, "", "");
  5     
  6     //返回头节点
  7     public HeroNode head() {
  8         return head;
  9     }
 10     
 11     //直接向链表最后追加数据
 12     public void addToLast(HeroNode newNode) {
 13         if (newNode == null) {
 14             System.out.println("添加失败，要添加的节点不能为空");
 15             return;
 16         }else {
 17             //借助辅助指针进行遍历
 18             HeroNode tmp = head;
 19             while(true) {
 20                 if (tmp.next == null) {
 21                     //说明找到了末尾
 22                     tmp.next = newNode; 
 23                     newNode.pre = tmp; 
 24                     break;
 25                 }
 26                 //继续遍历
 27                 tmp = tmp.next;
 28             }
 29         }
 30     }
 31     
 32     //根据传入节点的id值删除数据
 33     public void deleteNodeById(int id) {
 34         if (head.next == null) {
 35             System.out.println("链表空，无可删除数据");
 36             return;
 37         }else {
 38             HeroNode tmp = head.next;
 39             boolean flag = false;
 40             while(tmp != null) {
 41                 if (tmp.id == id) {
 42                     flag = true;
 43                     tmp.pre.next = tmp.next; //当前节点的上一个节点指向当前节点的下一个节点
 44                     //需要考虑到双链表中最后一个节点的删除情况
 45                     if (tmp.next != null) {
 46                         tmp.next.pre = tmp.pre;
 47                     }
 48                     break;
 49                 }
 50                 tmp = tmp.next;
 51             }
 52             if (flag) {
 53                 System.out.println("删除成功");
 54             }else {
 55                 System.out.println("删除失败：未查找到与改id值相等的英雄");
 56             }
 57         }
 58     }
 59     
 60     //根据传入节点的id 值查找对应的节点并将其修改
 61     public void modify(HeroNode modifyNode) {
 62         if (head.next == null) {
 63             System.out.println("链表空，无可修改的数据");
 64             return;
 65         }else {
 66             HeroNode tmp = head.next;
 67             while(tmp != null) {
 68                 if (tmp.id == modifyNode.id) {
 69                     //修改：重新为节点中的data域赋值
 70                     tmp.id = modifyNode.id;
 71                     tmp.name = modifyNode.name;
 72                     tmp.address = modifyNode.address;
 73                     return;
 74                 }
 75                 //继续遍历
 76                 tmp = tmp.next;
 77             }
 78         }
 79     }
 80     
 81     //作业：双来表按照顺序添加节点【此处示例为升序】 ascending : 上升的
 82     public void addByAscending(HeroNode newNode) {
 83         if (newNode == null) {
 84             System.out.println("添加失败：添加的节点不能为空");
 85             return;
 86         }
 87         //特殊添加1：直接添加在头节点后面
 88         if (head.next == null) {
 89             newNode.pre = head;
 90             head.next = newNode;
 91             return;
 92         }
 93         //链表中插入
 94         HeroNode tmp = head.next;
 95 
 96         while(true) {
 97             //需要考虑到最后一个节点的插入情况
 98             if (tmp.next == null) {
 99                 tmp.next = newNode;
100                 newNode.pre = tmp;
101                 return;
102             }
103             if (newNode.id > tmp.id && newNode.id < tmp.next.id) {
104                 // 与原tmp后节点建立链接
105                 tmp.next.pre = newNode;
106                 newNode.next = tmp.next;
107                 
108                 //与原tmp前节点建立链接
109                 tmp.next = newNode;
110                 newNode.pre = tmp;
111                 return;
112             }
113             else if (newNode.id == tmp.id) {
114                 System.out.println("插入失败，改id值已经存在");
115                 return;
116             }
117             //继续遍历 
118             tmp = tmp.next;
119         }
120     }
121     
122     //遍历双链表
123     public void list() {
124         if (head.next == null) {
125             System.out.println("链表尾空，无需遍历");
126             return;
127         }else {
128             //借助辅助节点进行遍历
129             HeroNode tmp = head.next;
130             while(tmp != null) {
131                 System.out.println(tmp);
132                 //指针后移
133                 tmp = tmp.next;
134             }
135         }
136     }
137 }

测试类：

 1 public class DoubleLinkedListDemo {
 2 
 3     public static void main(String[] args) {
 4         System.out.println("测试双链表添加数据【直接奥链表末端】-->");
 5         HeroNode hero1 = new HeroNode(1, "吕布", "无归属");
 6         HeroNode hero3 = new HeroNode(3, "典韦", "魏国");
 7         HeroNode hero2 = new HeroNode(2, "赵云", "蜀国");
 8         HeroNode hero5 = new HeroNode(5, "马超", "西凉");
 9         HeroNode beDeletedHero = new HeroNode(15, "徐元直", "蜀国"); //改数据用于后期做删除测试
10         HeroNode beModifiedHero = new HeroNode(4, "关云长", "蜀国"); //用于后期被修改
11         DoubleLinkedList heroList = new DoubleLinkedList();
12         heroList.addToLast(hero1);
13         heroList.addToLast(hero3);
14         heroList.addToLast(hero2);
15         heroList.addToLast(hero5);
16         heroList.addToLast(beDeletedHero);
17         heroList.addToLast(beModifiedHero);
18         heroList.list();
19         
20         System.out.println("删除数据 -->");
21         heroList.deleteNodeById(15);
22         heroList.list();
23         
24         System.out.println("修改数据：-->");
25         heroList.modify(new HeroNode(4, "关羽", "蜀国"));
26         heroList.list();
27         
28         System.out.println("升序添加-->");
29         HeroNode h1 = new HeroNode(1, "吕布", "无归属");
30         HeroNode h3 = new HeroNode(3, "典韦", "魏国");
31         HeroNode h2 = new HeroNode(2, "赵云", "蜀国");
32         HeroNode h5 = new HeroNode(5, "关羽", "蜀国");
33         HeroNode h4 = new HeroNode(4, "马超", "西凉");
34         DoubleLinkedList ascendingList = new DoubleLinkedList();
35         ascendingList.addByAscending(h1);
36         ascendingList.addByAscending(h3);
37         ascendingList.addByAscending(h2);
38         ascendingList.addByAscending(h5);
39         ascendingList.addByAscending(h4);
40         ascendingList.list();
41     }
42 
43 }

示例代码运行结果：

这篇关于04--链表之-->双链表的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！