Java数据结构：双向链表的实现_双向链表java实现

---

---

1 双向链表

1.1 双向链表介绍

相较单链表，双向链表除了data与next域，还多了一个pre域用于表示每个节点的前一个元素。这样做给双向链表带来了很多优势：

1. 单向链表查找的方向只能是一个方向，而双向链表可以向前或者向后查找；
2. 单链表如果想要实现删除操作，需要找到待删除节点的前一个节点。而双向链表可以实现自我删除。

双向链表结构示意图如下：

1.2 双向链表实现思路

与单链表实现类似，交集部分不再赘述，详情可参考文章：Java数据结构：单链表的实现与面试题汇总

遍历：
与单链表遍历方式一样，同时，双向链表可以支持向前和向后两种查找方式

添加：

• 添加到末尾

  • 先找到双向链表最后一个节点
  • cur.next = newNode；
  • newNode.pre = cur；

• 按照no顺序添加

  • 先判断该链表是否为空，如果为空则直接添加
  • 如果不为空则继续处理
  • 根据no遍历链表，找到合适的位置
  • newNode.next = cur.next;
  • cur.next = newNode;
  • newNode.pre = cur;

修改操作与单链表实现步骤一致

删除操作：

• 双向链表可以实现自我删除
• 直接找到待删除的节点
• cur.pre.next = cur.next;
• cur.next.pre = cur.pre;
• 需要特别注意是否为最后一个元素，如果为最后一个元素，cur.next为null，此时使用cur.next.pre会出现空指针异常，所以，如果为最后一个元素，则该步骤可以省略，cur.next为null即可。

以删除红色的2号节点为例：

---

2 双向链表实现完整代码

2.1 节点类 Student.java

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * 学生类节点
 */
public class StudentNode {
    public String no; //学号
    public String name; //姓名
    public int age; //年龄
    public StudentNode pre; //指向前一个节点
    public StudentNode next; //指向下一个节点

    //构造器
    public StudentNode(String no, String name, int age ){
        this.no = no;
        this.name = name;
        this.age = age;
    }

    //为了显示方便
    @Override
    public String toString() {
        return "StudentNode{" +
                "no='" + no + '\'' +
                ", name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}
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

2.2 双向链表实现类 StudentDoubleLinkedList.java

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * 学生双向链表的具体实现
 */
public class StudentDoubleLinkedList {
    //定义头节点
    private StudentNode head = new StudentNode("", "", 0);

    //获取头节点
    public StudentNode getHead(){
        return head;
    }

    //遍历双向链表的方法
    public void showList(){
        //判断链表是否为空
        if (head.next == null){
            System.out.println("当前链表为空");
            return;
        }
        //遍历 使用辅助指针
        StudentNode temp = head;
        while (temp != null){
            //更新指针
            temp = temp.next;
            if (temp.next == null){
                System.out.print(temp);
                break;
            }
            System.out.print(temp + "--->");
        }
    }

    //添加节点的方法
    //添加到尾部
    public void add(StudentNode newNode){
        //先找到最后一个节点
        StudentNode cur = head;
        while (true){
            //到达最后退出循环
            if (cur.next == null){
                break;
            }
            //更新指针
            cur = cur.next;
        }
        //添加操作
        newNode.next = cur.next; //也可以省略，因为恒为null
        cur.next = newNode;
        newNode.pre = cur;
    }

    //添加节点的方法
    //根据学号顺序添加
    public void addByOrder(StudentNode newNode){
        //如果当前链表为空，则直接添加
        if (head.next == null){
            head.next = newNode;
            newNode.pre = head;
            return;
        }
        //按照学号找到对应位置
        StudentNode cur = head;
        boolean flag = false; //标识待添加的no是否存在
        while (true){
            if (cur.next == null){
                //已经到达链表的尾部
                break;
            } else if (Integer.parseInt(cur.next.no) == Integer.parseInt(newNode.no)){
                //已经存在
                flag = true;
                break;
            }else if (Integer.parseInt(cur.next.no) > Integer.parseInt(newNode.no)){
                //位置找到
                break;
            }
            cur = cur.next;
        }
        if (flag){
            System.out.println("当前no已经存在，无法添加!");
        }else {
            //添加操作
            newNode.next = cur.next;
            cur.next = newNode;
            newNode.pre = cur;
        }
    }

    //根据no学号修改学生信息
    public void update(StudentNode studentNode){
        if (head.next == null){
            System.out.println("当前链表为空, 无法修改");
            return;
        }
        StudentNode temp = head.next;
        boolean flag = false; //表示是否找到节点
        while (true){
            if (temp == null){
                break;
            }
            if (temp.no == studentNode.no){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag){
            temp.name = studentNode.name;
            temp.age = studentNode.age;
            System.out.println("更新成功!");
        }else {
            System.out.println("没有找到");
        }
    }

    //从双向链表中删除节点
    public void delete(String no){
        //直接找到对应no的节点直接删除
        StudentNode cur = head.next;
        boolean flag = false; //标记是否找到
        while (true){
            if (cur == null){
                break;
            }
            if (cur.no.equals(no)){
                flag = true; //找到了
                break;
            }
            cur = cur.next;
        }
        if (flag){
            //删除操作
            //注意考虑最后一个节点后一个为空的情况
            if (cur.next != null) {
                cur.next.pre = cur.pre;
            }
            cur.pre.next = cur.next;
            System.out.println("删除成功!");
        }else {
            System.out.println( no + "节点不存在，无法删除！");
        }
    }
}
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

2.3 测试类 StudentDoubleLinkedListDemo.java

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * 双向链表测试类
 */
public class DoubleLinkedListDemo {
    public static void main(String[] args) {
        StudentDoubleLinkedList doubleLinkedList = new StudentDoubleLinkedList();
        doubleLinkedList.addByOrder(new StudentNode("1", "黄小黄", 20));
        doubleLinkedList.addByOrder(new StudentNode("3", "懒羊羊", 20));
        doubleLinkedList.addByOrder(new StudentNode("2", "沸羊羊", 25));
        doubleLinkedList.addByOrder(new StudentNode("4", "美羊羊", 15));
        System.out.println("遍历:");
        doubleLinkedList.showList();

        //测试更新方法
        System.out.println("\n更新编号为4的信息后:");
        doubleLinkedList.update(new StudentNode("4", "祢豆子", 14));
        doubleLinkedList.showList();

        //测试删除方法
        System.out.println("\n删除第一个和最后一个:");
        doubleLinkedList.delete("1");
        doubleLinkedList.delete("4");
        doubleLinkedList.showList();
    }
}
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

2.4 结果

遍历:
StudentNode{no='1', name='黄小黄', age=20}--->StudentNode{no='2', name='沸羊羊', age=25}--->StudentNode{no='3', name='懒羊羊', age=20}--->StudentNode{no='4', name='美羊羊', age=15}
更新编号为4的信息后:
更新成功!
StudentNode{no='1', name='黄小黄', age=20}--->StudentNode{no='2', name='沸羊羊', age=25}--->StudentNode{no='3', name='懒羊羊', age=20}--->StudentNode{no='4', name='祢豆子', age=14}
删除第一个和最后一个:
删除成功!
删除成功!
StudentNode{no='2', name='沸羊羊', age=25}--->StudentNode{no='3', name='懒羊羊', age=20}
Process finished with exit code 0
1
2
3
4
5
6
7
8
9
10

---

3 双向链表小结

• 单向链表查找的方向只能为一个方向，双向链表解决了这个缺点，可以实现双向查找；
• 单链表进行删除操作必须找到待删除元素的前一个元素，才能完成删除操作。而双向链表就简单多了，只需要找到待删除的节点，进行自我删除；
• 本节介绍了双向链表的遍历、添加、按顺序添加、更新、删除方法的实现，可以尝试像单链表篇一样，尝试求有效节点数量，以及如何逆序输出双向链表加强练习！

---

写在最后

 本文被 Java数据结构 收录点击订阅专栏 ， 持续更新中。
 创作不易，如果你有任何问题，欢迎私信，感谢您的支持！