链表简介
因为学过C语言版的数据结构，这里很好理解
链表是以节点的方式来存储,是链式存储
每个节点包含data域, next域:指向下一个节点.
如图:发现链表的各个节点不一定是连续存储.
链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定单链表(带头结点)逻辑结构示意图如下
我博客前面有更新大话数据结构，这块讲的比较详细，有需求的可以去看看
简单的链表
package com.caq.linkedlist; /** * * @Date 2021/12/8 17:11 * @Version 1.0 */ public class SingleLinkedListDemo { public static void main(String[] args) { //进行测试 HeroNode hero1 = new HeroNode(1, "宋江", "及时雨"); HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟"); HeroNode hero3 = new HeroNode(3, "吴用", "智多星"); //创建要给链表 SingleLinkedList singleLinkedList = new SingleLinkedList(); //加入 singleLinkedList.add(hero1); singleLinkedList.add(hero2); singleLinkedList.add(hero3); //显示 singleLinkedList.list(); } } //定义SingleLinkedList 管理英雄 class SingleLinkedList { //先初始化一个头结点，头结点不要动，不存放具体的数据 private HeroNode head = new HeroNode(0,"",""); //添加节点到单向链表 public void add(HeroNode heroNode){ HeroNode temp = head; //遍历链表，找到最后 while (true){ //找到链表的最后 if (temp.next == null){ break; } //如果没有找到最后，就讲temp后移 /**这里的next是对象变量 * 什么是对象变量呢？在Java核心卷1中97页提出，对象变量引用新构造的对象 * 我们学过C语言可以知道，这个对象变量就类似与指针指向我们的对象 * 再去看上面的程序temp.next == null代表head结点后面没有新的结点了 * 因为next变量（可以理解为c语言的指针）在堆中没有指向任何数据，因此可以判断是尾结点 */ temp = temp.next;//将我们的这个临时对象变量后移指向头接点的下一个元素 } //当退出while循环时，temp就指向了链表的最后 //将最后这个节点的next指向了新的节点 temp.next = heroNode;//把这个对象变量指向heroNode也就是我们的新节点 } //显示链表[遍历] public void list(){ if (head.next == null){ System.out.println("链表为空"); return; } //因为头结点，不能动，我们需要一个辅助变量来遍历 /** 这个遍历的时候容易出错，我们自己学习的时候可以多用debug来进行学习 我们看67行，我们搞了一个辅助变量temp因为头结点不能动，我们让temp = 头结点的下一个对象 好，我们进入while循环，直接打印temp的信息，因为我们上边重写了toString方法可以直接打印 之后！我们将temp在后移，此时的temp已经是头结点的下一个对象了，之后在后移这样就可以实现 打印链表中的所有对象了！ */ HeroNode temp = head.next; while (true){ //判断是否到链表最后 if (temp == null){ break; } //输出节点信息 System.out.println(temp); //将next后移，一定小心 temp = temp.next; } } } //定义HereNode,每一个HeroNode对象就是一个节点 class HeroNode { public int number; public String name; public String nickname; public HeroNode next; //指向下一个节点 //构造器 public HeroNode(int number, String name, String nickname) { this.number = number; this.name = name; this.nickname = nickname; } @Override public String toString() { return "HeroNode{" + "number=" + number + ", name='" + name + '\'' + ", nickname='" + nickname + '\'' + " }"; } }
顺序链表
package com.caq.linkedlist; /** * * @Date 2021/12/8 17:11 * @Version 1.0 */ public class SingleLinkedListDemo { public static void main(String[] args) { //进行测试 HeroNode hero1 = new HeroNode(1, "宋江", "及时雨"); HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟"); HeroNode hero3 = new HeroNode(3, "吴用", "智多星"); //创建要给链表 SingleLinkedList singleLinkedList = new SingleLinkedList(); //按照编号的顺序 // singleLinkedList.add(hero1); // singleLinkedList.add(hero2); // singleLinkedList.add(hero3); //不按照编号的顺序 singleLinkedList.addByOrder(hero1); singleLinkedList.addByOrder(hero3); singleLinkedList.addByOrder(hero2); singleLinkedList.addByOrder(hero2); //显示 singleLinkedList.list(); } } //定义SingleLinkedList 管理英雄 class SingleLinkedList { //先初始化一个头结点，头结点不要动，不存放具体的数据 private HeroNode head = new HeroNode(0,"",""); //添加节点到单向链表 public void add(HeroNode heroNode){ HeroNode temp = head; //遍历链表，找到最后 while (true){ //找到链表的最后 if (temp.next == null){ break; } //如果没有找到最后，就讲temp后移 /**这里的next是对象变量 * 什么是对象变量呢？在Java核心卷1中97页提出，对象变量引用新构造的对象 * 我们学过C语言可以知道，这个对象变量就类似与指针指向我们的对象 * 再去看上面的程序temp.next == null代表head结点后面没有新的结点了 * 因为next变量（可以理解为c语言的指针）在堆中没有指向任何数据，因此可以判断是尾结点 */ temp = temp.next;//将我们的这个临时对象变量后移指向头接点的下一个元素 } //当退出while循环时，temp就指向了链表的最后 //将最后这个节点的next指向了新的节点 temp.next = heroNode;//把这个对象变量指向heroNode也就是我们的新节点 } //第二种方式添加，我们按顺序来添加根据排名 public void addByOrder(HeroNode heroNode){ //头结点不动，仍然通过temp来操作 HeroNode temp = head; boolean flag = false; while (true){ //这个判断的是head后面没有元素，直接添加 if (temp.next == null){ break; } //有元素的时候，比较number大小， if (temp.next.number > heroNode.number){//位置找到，就在temp的后面插入（temp.next就是temp的后面） break; }else if (temp.next.number == heroNode.number){ flag = true; //说明编号存在 break; } temp = temp.next; } //判断flag的值 if (flag){ System.out.println("不能插入，因为"+heroNode.number+"已经存在"); }else { //可以插入 heroNode.next =temp.next; temp.next = heroNode; } } //显示链表[遍历] public void list(){ if (head.next == null){ System.out.println("链表为空"); return; } //因为头结点，不能动，我们需要一个辅助变量来遍历 /** 这个遍历的时候容易出错，我们自己学习的时候可以多用debug来进行学习 我们看67行，我们搞了一个辅助变量temp因为头结点不能动，我们让temp = 头结点的下一个对象 好，我们进入while循环，直接打印temp的信息，因为我们上边重写了toString方法可以直接打印 之后！我们将temp在后移，此时的temp已经是头结点的下一个对象了，之后在后移这样就可以实现 打印链表中的所有对象了！ */ HeroNode temp = head.next; while (true){ //判断是否到链表最后 if (temp == null){ break; } //输出节点信息 System.out.println(temp); //将next后移，一定小心 temp = temp.next; } } } //定义HereNode,每一个HeroNode对象就是一个节点 class HeroNode { public int number; public String name; public String nickname; public HeroNode next; //指向下一个节点 //构造器 public HeroNode(int number, String name, String nickname) { this.number = number; this.name = name; this.nickname = nickname; } @Override public String toString() { return "HeroNode{" + "number=" + number + ", name='" + name + '\'' + ", nickname='" + nickname + '\'' + " }"; } }
实现效果
不能插入，因为2已经存在
HeroNode{number=1, name='宋江', nickname='及时雨' } HeroNode{number=2, name='卢俊义', nickname='玉麒麟' } HeroNode{number=3, name='吴用', nickname='智多星' } Process finished with exit code 0
