【数据结构(三)】双向链表（2）

---

1. 基本概念

管理单向链表的缺点分析:

    ①单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。
    ②单向链表不能自我删除，需要靠辅助节点 ，而双向链表，则可以自我删除，所以前面我们单链表删除时节点，总是找到 temp（temp 是待删除节点的前一个节点）。

双向链表示意图：

2. 管理双向链表的思路

一、遍历：

    和单向链表一样，可以向前，也可以向后查找。

二、添加：

默认添加到双向链表的最后

    ①先找到链表的最后一个节点
    ②temp.next = newHeroNode
    ③newHeroNode.pre = temp

三、修改：

思路和原理与单向链表一样

四、删除：

因为是双向链表，因此，可以实现自我删除某个节点

    ①直接找到要删除的这个节点，比如temp
    ②temp.pre.next = temp.next
    ③temp.next.pre = temp.pre

3. 代码实现

package Linkedlist;

public class DoubleLinkedListDemo {
    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();
        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;
        }

        //因为头节点不能动，每个HeroNode对象就是一个节点
        HeroNode2 temp = head.next;
        while (true) {
            //判断是否到链表最后
            if(temp == null){
                break;
            }
            //输出节点的信息
            System.out.println(temp);
            //将next后移。（不后移就成了死循环，一定小心）
            temp = temp.next;            
        }
    }    

    //添加一个节点到双向链表的最后
    public void add (HeroNode2 heroNode){

        //因为head节点不能动，因此我们需要一个辅助遍历temp
        HeroNode2 temp = head;
        //遍历链表，找到最后
        while (true) {
            //找到链表最后
            if(temp.next == null){
                break;
            }
            //如果没有找到 最后，将temp后移
            temp = temp.next;
        }
        //当退出while循环时，temp就指向了链表的最后
        //形成一个双向链表
        temp.next = heroNode;
        heroNode.pre = temp;
    }

    //修改一个节点的内容，可以看到双向链表的节点内容修改和单向链表一样
    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){//已经到链表的最后节点的next
                break;
            }
            if(temp.no == no){
            //找到的待刪除节点的前一个节点temp
            flag = true;
            break;
            }
            temp = temp.next;//temp后移
        }
        //判断flag
        if(flag){//找到
            //可以删除
            // temp.next = temp.next.next;//单向链表
            temp.pre.next = temp.next;
            //问题：如果是最后一个节点，就不需要执行下面这句话，否则出现空指针
            if (temp.next != null) {
                temp.next.pre = temp.pre;
            }
            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;//指向下一个节点，默认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 "HeroNode [no = " + no + ", name = " + name + ", nickname = " + nickname + ", next = " + next + "]";
        return "HeroNode [no = " + no + ", name = " + name + ", nickname = " + nickname + "]";
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190

运行结果：

---

课后作业：
双向链表的第二种添加方式,按照编号顺序 [示意图]按照单链表的顺序添加，稍作修改即可.