双向链表 - DoubleLinkedList_tdoublelinkedlist

作者：空白诗007 | 2024-08-11 22:28:30

踩

tdoublelinkedlist

文章目录

1 单链表的缺点
2 双向链表的操作思路
3 双向链表的代码实现
4 双向链表完整代码

1 单链表的缺点

1、单向链表查找的方向只能是一个方向，而双向链表可以向前或向后查找
2、单向链表不能自我删除，需要靠辅助节点。而双向链表则可以自我删除，所以单链表删除节点时总是要先找到temp节点，temp节点是待删除节点的前一个节点(认真体会)

2 双向链表的操作思路

2.1 添加（默认添加到链表末尾）

1、先找到双向链表的最后那个节点，如temp节点
2、修改节点的前后链接
temp.next = newNode;
newNode.pre = temp;

2.2 删除

1、双向链表可以自我删除
2、找到要删除的那个节点，如temp节点
3、修改节点的前后链接
temp.pre.next = temp.next;
temp.next.pre = temp.pre;

2.3 修改

思路与修改单链表相同

2.4 遍历

与单链表的遍历方法一样，区别是可以向前或向后查找。

3 双向链表的代码实现

3.1 添加节点到双向链表的末尾

/**
 * 添加一个节点到双向链表的最后
 * （请注意：是添加到链表的最后）
 */
public void addToEnd(HisNode hisNode) {
    // 因为head节点不能动，因此需要一个辅助变量temp
    HisNode temp = head;
    // 遍历链表，找到最后
    while (true) {
        // 找到链表的最后
        if (temp.next == null) {
            break;
        }
        // 如果没有找到最后，将temp后移
        temp = temp.next;
    }

    // 当退出while循环时，temp就指向了链表的最后
    temp.next = hisNode;
    hisNode.pre = temp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

测试添加节点功能：

	// 创建节点
	HisNode node1 = new HisNode(1, "宋江", "及时雨");
	HisNode node2 = new HisNode(2, "卢俊义", "玉麒麟");
	HisNode node3 = new HisNode(3, "吴用", "智多星");
	HisNode node4 = new HisNode(4, "林冲", "豹子头");
	// 创建一个双向链表并添加节点到末尾
	DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
	doubleLinkedList.addToEnd(node1);
	doubleLinkedList.addToEnd(node2);
	doubleLinkedList.addToEnd(node3);
	doubleLinkedList.addToEnd(node4);
	
	// 遍历双链表
	System.out.println("遍历双向链表：");
	doubleLinkedList.list();
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

添加效果：
添加节点到末尾

3.2 删除节点

/**
 * 从双向链表中删除一个节点
 * 1、对于双向链表，我们可以直接找到这个节点
 * 2、自我删除即可
 */
public void del(int no) {
    // 判断当前链表是否为空
    if (head.next == null) {
        System.out.println("链表为空，无法删除");
        return;
    }

    // 辅助变量
    HisNode temp = head.next;
    // 是否找到待删除节点的标志
    boolean flag = false;
    while (true) {
        // 已经到链表的最后
        if (temp == null) {
            break;
        }
        // 找到待删除节点的前一个节点
        if (temp.no == no) {
            flag = true;
            break;
        }
        // temp后移，遍历
        temp = temp.next;
    }

    // 判断是否找到待删除节点
    if (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);
    }
}
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

测试删除节点：

	// 删除
	doubleLinkedList.del(3);
	System.out.println("删除节点后的双向链表是：");
	doubleLinkedList.list();
1
2
3
4

删除效果：
删除节点

3.3 修改节点

/**
 * 修改一个节点的内容（与单向链表的修改方法一样）
 */
public void update(HisNode newHisNode) {
    // 判断是否为空
    if (head.next == null) {
        System.out.println("链表为空");
        return;
    }

    // 定义一个辅助变量
    HisNode temp = head.next;
    // 表示是否找到该节点
    boolean flag = false;

    while (true) {
        // 已遍历完链表
        if (temp == null) {
            break;
        }
        // 找到需要修改的节点，根据no编号修改
        if (temp.no == newHisNode.no) {
            // 找到了
            flag = true;
            break;
        }
        temp = temp.next;
    }

    // 根据flag判断是否找到要修改的节点
    if (flag) {
        temp.name = newHisNode.name;
        temp.nickName = newHisNode.nickName;
    } else {
        System.out.printf("没有找到编号 %d 的节点，不能修改\n", newHisNode.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

测试修改节点：

	// 修改
	HisNode newHisNode = new HisNode(4, "公孙胜", "入云龙");
	doubleLinkedList.update(newHisNode);
	System.out.println("修改节点后的双向链表是：");
	doubleLinkedList.list();
1
2
3
4
5

修改效果：
修改节点

3.4 遍历查找

/**
 * 遍历双向链表
 */
public void list() {
    // 判断是否为空
    if (head.next == null) {
        System.out.println("链表为空");
        return;
    }

    // 因为头节点不能动，因此需要一个辅助变量来遍历
    HisNode temp = head.next;
    while (true) {
        // 判断是否到链表最后
        if (temp == null) {
            break;
        }
        // 输出节点信息
        System.out.println(temp);
        // 将temp后移，此处一定小心
        temp = temp.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

之前的示例已展示过遍历效果了哦。

4 双向链表完整代码

任意定义一个节点类，如HisNode

4.1 HisNode.java:

package com.company.linkedlist.doubles;

/**
 * 每个HisNode对象就是一个节点
 */
public class HisNode {
    public int no;
    public String name;
    public String nickName;
    /**
     * 指向前一个节点, 默认为null
     */
    public HisNode pre;
    /**
     * 指向下一个节点,默认为null
     */
    public HisNode next;

    public HisNode(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    /**
     * 为了显示方法，我们重新toString
     */
    @Override
    public String toString() {
        return "HisNode{" +
                "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

4.2 DoubleLinkedList.java

package com.company.linkedlist.doubles;

/**
 * 创建一个双向链表的类
 */
public class DoubleLinkedList {
    /**
     * 先初始化一个头结点，头结点不要动，不存放具体的数据
     */
    private HisNode head = new HisNode(0, "", "");

    /**
     * 返回头节点
     */
    public HisNode getHead() {
        return head;
    }

    /**
     * 添加一个节点到双向链表的最后
     * （请注意：是添加到链表的最后）
     */
    public void addToEnd(HisNode hisNode) {
        // 因为head节点不能动，因此需要一个辅助变量temp
        HisNode temp = head;
        // 遍历链表，找到最后
        while (true) {
            // 找到链表的最后
            if (temp.next == null) {
                break;
            }
            // 如果没有找到最后，将temp后移
            temp = temp.next;
        }

        // 当退出while循环时，temp就指向了链表的最后
        temp.next = hisNode;
        hisNode.pre = temp;
    }

    /**
     * 从双向链表中删除一个节点
     * 1、对于双向链表，我们可以直接找到这个节点
     * 2、自我删除即可
     */
    public void del(int no) {
        // 判断当前链表是否为空
        if (head.next == null) {
            System.out.println("链表为空，无法删除");
            return;
        }

        // 辅助变量
        HisNode temp = head.next;
        // 是否找到待删除节点的标志
        boolean flag = false;
        while (true) {
            // 已经到链表的最后
            if (temp == null) {
                break;
            }
            // 找到待删除节点的前一个节点
            if (temp.no == no) {
                flag = true;
                break;
            }
            // temp后移，遍历
            temp = temp.next;
        }

        // 判断是否找到待删除节点
        if (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);
        }
    }

    /**
     * 修改一个节点的内容（与单向链表的修改方法一样）
     */
    public void update(HisNode newHisNode) {
        // 判断是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }

        // 定义一个辅助变量
        HisNode temp = head.next;
        // 表示是否找到该节点
        boolean flag = false;

        while (true) {
            // 已遍历完链表
            if (temp == null) {
                break;
            }
            // 找到需要修改的节点，根据no编号修改
            if (temp.no == newHisNode.no) {
                // 找到了
                flag = true;
                break;
            }
            temp = temp.next;
        }

        // 根据flag判断是否找到要修改的节点
        if (flag) {
            temp.name = newHisNode.name;
            temp.nickName = newHisNode.nickName;
        } else {
            System.out.printf("没有找到编号 %d 的节点，不能修改\n", newHisNode.no);
        }
    }


    /**
     * 遍历双向链表
     */
    public void list() {
        // 判断是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }

        // 因为头节点不能动，因此需要一个辅助变量来遍历
        HisNode temp = head.next;
        while (true) {
            // 判断是否到链表最后
            if (temp == null) {
                break;
            }
            // 输出节点信息
            System.out.println(temp);
            // 将temp后移，此处一定小心
            temp = temp.next;
        }
    }

}
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

4.3 DoubleLinkedListDemo.java

package com.company.linkedlist.doubles;

public class DoubleLinkedListDemo {

    public static void main(String[] args) {
        // 创建节点
        HisNode node1 = new HisNode(1, "宋江", "及时雨");
        HisNode node2 = new HisNode(2, "卢俊义", "玉麒麟");
        HisNode node3 = new HisNode(3, "吴用", "智多星");
        HisNode node4 = new HisNode(4, "林冲", "豹子头");
        // 创建一个双向链表并添加节点到末尾
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
        doubleLinkedList.addToEnd(node1);
        doubleLinkedList.addToEnd(node2);
        doubleLinkedList.addToEnd(node3);
        doubleLinkedList.addToEnd(node4);

        // 遍历双链表
        System.out.println("遍历双向链表：");
        doubleLinkedList.list();

        // 删除
        doubleLinkedList.del(3);
        System.out.println("删除节点后的双向链表是：");
        doubleLinkedList.list();

        // 修改
        HisNode newHisNode = new HisNode(4, "公孙胜", "入云龙");
        doubleLinkedList.update(newHisNode);
        System.out.println("修改节点后的双向链表是：");
        doubleLinkedList.list();
    }

}
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

微信公众号：
在这里插入图片描述

本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】