李林超博客
首页
归档
留言
友链
动态
关于
归档
留言
友链
动态
关于
首页
Java
正文
数据结构学习--链表
Leefs
2020-01-26 PM
1306℃
0条
# 数据结构学习--链表 ### 一、链表(Linked List)介绍 链表是有序的列表,但是它在内存中是存储如下: ![03.链表01.png][1] **上图总结** (1)链表是以节点的方式来存储,是链式存储 (2)每个节点包含data域,next域:指向下一个节点。 (3)如图:发现链表的各个节点不一定是连续存储 (4)链表分带头节点的链表和没有头节点的链表,根据实际的需求来确定 **单链表(带头节点)逻辑结构示意图如下** ![03.链表02.png][2] ### 二、单链表的应用实例 使用带head头的单向链表实现 水浒英雄排行榜管理完成对英雄人物的增删改查操作。 (1)第一种方法在添加英雄时,直接添加到链表的尾部 **思路分析示意图:** ![03.链表03.png][3] **添加(创建)思路:** 1.先创建一个head头节点,作用就是表示单链表的头 2.后面我们每添加一个节点,就直接加入到链表的最后 **遍历:** 1.通过一个辅助变量遍历,帮助遍历整个链表 (2)第二种方式在添加英雄时,根据排名将英雄插入到指定位置(如果有这个排名,则添加失败,并给出提示) **思路的分析示意图:** ![03.链表04.png][4] **需要按照编号的顺序添加思路:** 1.首先找到新添加的节点的位置,是通过辅助的变量(指针),通过遍历来搞定 2.新的节点`next=temp.next` 3.将`temp.next`=新的节点 (3)修改节点功能 思路: > 1. 先找到该节点,通过遍历 > 2. `tem.name=newHeroNode.name; temp.nickname=newHeroNode.nickname` (4)删除节点 思路分析的示意图: ![03.链表05.png][5] 从单链表中删除一个节点的思路: 1. 我们先找到需要删除的这个节点的前一个节点temp 2. `temp.next=temp.next.next` 3. 被删除的节点,将不会有其它引用指向,会被垃圾回收机制回收 **代码** ```java public class SingleLinkedListDemo { public static void main(String[] args) { //先创建一个节点 HeroNode hero1 = new HeroNode(1,"宋江","及时雨"); HeroNode hero2 = new HeroNode(2,"卢俊义","玉麒麟"); HeroNode hero3 = new HeroNode(3,"吴用","智多星"); HeroNode hero4 = new HeroNode(4,"林冲","豹子头"); SingleLinkedList singleLinkedList = new SingleLinkedList(); //加入 /* singleLinkedList.add(hero1); singleLinkedList.add(hero4); singleLinkedList.add(hero2); singleLinkedList.add(hero3);*/ //加入按照编号的顺序 singleLinkedList.addByOrder(hero1); singleLinkedList.addByOrder(hero4); singleLinkedList.addByOrder(hero2); singleLinkedList.addByOrder(hero3); //显示 singleLinkedList.list(); //测试修改节点 HeroNode newHeroNode = new HeroNode(2,"小卢","玉麒麟!!"); singleLinkedList.update(newHeroNode); System.out.println("修改后的链表情况~~"); singleLinkedList.list(); //删除一个节点 singleLinkedList.del(1); singleLinkedList.del(4); System.out.println("删除后的链表情况~~"); singleLinkedList.list(); } } //定义SingleLinkedList管理我们的英雄 class SingleLinkedList{ //先初始化一个头节点,头节点不要动,不存放具体的数据 private HeroNode head = new HeroNode(0,"",""); //添加节点到单向链表 //思路:当不考虑编号顺序时 //1.找到 当前链表的最后节点 //2.将最后这个节点的next指向新的节点 public void add(HeroNode heroNode){ //因为head节点不能动,因此我们需要一个辅助遍历temp HeroNode temp = head; //遍历链表,找到最后 while(true){ //找到链表的最后 if(temp.next == null){ break; } //如果没有找到最后,将tenp后移 temp = temp.next; } //当退出while循环的时候,temp就指向了链表的最后 //将最后这个节点的next指向新的节点 temp.next = heroNode; } //第二种方式在添加英雄时,根据排名将英雄插入到指定位置 //如果有这个排名,则添加失败,并给出提示 public void addByOrder(HeroNode heroNode){ //因为头节点不能动,因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置 //因为单链表,因为我们找的temp是位于添加位置的前一个节点,否则插入不了 HeroNode temp = head; boolean flag = false;//flag标志添加的编号是否存在,默认为false while(true){ if(temp.next == null){//说明temp已经在链表的最后 break; } if(temp.next.no>heroNode.no){//位置找到,就在temp的后面插入 break; }else if(temp.next.no == heroNode.no){//说明希望添加的heroNode的编号已然存在 flag = true;//说明编号存在 break; } temp = temp.next;//后移,遍历当前链表 } //判断flag的值 if(flag){//不能添加,说明编号存在 System.out.printf("准备插入的英雄的编号%d已经存在看,不能加入\n",heroNode.no); }else{ //插入到链表中,temp的后面 heroNode.next = temp.next; temp.next=heroNode; } } //修改节点的信息,根据no编号来修改,即no编号不能改/ //说明 //1.根据newHeroNode的no来修改即可 public void update(HeroNode newHeroNode){ //判断是否为空 if(head.next == null){ System.out.println("链表为空!"); return; } //找到需要修改的节点,根据No编号 //定义一个辅助变量 HeroNode temp = head.next; boolean flag = false;//表示是否找到该节点 while(true){ if(temp == null){ break;//已经遍历完链表 } if(temp.no == newHeroNode.no){ //找到 flag = true; break; } temp = temp.next; } //根据flag判断是否找到要修改的节点 if(flag){ temp.name = newHeroNode.name; temp.nickname=newHeroNode.nickname; }else{//没有找到 System.out.printf("没有找到 编号%d的节点,不能修改\n",newHeroNode.no); } } //删除节点 //1.head不能动,因此我们需要一个temp辅助节点找到待删除节点的前一个节点 //2.说明我们在比较时,是temp.next.no和 需要删除的节点的no比较 public void del(int no){ HeroNode temp = head; boolean flag = false;//标志是否找到待删除节点的 while(true){ if(temp.next == null){//已经到链表的最后 break; } if(temp.next.no == no){ //找到的待删除节点的前一个节点temp flag = true; break; } temp=temp.next;//temp后移,遍历 } //判断flag if(flag){//找到 -- 可以删除 temp.next=temp.next.next; }else{ System.out.printf("要删除的%d节点不存在\n",no); } } //显示链表【遍历】 public void list(){ //判断链表是否为空 if(head.next == null){ System.out.println("链表为空"); return; } //因为头节点,不能动,因此我们需要一个辅助变量来遍历 HeroNode temp = head.next; while(true){ //判断是否到链表最后 if(temp == null){ break; } //输出节点的信息 System.out.println(temp); //将temp后移,一定小心 temp = temp.next; } } } //定义HeroNode,每个HeroNode对象就是一个节点 class HeroNode{ public int no; public String name; public String nickname; public HeroNode next;//指向下一个节点 //构造器 public HeroNode(int no,String name,String nickname){ this.no=no; this.name=name; this.nickname=nickname; } //为了显示方法,我们重新toString @Override public String toString(){ return "HeroNode [no="+no+",name="+name+",nickname="+nickname+"]"; } } ``` [1]: https://lilinchao.com/usr/uploads/2020/01/1387297420.png [2]: https://lilinchao.com/usr/uploads/2020/01/2529888251.png [3]: https://lilinchao.com/usr/uploads/2020/01/3343961221.png [4]: https://lilinchao.com/usr/uploads/2020/01/3182253061.png [5]: https://lilinchao.com/usr/uploads/2020/01/3143447336.png
标签:
数据结构
,
链表
非特殊说明,本博所有文章均为博主原创。
如若转载,请注明出处:
https://lilinchao.com/archives/479.html
上一篇
数据结构学习--环形队列(二)
下一篇
数据结构学习--单链表面试题
取消回复
评论啦~
提交评论
栏目分类
随笔
2
Java
326
大数据
229
工具
31
其它
25
GO
47
标签云
GET和POST
人工智能
Flume
锁
Thymeleaf
二叉树
Golang基础
DataX
nginx
Netty
国产数据库改造
Java编程思想
CentOS
Golang
Hadoop
数据结构
散列
Spark
Hbase
SpringBoot
Ubuntu
机器学习
Redis
MyBatisX
SpringCloud
Flink
Typora
持有对象
Java阻塞队列
HDFS
友情链接
申请
范明明
庄严博客
Mx
陶小桃Blog
虫洞