单链表应用_单链表的实际应用

作者：从前慢现在也慢 | 2024-04-15 07:50:41

踩

单链表的实际应用

一. 链表介绍

链表是以节点的方式来存储的，是链式存储。
每个节点包含data域和next域，next域指向下一个节点。
链表的各个节点不一定是连续存储。
链表分为带头节点的链表和没有头节点的链表，根据实际需求来确定。

二. 单链表应用实例的代码实现

节点

package datastructure.linkedlist.simplelinkedlist;

public class HeroNode {

    public int no;   // 编号
    public String name; // 姓名
    public HeroNode next; // 下一个节点

    public HeroNode() {
    }

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

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

}
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

链表

package datastructure.linkedlist.simplelinkedlist;

import java.util.Stack;

// 单链表
public class SimpleLinkedList {

    // 头节点
    private HeroNode head = new HeroNode(0, "");

    // 头结点的get方法
    public HeroNode getHead() {
        return head;
    }

    // 添加节点
    public void add(HeroNode heroNode) {
        HeroNode temp = head;
        // 把要添加的节点添加到链表的最后面
        while (true) {
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        temp.next = heroNode;
    }

    // 按照编号顺序添加节点
    public void addByOrder(HeroNode heroNode) {
        HeroNode temp = head;
        // 用来判断节点编号有没有重复  true为重复
        boolean flag = false;
        // 为要添加的节点找合适的位置
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.no > heroNode.no) {
                break;
            } else if (temp.next.no == heroNode.no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            System.out.println("节点编号重复！");
        } else {
            // 如果节点编号没有重复，就将要添加的节点插入到链表中合适的位置
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

    // 删除节点
    public void delete(int heroNo) {
        HeroNode temp = head;
        // 用来判断链表中有没有要删除的节点
        boolean flag = false;
        // 寻找要删除节点的前一个节点
        while (true) {
            if (temp.next == null) {
                System.out.println("没有要删除的这个节点!");
                break;
            }
            if (temp.next.no == heroNo) {
                // 链表中存在要删除的节点
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            // 把要删除节点的前一个节点的next指向要删除节点的next (断开要删除节点在链表中的连接)
            temp.next = temp.next.next;
        }
    }


    // 修改节点数据
    public void update(HeroNode heroNode) {
        HeroNode temp = head.next;
        // 用来判断有没有找到要修改的节点
        boolean flag = false;
        // 在链表中寻找要修改的节点
        while (true) {
            if (temp == null) {
                System.out.println("没有要修改的这个节点！");
                break;
            }
            if (temp.no == heroNode.no) {
                // 找到要修改的节点
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            // 修改节点的信息 （当前节点中只需要修改name）
            temp.name = heroNode.name;
        }
    }

    // 遍历所有节点
    public void allNode() {
        HeroNode temp = head.next;
        if (temp == null) {
            System.out.println("此链表为空链表！");
            return;
        }
        while (true) {
            System.out.println(temp);
            temp = temp.next;
            if (temp == null) {
                break;
            }
        }
    }

    // 返回单链表的长度
    public int getLength(HeroNode headNode) {
        if (headNode.next == null) {
            return 0;
        }
        // 记录链表的长度
        int length = 0;
        HeroNode temp = headNode.next;
        while (temp != null) {
            length ++;
            temp = temp.next;
        }
        return length;
    }

    // 获取倒数第N个节点
    public HeroNode getLastIndexNode(HeroNode headNode, int index) {
        // 如果链表为空，返回null
        if (headNode.next == null) {
            return null;
        }
        // 如果传入的index不符合要求,
        int length = getLength(headNode);
        if (index <= 0 || index > length) {
            System.out.println("获取失败！");
            return null;
        }
        // 寻找链表中倒数第index个节点并返回+
        HeroNode currentNode = headNode.next;
        for (int i = 0; i < length - index; i++) {
            currentNode = currentNode.next;
        }
        return currentNode;
    }

    // 单链表的反转
    public void reverse(HeroNode headNode) {
        // 头节点不算  如果链表中没有节点或者只有一个节点，直接return
        if (headNode.next == null || headNode.next.next == null) {
            return;
        }
        HeroNode currentNode = headNode.next;
        HeroNode nextNode = null;
        // 创建一个新的头节点 相当于创建一条新的链表
        HeroNode reverseHead = new HeroNode(0, "");
        // 不断地把旧链表的下一个节点 插入到新链表的头节点和第一个节点之间
        while (currentNode != null) {
            nextNode = currentNode.next;        // 记录当前节点的下一个节点
            currentNode.next = reverseHead.next;  // 把新链表接到当前节点的后面（也就是把当前节点接到新链表的第一个节点之前）
            reverseHead.next = currentNode;        // 当前节点接到新链表的头节点之后
            currentNode = nextNode;             // 向下进行
        }
        // 把新链表接到原来链表的头节点上
        headNode.next = reverseHead.next;
    }

    // 单链表的逆序打印的第一种方法  两次反转 遍历打印
    public void reversePrint1(HeroNode headNode) {
        // 反转链表
        reverse(headNode);
        // 打印所有节点
        allNode();
        // 把链表反转回去
        reverse(headNode);
    }

    // 单链表的逆序打印 第二种方法    利用栈stack 不改变原来单链表的数据结构
    public void reversePrint2(HeroNode headNode) {
        if (headNode.next == null) {
            return;
        }
        HeroNode current = headNode.next;
        Stack<HeroNode> stack = new Stack<>();
        // 把每个节点按链表的顺序压入栈中
        while (current != null) {
            stack.push(current);
            current = current.next;
        }
        // 逐个出栈  先进后出
        while (stack.size() > 0) {
            System.out.println(stack.pop());
        }
    }

    // 有序合并两个有序的单链表
    public void mergeTwoSimpleLinkedList(HeroNode headNode1, HeroNode headNode2) {
        // 如果有一个链表为空或者都为空，说明不用合并 直接return
        if (headNode1.next == null && headNode2.next == null) {
            return;
        } else if (headNode1.next == null) {
            return;
        } else if (headNode1.next == null) {
            return;
        }

        // 把第一个链表接到新链表上
        HeroNode current = headNode1.next;
        HeroNode nextNode = null;
        while (current != null) {
            nextNode = current.next;   // 记录下一个节点
            current.next = null;       // 把当前节点断开连接置为单独的节点
            addByOrder(current);      // 按照顺序添加到新的链表上
            current = nextNode;       // 向下进行
        }

        // 遍历第二个链表有序添加到新链表上
        current = headNode2.next;
        while (current != null) {
            nextNode = current.next;
            current.next = null;
            addByOrder(current);
            current = nextNode;
        }
    }

}
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
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236

测试类

package datastructure.linkedlist.simplelinkedlist;

public class SimpleLinkedListDemo {

    public static void main(String[] args) {
        HeroNode heroNode1 = new HeroNode(1, "宋江");
        HeroNode heroNode2 = new HeroNode(2, "卢俊义");
        HeroNode heroNode3 = new HeroNode(3, "吴用");
        HeroNode heroNode4 = new HeroNode(4, "林冲");

        /*// 创建一个单链表
        SimpleLinkedList simpleLinkedList = new SimpleLinkedList();
        // 向单链表添加节点
        simpleLinkedList.addByOrder(heroNode1);
        simpleLinkedList.addByOrder(heroNode3);
        simpleLinkedList.addByOrder(heroNode2);
        simpleLinkedList.addByOrder(heroNode4);
        // 遍历单链表
        System.out.println("原单链表是这样的:");
        simpleLinkedList.allNode();*/

        SimpleLinkedList simpleLinkedList1 = new SimpleLinkedList();
        SimpleLinkedList simpleLinkedList2 = new SimpleLinkedList();
        /*simpleLinkedList1.addByOrder(heroNode3);
        simpleLinkedList1.addByOrder(heroNode1);*/
        simpleLinkedList1.addByOrder(heroNode4);
        simpleLinkedList1.addByOrder(heroNode2);
        simpleLinkedList2.addByOrder(heroNode3);
        simpleLinkedList2.addByOrder(heroNode1);
        // 遍历第一个单链表
        System.out.println("第一个链表：");
        simpleLinkedList1.allNode();
        // 遍历第一个单链表
        System.out.println("第二个链表：");
        simpleLinkedList2.allNode();
        // 合并两个链表并遍历
        System.out.println("合并后的链表：");
        SimpleLinkedList simpleLinkedList = new SimpleLinkedList();
        simpleLinkedList.mergeTwoSimpleLinkedList(simpleLinkedList1.getHead(), simpleLinkedList2.getHead());
        simpleLinkedList.allNode();

        /*// 逆序输出链表
        System.out.println("两次反转方法，逆序打印链表。。。");
        simpleLinkedList.reversePrint1(simpleLinkedList.getHead());
        System.out.println("利用栈逆序打印链表。。。");
        simpleLinkedList.reversePrint2(simpleLinkedList.getHead());*/

        /*// 反转单链表
        simpleLinkedList.reverse(simpleLinkedList.getHead());
        // 遍历单链表
        System.out.println("反转之后的链表是这样的:");
        simpleLinkedList.allNode();*/

        /*// 遍历单链表
        simpleLinkedList.allNode();
        // 修改单链表的某个节点
        System.out.println("修改单链表之后：");
        HeroNode heroNode = new HeroNode(2, "小卢");
        simpleLinkedList.update(heroNode);
        // 遍历单链表
        simpleLinkedList.allNode();
        // 删除节点
        simpleLinkedList.delete(3);
        // simpleLinkedList.delete(2);
        // simpleLinkedList.delete(1);
        // simpleLinkedList.delete(4);
        System.out.println("删除节点后：");
        // 遍历节点
        simpleLinkedList.allNode();
        // 查看单链表的节点个数
        int length = simpleLinkedList.getLength(simpleLinkedList.getHead());
        System.out.println("这个链表的节点个数为" + length);
        // 查看倒数第N个节点
        HeroNode currentNode = simpleLinkedList.getLastIndexNode(simpleLinkedList.getHead(), 2);
        System.out.println(currentNode);*/

    }


}
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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/426613