Java教程

03--链表之-->单链表

本文主要是介绍03--链表之-->单链表,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
  • 链表的物理存储结构:

 

 特点:

  1. 链表是以节点的方式来存储数据的
  2. 每个节点包含data域,next域:指向下一个节点
  3. 链表的各个节点不一定是连续的
  4. 分类:链表分带头节点的和没有头节点的,根据实际需求来决定

  •  案例:定义单链表实现三国英雄任务增删查改以及排序、遍历、合并等操作
 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 }

由于功能较为繁多,之前测试的结果忘记保存了,在此就贴一张最后一个合并两个有序的单链表,合并后依然有序的结果把~

 

这篇关于03--链表之-->单链表的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!