前言
链表是一种常见的基础数据结构，它是一种线性表，但在内存中它并不是顺序存储的，它是以链式进行存储的，每一个节点里存放的是下一个节点的“指针”。在java中的数据分为引用数据类型和基础数据类型，在java中不存在指针的概念，但是对于链表而言的指针，指的就是引用数据类型的地址。
链表和数组都是线性的数据结构，对于数组而言其长度是固定的，由于在内存中其是连续的，因此更适合做查找与遍历，而链表在内存中是并不是顺序存储的，但是由于其是通过“指针”构成的，因此在插入、删除时比较数组更为的方便。
下面的代码通过内部类并结合递归的方式来实现了一个简单的用java语言描述的链表的数据结构，下面话不多说了，来一起看看详细的介绍吧
链表数据结构的定义
首先来看一下，链表数据结构的定义，代码如下：
|
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
|
class nodemanager { private node root; // 根节点 private int currentindex = 0; // 节点的序号，每次操作从0开始 public void add(int data) {} public void delnode(int data) {} public void print() {} public boolean findnode(int data) {} public boolean updatenode(int olddata, int newdata) {} // 向索引之前插入 public void insert(int index, int data) {} // 谁拥有数据，谁提供方法 class node { private int data; private node next; // 把当前类型作为属性 public node(int data) { this.data = data; } public void setdata(int data) { this.data = data; } public int getdata() { return data; } // 添加节点 public void addnode(int data) {} // 删除节点 public void delnode(int data) {} // 输出所有节点 public void printnode() {} // 查找节点是否存在 public boolean findnode(int data) {} // 修改节点 public boolean updatenode(int olddata, int newdata) {} // 插入节点 public void insertnode(int index, int data) {} }} |
对于链表的定义来说，nodemanager类是用来管理链表操作的，而成员内部类node是用于提供链表数据与链式结构的。对于类的使用者来说，并不直接访问数据，因此操作的是nodemanager类，而内部类node提供了真正的数据管理，因此node类需要提供真正的数据操作方法，对于nodemanager类中也需要提供一套由外部来操作链表的方法。因此，在nodemanager类和node类中都提供了看似相同的方法，但实际的意义并不相同。
下面来查看nodemanager类和node类中的add()方法，代码如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
public void add(int data) { if ( root == null ) { root = new node(data); } else { root.addnode(data); }}// 添加节点public void addnode(int data) { if ( this.next == null ) { this.next = new node(data); } else { this.next.addnode(data); }} |
代码中上面的方法是nodemanager类中的方法，而下面的方法是node类中的方法。
在manager类中提供了一个root的成员变量，它用于管理链表的头节点，因此在添加节点时，会先判断root是否为空，如果为空则直接将节点由root来进行保存，如果root不为空，则通过node类中的addnode()方法来进行添加，添加到思路是找到当前链表的最后一个节点，并将新添加到节点赋值给最后一个节点的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
148
|
class nodemanager { private node root; // 根节点 private int currentindex = 0; // 节点的序号，每次操作从0开始 public void add(int data) { if ( root == null ) { root = new node(data); } else { root.addnode(data); } } public void delnode(int data) { if ( root == null ) return ; if ( root.getdata() == data ) { node tmp = root; root = root.next; tmp = null; } else { root.delnode(data); } } public void print() { if ( root != null ) { system.out.print(root.getdata() + " "); root.printnode(); system.out.println(); } } public boolean findnode(int data) { if ( root == null ) return false; if ( root.getdata() == data ) { return true; } else { return root.findnode(data); } } public boolean updatenode(int olddata, int newdata) { if ( root == null ) return false; if ( root.getdata() == olddata ) { root.setdata(newdata); return true; } else { return root.updatenode(olddata, newdata); } } // 向索引之前插入 public void insert(int index, int data) { if ( index < 0 ) return ; currentindex = 0; if ( index == currentindex ) { node newnode = new node(data); newnode.next = root; root = newnode; } else { root.insertnode(index, data); } } // 谁拥有数据，谁提供方法 class node { private int data; private node next; // 把当前类型作为属性 public node(int data) { this.data = data; } public void setdata(int data) { this.data = data; } public int getdata() { return data; } // 添加节点 public void addnode(int data) { if ( this.next == null ) { this.next = new node(data); } else { this.next.addnode(data); } } // 删除节点 public void delnode(int data) { if ( this.next != null ) { if ( this.next.getdata() == data ) { node tmp = this.next; this.next = this.next.next; tmp = null; } else { this.next.delnode(data); } } } // 输出所有节点 public void printnode() { if ( this.next != null ) { system.out.print(this.next.getdata() + " "); this.next.printnode(); } } // 查找节点是否存在 public boolean findnode(int data) { if ( this.next != null ) { if ( this.next.getdata() == data ) { return true; } else { return this.next.findnode(data); } } return false; } // 修改节点 public boolean updatenode(int olddata, int newdata) { if ( this.next != null ) { if ( this.next.getdata() == olddata ) { this.next.setdata(newdata); return true; } else { return this.next.updatenode(olddata, newdata); } } return false; } // 插入节点 public void insertnode(int index, int data) { currentindex ++; if ( index == currentindex ) { node newnode = new node(data); newnode.next = this.next; this.next = newnode; } else { this.next.insertnode(index, data); } } }} |
以上就是链表基本操作的完整代码，下面写一个调用的代码进行测试，代码如下：
|
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
|
public class linklist { public static void main(string[] args) { nodemanager nm = new nodemanager(); system.out.println("链表的添加（添加5、4、3、2、1）"); nm.add(5); nm.add(4); nm.add(3); nm.add(2); nm.add(1); nm.print(); system.out.println("链表的删除（删除3）"); nm.delnode(3); nm.print(); system.out.println("链表的查找（查找1）"); system.out.println(nm.findnode(1)); system.out.println("链表的查找（查找10）"); system.out.println(nm.findnode(10)); system.out.println("链表的更新（把1更新为10）"); nm.updatenode(1, 10); nm.print(); system.out.println("链表的插入（在第1个位置插入20）"); nm.insert(1, 20); nm.print(); system.out.println("链表的插入（在第0个位置插入30）"); nm.insert(0, 30); nm.print(); }} |
将代码编译、运行，结果如下图：
对于java中的集合类中用到了不少的数据结构的知识，等自己状态好的时候学习学习java集合类的源码。我会努力做一个初级程序员！
总结
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，如果有疑问大家可以留言交流，谢谢大家对服务器之家的支持。
原文链接：https://www.cnblogs.com/tosser/p/9064671.html
