简介

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

image-20200826154723652

单向链表与双向链表

单向链表，查找的方向只能是一个方向，而双向链 表可以向前或者向后查找。也就是可以直接从逆序遍历

单向链表不能自我删除，需要靠辅助节点 ，而双向 链表，则可以自我删除不需要借助其他节点，而前面我们单链表删除时节点，总是找到temp,temp是待删除节点的前一个节点。

单链表删除节点

单链表删除节点

双向链表删除节点

image-20200826155922523

代码实现

这和单链表没啥大区别。不过是多了个直接前驱指针。同样是上文单链表的例子，也定义了一个单独的头节点。

节点初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 定义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 + "]";
    }

}

链表初始化

1
2
// 先初始化一个头节点, 头节点不要动, 不存放具体的数据
private HeroNode2 head = new HeroNode2(0, "", "");

排序添加节点

这里比较大小还是借助了辅助节点。用的是tem.next来进行比较

image-20200826165805702

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
//第二种方式在添加英雄时，根据排名将英雄插入到指定位置
//(如果有这个排名，则添加失败，并给出提示)
public void addByOrder(HeroNode2 heroNode) {
    //因为头节点不能动，因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置
    //因为单链表，因为我们找的temp 是位于添加位置的前一个节点，才能指向它，否则插入不了
    HeroNode2 temp = head;
    while (temp.next != null) {
        if (temp.next.no > heroNode.no) { //位置找到，就在temp的后面插入
            //插入到链表中, temp的后面
            heroNode.next = temp.next;
            temp.next.pre = heroNode;
            temp.next = heroNode;
            heroNode.pre = temp;

            return;
        } else if (temp.no == heroNode.no) {//说明希望添加的heroNode的编号已然存在
            System.out.printf("准备插入的英雄的编号 %d 已经存在了, 不能加入\n", heroNode.no);
            return;
        }
        temp = temp.next; //后移，遍历当前链表
    }
    //第一次添加,temp.next 为null
    temp.next = heroNode;
    heroNode.pre = temp;
}

删除节点

用的是在本节点进行删除操作。由于这里链表初始化了头节点，所以只要考虑尾节点这种特殊情况。

image-20200826170118842

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
// 从双向链表中删除一个节点,
// 说明
// 1 对于双向链表，我们可以直接找到要删除的这个节点
// 2 找到后，自我删除即可
public void del(int no) {
    // 判断当前链表是否为空
    if (head.next == null) {// 空链表
        System.out.println("链表为空，无法删除");
        return;
    }
    HeroNode2 temp = head.next; // 辅助变量(指针)
    while (temp!=null){
        //不能是最后一个节点
        if (temp.no==no&&temp.next!=null){
            temp.pre.next = temp.next;
            temp.next.pre = temp.pre;
            return;
        }
        //当要删除当是最后一个节点时
        if (temp.no==no&&temp.next==null){
            temp.pre.next = null;
            return;
        }
        temp  = temp.next;
    }
    System.out.println("要删除的节点不存在！");
}

完整代码

其他的基本操作例如增加，修改与单链表没有太多的区别。（其实都没啥大区别）

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

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.addByOrder(hero1);
        doubleLinkedList.addByOrder(hero4);
        doubleLinkedList.addByOrder(hero2);
        doubleLinkedList.addByOrder(hero3);

        doubleLinkedList.list();

        // 修改
        HeroNode2 newHeroNode = new HeroNode2(4, "公孙胜", "入云龙");
        doubleLinkedList.update(newHeroNode);
        System.out.println("修改后的链表情况");
        doubleLinkedList.list();

        // 删除
        doubleLinkedList.del(4);
        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 (temp != null) {
            // 输出节点的信息
            System.out.println(temp);
            // 将temp后移， 一定小心
            temp = temp.next;
        }
    }

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

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

    //第二种方式在添加英雄时，根据排名将英雄插入到指定位置
    //(如果有这个排名，则添加失败，并给出提示)
    public void addByOrder(HeroNode2 heroNode) {
        //因为头节点不能动，因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置
        //因为单链表，因为我们找的temp 是位于添加位置的前一个节点，才能指向它，否则插入不了
        HeroNode2 temp = head;
        while (temp.next != null) {
            if (temp.next.no > heroNode.no) { //位置找到，就在temp的后面插入
                //插入到链表中, temp的后面
                heroNode.next = temp.next;
                temp.next.pre = heroNode;
                temp.next = heroNode;
                heroNode.pre = temp;

                return;
            } else if (temp.no == heroNode.no) {//说明希望添加的heroNode的编号已然存在
                System.out.printf("准备插入的英雄的编号 %d 已经存在了, 不能加入\n", heroNode.no);
                return;
            }
            temp = temp.next; //后移，遍历当前链表
        }
        //第一次添加,temp.next 为null
        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;
        while (temp != null) {
            if (temp.no == newHeroNode.no) {
                temp.name = newHeroNode.name;
                temp.nickname = newHeroNode.nickname;
                return;
            }
            temp = temp.next;
        }
        System.out.println("没有找到该节点信息！");
    }

    // 从双向链表中删除一个节点,
    // 说明
    // 1 对于双向链表，我们可以直接找到要删除的这个节点
    // 2 找到后，自我删除即可
    public void del(int no) {
        // 判断当前链表是否为空
        if (head.next == null) {// 空链表
            System.out.println("链表为空，无法删除");
            return;
        }
        HeroNode2 temp = head.next; // 辅助变量(指针)
        while (temp != null) {
            //不能是最后一个节点
            if (temp.no == no && temp.next != null) {
                temp.pre.next = temp.next;
                temp.next.pre = temp.pre;
                return;
            }
            //当要删除当是最后一个节点时
            if (temp.no == no && temp.next == null) {
                temp.pre.next = null;
                return;
            }
            temp = temp.next;
        }
        System.out.println("要删除的节点不存在！");
    }
}

// 定义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 + "]";
    }

}