正文

Java实现单链表SingleLinkedList增删改查及反转 逆序等

︶ㄣ米米素材网 メ
米米素材网V管理员 / 阅读
0710

单链表是链表的其中一种基本结构。一个最简单的结点结构如图所示，它是构成单链表的基本结点结构。在结点中数据域用来存储数据元素，指针域用于指向下一个具有相同结构的结点。 因为只有一个指针结点，称为单链表

节点类

可以根据需要，对节点属性进行修改。注意重写toString()方法，以便后续的输出操作。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//节点类
class Node {
    public int id;
    public String name;
    public Node next;
 
    public Node(int id, String name) {
        this.id = id;
        this.name = name;
    }
 
    @Override
    public String toString() {
        return "Node{" +
                "id=" + id +
                ", 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
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
//链表类（管理节点）
class LinkedList {
    //头节点
    Node head = new Node(0,null);
 
    //链表有效数据个数（链表长度）（头节点不计）
    public int size(){
        Node temp = head;
        int size = 0;
        while (true){
            if (temp.next == null){
                break;
            }
            size++;
            temp = temp.next;
        }
        return size;
    }
 
    //展示链表
    public void list(){
        if (head.next == null){
            System.out.println("链表为空！");
            return;
        }
        Node temp = head.next;
        while (true){
            if (temp == null){
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }
    }
 
    //增(根据id从小到大)
    public void add(Node newNode){
        Node temp = head;
        while (true){ //用来找到链表尾
            if (temp.next == null) {
                break;
            }
            if (temp.id == newNode.id){
                System.out.println("要添加的节点的id已经存在，添加失败！");
                return;
            }
            if (temp.next.id > newNode.id){
                break;
            }
            temp = temp.next;
        }
        Node node = newNode;
        newNode.next = temp.next;
        temp.next = node;
    }
 
    //删(根据id匹配删除)
    public void remove(int id){
        if (head.next == null){
            System.out.println("链表为空!");
            return;
        }
        Node temp = head;
        boolean flag = false; //用来标记是否找到对应id的节点
        while (true){
            if (temp.next == null){
                break;
            }
            if (temp.next.id == id){ //找到要删除节点的前一个节点
                flag =true;
                break;
            }
            temp = temp.next;
        }
        if (flag){
            temp.next = temp.next.next;
        }else {
            System.out.println("没有找到要删除的节点，删除失败!");
        }
    }
 
    //改（根据id匹配要修改的节点）
    public void update(int id,String name){
        if (head.next == null){
            System.out.println("链表为空！");
            return;
        }
        Node temp = head;
        boolean flag = false; //用来标记是否找到对应id的节点
        while (true){
            if (temp.next == null){
                break;
            }
            if (temp.id == id){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag){
            temp.name = name;
        }else {
            System.out.println("没有找到要修改的节点，修改失败！");
        }
    }
 
    //查（根据id匹配）
    public Node show(int id){
        if (head.next == null){
            System.out.println("链表为空！");
            return null;
        }
        Node temp = head.next;
        boolean flag = false;
        while (true){
            if (temp == null){
                break;
            }
            if (temp.id == id){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag){
            return temp;
        }else {
            System.out.println("没有找到要查找的节点，查找失败！");
            return null;
        }
    }
 
    //查找倒数第n个节点
    public Node lastShow(int n){
        Node temp = head.next;
        int size = this.size();
        if (size < n || n <= 0){
            System.out.println("查找的节点不存在！");
            return  null;
        }
        for (int i = 0; i < size - n; i++) {
            temp = temp.next;
        }
        return temp;
    }
 
    //链表反转
    public void reverse(){
        if (head.next == null || head.next.next == null){
            return;
        }
        Node reverseHead = new Node(0,null);
        Node cur = head.next; //记录当前遍历到的节点
        Node next = null; //记录当前遍历到的节点的下一个节点
        while (true){
            if (cur == null){ //确保遍历到最后一个
                break;
            }
            next = cur.next; //保存下一个节点，避免断链
            //使得反转头节点指向遍历到的当前节点，而让遍历到的当前节点指向反转头节点的下一个节点
            // 确保遍历到的当前节点始终位于反转头节点的下一个
            cur.next = reverseHead.next;
            reverseHead.next = cur;
            //遍历
            cur = next;
        }
        head.next = reverseHead.next; //最后让原头节点指向反转头节点的下一个节点，即可实现原链表的反转
    }
 
    //逆序打印
    //方法一：先反转
    //方法二：使用栈结构
    public void reversePrint(){
        if (head.next == null){
            System.out.println("链表为空！");
            return;
        }
        Stack<Node> nodes = new Stack<>();
        Node temp = head.next;
        while (true){
            if (temp == null){
                break;
            }
            nodes.push(temp);
            temp = temp.next;
        }
        while (nodes.size() > 0){
            System.out.println(nodes.pop());
        }
    }
}

测试类

?
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
import java.util.Stack;
 
/**
 * @Author: Yeman
 * @Date: 2021-10-14-12:55
 * @Description:
 */
//测试类
public class SingleLinkedListTest {
    public static void main(String[] args) {
 
        LinkedList linkedList = new LinkedList();
 
        Node node1 = new Node(1, "阿兰");
        Node node2 = new Node(2, "洛国富");
        Node node3 = new Node(3, "艾克森");
 
        //可以不按照id顺序添加
        linkedList.add(node1);
        linkedList.add(node3);
        linkedList.add(node2);
 
        linkedList.list();
 
        System.out.println(linkedList.size()); //链表长度
 
//        System.out.println(linkedList.lastShow(2)); //倒数查找
 
//        linkedList.update(2,"张玉宁"); //改
//
//        linkedList.remove(3); //删
//
//        System.out.println(linkedList.show(2)); //查
 
//        linkedList.reverse(); //链表反转
 
        linkedList.reversePrint(); //逆序打印
        
    }
}

小结

单链表的节点由具体数据域和指针域两部分组成，而带有头节点的单链表的头节点不存储具体数据，其指针域则指向链表的第一个有效节点，即非头节点的第一个节点。

当对单链表进行增删改查，逆序等操作时，要定义一个Node类型的辅助变量来遍历链表，而头节点注意要保持不动。

进行反转操作时，最后需要使得头节点指向反转后的链表的第一个节点，这是唯一一处使得头节点变动的地方。

到此这篇关于Java实现单链表SingleLinkedList增删改查及反转 逆序等的文章就介绍到这了,更多相关Java 单链表 内容请搜索米米素材网以前的文章或继续浏览下面的相关文章希望大家以后多多支持米米素材网！

原文链接：https://blog.csdn.net/m0_46653805/article/details/120771961