- 链表的物理存储结构：
特点：
- 链表是以节点的方式来存储数据的
- 每个节点包含data域，next域：指向下一个节点
- 链表的各个节点不一定是连续的
- 分类：链表分带头节点的和没有头节点的，根据实际需求来决定
- 案例：定义单链表实现三国英雄任务增删查改以及排序、遍历、合并等操作
1 //定义一个HeroNode类，每一个HeroNode类的对象都是要给节点，包含对象的属性以及下一个节点的地址
2 class HeroNode{
3 //data域
4 public int id;
5 public String name;
6 public String address;
7
8 //创建构造器，用于初始化每个节点中的data域，即为英雄的属性赋值
9 public HeroNode(int id,String name,String address) {
10 this.id = id;
11 this.name = name;
12 this.address = address;
13 }
14
15 //next域，指向下一个节点【默认值为null，代表链表的尾部】
16 HeroNode next;
17
18 //重写toString方法，使打印节点对象的地址 --> 打印节点对象的内容【只打印每个节点对象中的data域】
19 @Override
20 public String toString() {
21 return "HeroNode [id=" + id + ", name=" + name + ", address=" + address + "]";
22 }
23
24 }
1 //定义一个SingleLinkedList类，用于管理整个单链表【带头节点的】
2 class SingleLinkedList{
3 //每个链表对象都会有一个头节点，所以先创建一个头节点对象
4 HeroNode headHeroNode = new HeroNode(0, "", "");
5
6 //1、直接向单链表的末尾追加节点
7 public void addToLast(HeroNode newHeroNode) {
8 //头节点不能动，借助辅助指针进行遍历
9 HeroNode tmp = headHeroNode;
10 while(true) {
11 if (tmp.next == null) {
12 //说明到了链表的尾部
13 tmp.next = newHeroNode;
14 break;
15 }
16 //向后移动
17 tmp = tmp.next;
18 }
19 }
20
21 //2、按照id号进行顺序【升序】排序
22 // <-- 3 -->
23 //0 1 2 4 5
24 public void addByAscend(HeroNode newHeroNode) {
25 //辅助指针进行遍历，找到带升序的节点
26 HeroNode tmp = headHeroNode;
27 while(true) {
28 if(tmp.next == null) {
29 //追加到链表的末尾
30 tmp.next = newHeroNode;
31 break;
32 }
33 //如果是降序的话此处应改为：newHeroNode.id > tmp.id
34 if (tmp.next.id > newHeroNode.id) {
35 tmp.next = newHeroNode; //与前一个节点建立连接
36 newHeroNode.next = tmp.next;
37 break;
38 }
39 else if(tmp.next.id == newHeroNode.id) {
40 System.out.println("id号为：" + newHeroNode.id + "已存在，不能插入");
41 break;
42 }
43 tmp = tmp.next;
44 }
45 }
46
47 //3、修改节点【根据id号查找与之对应的节点】
48 //1 -- 3 -- 7 -- 9
49 // 3-->5
50 public void modify(HeroNode modifyNode) {
51 if (headHeroNode.next == null) {
52 System.out.println("链表空，无可修改的数据");
53 }
54 //定义临时指针代替头节点进行遍历
55 HeroNode tmp = headHeroNode.next;
56 while(true) {
57 if (tmp == null) {
58 System.out.println("修改失败，原因：未查找到id号为：" + modifyNode.id + "的节点");
59 //记得干掉方法
60 return;
61 }
62 if (tmp.id == modifyNode.id) {
63 String oldName = tmp.name;
64 //其实所谓的修改，就是重新将遍历到的节点中的data域重新赋值
65 tmp.id = modifyNode.id;
66 tmp.name = modifyNode.name;
67 tmp.address = modifyNode.address;
68 System.out.println("英雄" + oldName + "的数据已被成功修改~~~");
69 break;
70 }
71 //继续遍历
72 tmp = tmp.next;
73 }
74 }
75
76 //4、删除节点 4
77 //1 -- 3 -- 4 -- 5 -- 7
78 public void delete(HeroNode deleteNode) {
79 if(headHeroNode.next == null) {
80 System.out.println("链表为空，无可删除的数据");
81 return;
82 }
83 //根据传入节点的id号进行遍历查询
84 //同样，头节点不能动，借助辅助指针进行链表的遍历
85 HeroNode tmp = headHeroNode;
86 while(true) {
87 if (tmp == null) {
88 System.out.println("删除失败，原因：并未查找到id号为" + deleteNode.id + "的节点");
89 return;
90 }
91 if(tmp.next.id == deleteNode.id) {
92 tmp.next = tmp.next.next;
93 System.out.println(deleteNode.name + "已被成功删除");
94 return;
95 }
96 //继续遍历
97 tmp = tmp.next;
98 }
99 }
100
101 //5、遍历单链表
102 public void list() {
103 if (headHeroNode.next == null) {
104 System.out.println("链表空，无数据");
105 return;
106 }else {
107 //借助临时指针进行遍历
108 HeroNode tmp = headHeroNode.next;
109 while(tmp != null) {
110 System.out.println(tmp);
111 tmp = tmp.next;
112 }
113 }
114 }
115
116
117
118 //返回单链表的头部
119 public HeroNode head() {
120 return headHeroNode;
121 }
122
123 //常见面试题：--> 1、求链表中有效节点的个数 【valid:有效的】
124 //需要传入一个头节点，因为每个单链表对象都不一样【长度也会有所差异】
125 public int validNodes(HeroNode head) {
126 //链表为空或者只有一个头节点
127 if (head == null || head.next == null) {
128 return 0;
129 }
130 //借助辅助指针进行遍历
131 HeroNode tmp = head.next;
132 int count = 0; //计数器
133 while(tmp != null) {
134 count++;
135 tmp = tmp.next;
136 }
137 return count;
138 }
139
140 //2、新浪面试题：求单链表中倒数第k个节点【reciprocal：倒数】
141 public HeroNode reciprocalNode(HeroNode headNode,int k) {
142 //空链表
143 if(headHeroNode.next == null) {
144 System.out.println("链表空");
145 return null;
146 }
147 //求出有效节点的个数
148 int validNodes = validNodes(headNode);
149 //k大于链表中有效数字的长度或者为非正整数
150 if (k > validNodes || k <= 0) {
151 System.out.println("k大于链表中有效数字的长度或者为非正整数");
152 return null;
153 }
154 //正常遍历情况：倒数第k个：即为有效数字的个数 - k
155 int index = validNodes - k;
156 //借助辅助指针进行遍历
157 HeroNode tmp = headNode.next;
158 //定义计数器用于记住遍历了几次
159 int count = 0;
160 while(true) {
161 if (count == index) {
162 return tmp;
163 }
164 count++;
165 tmp = tmp.next;
166 }
167 }
168
169 //3、腾讯面试题：单链表的反转
170 //思路：创建一个新的链表，每遍历到原链表中的一个节点便将其添加到新链表的头节点之后
171 public void reverse(HeroNode headNode) {
172 if (headNode.next == null || headNode.next.next == null) {
173 System.out.println("链表为空或只有一个节点，无需反转");
174 return;
175 }
176 HeroNode tmp = headNode.next; //临时指针遍历原来的链表
177 HeroNode nextNode = tmp.next; //记住下一个将要被遍历的节点
178 HeroNode reverseHead = new HeroNode(0, "", ""); //反转后的链表头
179 while(true) {
180 if(tmp == null) {
181 break;
182 }else {
183 nextNode = tmp.next; //先记住下个节点
184 tmp.next = reverseHead.next; //与链表头的下一个节点建立连接
185 reverseHead.next = tmp; //与链表头建立连接
186 tmp = nextNode; //遍历下个节点
187 }
188 }
189 //更换链表头，将旧的链表的头部指向新的链表头部后的第一个节点
190 headNode.next = reverseHead.next;
191 }
192
193 //4、百度面试题：从尾到头遍历单链表
194 //方法一：反转链表，打印【缺点：破坏原来链表的结构】
195 //方法二：使用栈，利用栈先进后出的特点，每遍历到一个接待你就将其push到栈中，最后pop所有的节点
196 public void reverseOrderPrint(HeroNode headNode) {
197 if (headNode.next == null) {
198 System.out.println("链表空，无需逆序打印");
199 return;
200 }else {
201 //定义栈容器
202 Stack<HeroNode> nodes = new Stack<>();
203 //辅助指针遍历单链表
204 HeroNode tmp = headNode.next; //0 1 2 3 5 6 9 7
205 while(tmp != null) {
206 //压栈
207 nodes.push(tmp);
208 tmp = tmp.next;
209 }
210 int size = nodes.size();
211 while(size != 0) {
212 System.out.println(nodes.pop());
213 size--;
214 }
215 }
216 }
217
218 //5、作业：合并两个有序的单链表，合并后仍然是有序的【升序】
219 //思路：依次取出两个单链表中的id值进行比较，将较小值追加到新的链表的后边
220 //如果一个链表已经到了末尾，则直接将另一个链表剩余的节点追加到新的链表的尾部
221 public static HeroNode mergeList(HeroNode head1,HeroNode head2) {
222 //如果两个单链表均为空则返回null
223 if (head1 == null && head2 == null) {
224 System.out.println("两个链表均为空，无需合并");
225 return null;
226 }else if (head1 == null) { //如果其中一个单链表为空则返回另一个单链表即可
227 return head2;
228 }else if (head2 == null) {
229 return head1;
230 }
231 //两个单链表都不为空
232 //为单链表1定义一个临时指针进行遍历，并记住下一个将要被遍历到的节点
233 HeroNode tmp1 = head1.next;
234 HeroNode next1 = null;
235 //为单链表2定义一个临时指针进行遍历，并记住下一个将要被遍历到的节点
236 HeroNode tmp2 = head2.next;
237 HeroNode next2 = null;
238 //定义合并后的链表头
239 HeroNode mergeHead = new HeroNode(0, "", "");
240 //同样，新的链表的头节点不能动，借助辅助指针遍历新的链表，用于借助链表遍历到的位置，便于追加节点
241 HeroNode tmpMerge = mergeHead; //此处不能为gergeHead.next,因为新链表的next为空,否则会出现空指针异常
242 while(tmp1 != null && tmp2 != null) {
243 if (tmp1.id < tmp2.id) { //轮到链表1
244 //记住链表1中下一个将要被遍历到的节点
245 next1 = tmp1.next;
246 //链接到新的链表的上
247 tmp1.next = tmpMerge.next;
248 tmpMerge.next = tmp1;
249 //临时指针向后移
250 tmpMerge = tmpMerge.next;
251 //继续遍历
252 tmp1 = next1;
253 }
254 else { //轮到链表2
255 next2 = tmp2.next;
256 tmp2.next = tmpMerge.next;
257 tmpMerge.next = tmp2;
258 //临时指针向后移
259 tmpMerge = tmpMerge.next;
260 tmp2 = next2;
261 }
262 if (tmp1 == null) {
263 //如果链表1为空，则将链表2中剩余的所有节点都链接到新的链表上
264 tmpMerge.next = tmp2;
265 break;
266 }else if(tmp2 == null) {
267 tmpMerge.next = tmp1;
268 break;
269 }
270 }
271 return mergeHead;
272 }
273
274 }
测试类中的部分测试数据：
1 public class SingleLinkedListDemo2 {
2
3 public static void main(String[] args) {
4 System.out.println("测试单链表添加数据:");
5 HeroNode hero1 = new HeroNode(1, "曹操", "魏国");
6 HeroNode hero4 = new HeroNode(4, "刘备", "蜀国");
7 HeroNode hero7 = new HeroNode(7, "诸葛亮", "蜀国");
8 HeroNode hero9 = new HeroNode(9, "孙权", "吴国");
9 SingleLinkedList heroList = new SingleLinkedList();
10 heroList.addToLast(hero1);
11 heroList.addToLast(hero4);
12 heroList.addToLast(hero7);
13 heroList.addToLast(hero9);
14
15 // heroList.addByAscend(hero1);
16 // heroList.addByAscend(hero2);
17 // heroList.addByAscend(hero3);
18 // heroList.addByAscend(hero4);
19 heroList.list();
20
21 // System.out.println("修改后：--->");
22 // HeroNode hero5 = new HeroNode(1, "夏侯惇", "魏国");
23 // heroList.modify(hero5);
24
25 // System.out.println("删除后：--->");
26 // HeroNode delNode = new HeroNode(1, "曹操", "魏国");
27 // heroList.delete(delNode);
28
29 // System.out.println("有效节点个数为：" + heroList.validNodes(heroList.head()));
30
31 // System.out.println("倒数第k个节点：-->");
32 // System.out.println(heroList.reciprocalNode(heroList.headHeroNode, 5));
33
34 // System.out.println("反转链表后：");
35 // heroList.reverse(heroList.head());
36
37 // System.out.println("逆序打印链表：");
38 // heroList.reverseOrderPrint(heroList.head());
39 // heroList.list();
40 System.out.println("-----------------------------");
41 HeroNode hero2 = new HeroNode(2, "夏侯惇", "魏国");
42 HeroNode hero5 = new HeroNode(5, "马超", "蜀国");
43 HeroNode hero8 = new HeroNode(8, "周瑜", "吴国");
44 HeroNode hero10 = new HeroNode(10, "张飞", "蜀国");
45 SingleLinkedList heroList2 = new SingleLinkedList();
46 heroList2.addToLast(hero2);
47 heroList2.addToLast(hero5);
48 heroList2.addToLast(hero8);
49 heroList2.addToLast(hero10);
50 heroList2.list();
51 System.out.println("合并两个有序的单链表:-->");
52 HeroNode newHeroHead = SingleLinkedList.mergeList(heroList.head(), heroList2.head());
53 SingleLinkedList mergeList = new SingleLinkedList();
54 mergeList.addToLast(newHeroHead.next);//注：去掉头节点插入【不然会出现两个头节点】
55 System.out.println("------------------");
56 mergeList.list();
57 }
58
59 }
由于功能较为繁多，之前测试的结果忘记保存了，在此就贴一张最后一个合并两个有序的单链表，合并后依然有序的结果把~
原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/279461.html