- 链表简介
- 简单的链表
- 顺序链表
- 单链表的插入
- 单链表的插入与删除
- 单链表新浪面试题
- 思路分析
- 查找单链表中的倒数第k个结点
- 思路分析
- 单链表的反转
- 思路分析
- 逆序打印链表
- 思路分析
- 双向链表
- 双向链表的添加节点
- 双向链表删除节点
- 循环链表
- 约瑟夫环问题
- 环行链表的思路分析：
- 约瑟夫环思路分析：
因为学过C语言版的数据结构，这里很好理解
- 链表是以节点的方式来存储,是链式存储
- 每个节点包含data域, next域:指向下一个节点.
- 如图:发现链表的各个节点不一定是连续存储.
- 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定单链表(带头结点)逻辑结构示意图如下
我博客前面有更新大话数据结构，这块讲的比较详细，有需求的可以去看看
简单的链表package com.caq.linkedlist;
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后移
temp = temp.next;//将我们的这个临时对象变量后移指向头接点的下一个元素
}
//当退出while循环时，temp就指向了链表的最后
//将最后这个节点的next指向了新的节点
temp.next = heroNode;//把这个对象变量指向heroNode也就是我们的新节点
}
//显示链表[遍历]
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);
//将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;
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后移
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;
}
//因为头结点，不能动，我们需要一个辅助变量来遍历
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
单链表的插入
实现思路如下：
Java中的插入和C语言中的插入思路是一样的
都是改变指针的指向，Java中没有被引用的对象会被垃圾回收
删除的思路
单链表的插入与删除package com.caq.linkedlist;
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();
System.out.println("***************");
//修改节点的代码
HeroNode heronode = new HeroNode(2, "库里", "萌神");
singlelinkedList.update(heroNode);
singlelinkedList.list();
System.out.println("***************");
//删除节点
singlelinkedList.delete(2);
singlelinkedList.delete(2);//没有找到要删除的结点2!
singlelinkedList.delete(1);
singlelinkedList.delete(3);//没有找到要删除的结点3!
singlelinkedList.delete(3);//链表为空
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后移
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;
}
}
//修改节点的信息，根据number编号来修改，既number编号不能改
public void update(HeroNode heroNode) {
HeroNode temp = head.next;
boolean flag = false;
while (true) {
if (temp.next == null) {
break;
}
//匹配节点
if (temp.number == heroNode.number) {
flag = true;
break;
}
temp = temp.next;
}
if (flag) {
temp.name = heroNode.name;
temp.nickname = heroNode.nickname;
} else {
System.out.println("没有找到编号为" + heroNode.number + "");
}
}
//删除节点
public void delete(int number) {
HeroNode temp = head;
boolean flag = false; //是否找到
while (true) {
if (temp.next == null) { //到最后了
break;
}
if (temp.next.number == number) {
flag = true;
break;
}
temp = temp.next; //temp后移，遍历链表
}
//被删除的结点，不会有其他引用指向，会被垃圾回收机制回收
//这和c语言一模一样啊！
if (flag) {
temp.next = temp.next.next;
}else {
System.out.println("没有找到要删除的结点"+number+"!");
}
}
//显示链表[遍历]
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);
//将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='智多星' }
***************
HeroNode{number=1, name='宋江', nickname='及时雨' }
HeroNode{number=2, name='库里', nickname='萌神' }
HeroNode{number=3, name='吴用', nickname='智多星' }
***************
没有找到要删除的结点2!
没有找到要删除的结点3!
链表为空
单链表新浪面试题
思路分析
定义一个辅助变量和一个计数器变量
让辅助变量一直往后指，只要不为空，计数器就加+1
最后return计数器的值
//显示有效结点的个数（头结点不统计）
public static int getLength(HeroNode head) {
if (head.next == null) {//证明是空链表
return 0;
}
int len = 0;
HeroNode temp = head.next;
while (temp != null) {
len++;
temp = temp.next; //向后遍历
}
return len;
}
输出结果
HeroNode{number=1, name='宋江', nickname='及时雨' }
HeroNode{number=2, name='卢俊义', nickname='玉麒麟' }
HeroNode{number=3, name='吴用', nickname='智多星' }
3
查找单链表中的倒数第k个结点
思路分析
1.编写一个方法，接受head节点，同时接收一个index
2.index表示是倒数第index个结点
3.先把链表从头到尾遍历，得到链表的总长度getLength
4.得到size后，我们从链表的第一个开始遍历（size-index）个，就可以得到
singlelinkedList.list();
System.out.println(getLength(singlelinkedList.getHead()));
//查看倒数第一个
System.out.println(findLastIndexNode(singlelinkedList.getHead(),1));
//查看倒数第二个
System.out.println(findLastIndexNode(singlelinkedList.getHead(),2));
public static HeroNode findLastIndexNode(HeroNode head, int index) {
if (head.next == null) {
return null;//没有找到
}
//第一个遍历得到的链表的有效长度
int size = getLength(head);
//第二个遍历size-index 位置，就是我们倒数的第k个结点
if (index <= 0 || index > size) {
return null;
}
//定义辅助变量，for循环定位到倒数的i
//比如我们要找倒数第二个，我们的有效数据是3个的话size-index = 1,也就是往后移动一位即可
HeroNode temp = head.next;
for (int i =0;i
输出结果为HeroNode{number=1, name='宋江', nickname='及时雨' }HeroNode{number=2, name='卢俊义', nickname='玉麒麟' }HeroNode{number=3, name='吴用', nickname='智多星' }3HeroNode{number=3, name='吴用', nickname='智多星' }HeroNode{number=2, name='卢俊义', nickname='玉麒麟' }
单链表的反转
思路分析
1.先定义一个节点reverseHead = new Heronode();
2.从头到尾遍历原来的链表，每遍历出来一个节点，就将其取出，并放在新的链表的最前端
3.原来的链表的head.next = reverseHead.next
public static void reversetList(HeroNode head) { //如果当前链表为空，或者只有一个节点，无需反转 if (head.next == null || head.next.next == null) { return; } //定义一个辅助的指针（变量）,帮助我们遍历原来的链表 Heronode temp = head.next; Heronode next = null;//指向当前节点的下一个节点 Heronode reverseHead = new Heronode(0, "", ""); //遍历原来的链表，并从头到尾遍历原来的链表，每遍历一个节点，就将其取出，并放在新链表reverseHead的最前端 while (temp != null) { next = temp.next;//先暂时保持当前节点的下一个节点。因为后面需要使用 temp.next = reverseHead.next;// reverseHead.next = temp;//将temp连接到新的链表上 temp = next;//让temp后移 } //将head.next指向reverseHead.next,实现单链表的反转 head.next = reverseHead.next;}
输出结果
//反转单链表System.out.println("*********");reversetList(singlelinkedList.getHead());singlelinkedList.list();HeroNode{number=1, name='宋江', nickname='及时雨' }HeroNode{number=2, name='卢俊义', nickname='玉麒麟' }HeroNode{number=3, name='吴用', nickname='智多星' }*********HeroNode{number=3, name='吴用', nickname='智多星' }HeroNode{number=2, name='卢俊义', nickname='玉麒麟' }HeroNode{number=1, name='宋江', nickname='及时雨' }
逆序打印链表
思路分析
不改变链表的结构情况下，利用栈先进后出的特性，将对象全放到栈里，最后在一个一个的d出来
//通过栈来实现链表的反转打印public static void stacktest(Heronode head){ if (head.next ==null){ return; } //创建一个栈，将各个结点压入栈 Stack stack = new Stack<>(); Heronode temp = head.next; //将链表的所有节点压入栈 while (temp != null){ stack.push(temp); temp = temp.next;//temp后移，这样就可以压入下一个节点 } //将栈中的结点进行打印，pop出栈 while (stack.size() > 0){ System.out.println(stack.pop()); }}
输出结果
HeroNode{number=3, name='吴用', nickname='智多星' }HeroNode{number=2, name='卢俊义', nickname='玉麒麟' }HeroNode{number=1, name='宋江', nickname='及时雨' }
双向链表
上图是C语言中的双向链表插入元素 的时候指针的变化
同样适用于我们Java中！
今天算是深刻体会到了C语言的重要性
上面的标注中，有个重要的点是
我们是把p赋值给s的前驱或者说是s的前驱指向了p
之后我们只能说是把p->next赋值给了s->next（不能说把s->next赋值给p->next）
双向链表的添加节点
双向链表删除节点
package com.caq.linkedlist;public class DoublelinkedDemo { public static void main(String[] args) { HeroNode2 head = new HeroNode2(2, "", ""); //双向链表的测试 HeroNode2 hero1 = new HeroNode2(1, "宋江", "及时雨"); HeroNode2 hero2 = new HeroNode2(2, "卢俊义", "玉麒麟"); HeroNode2 hero3 = new HeroNode2(3, "吴用", "智多星"); DoublelinkedList doublelinkedList = new DoublelinkedList(); doublelinkedList.add(hero1); doublelinkedList.add(hero2); doublelinkedList.add(hero3); doublelinkedList.list(); //修改 HeroNode2 newHero = new HeroNode2(2, "BB", "CC"); doublelinkedList.update(newHero); System.out.println("修改后的情况为"); doublelinkedList.list(); }}class DoublelinkedList { //生一个头结点 private HeroNode2 head = new HeroNode2(0, "", ""); //得到头结点 public HeroNode2 getHead() { return head; } //显示链表[遍历] public void list() { if (head.next == null) { System.out.println("链表为空"); return; } HeroNode2 temp = head.next; while (true) { if (temp == null) { break; } System.out.println(temp); temp = temp.next; } } //添加节点到单向链表 public void add(HeroNode2 heroNode) { HeroNode2 temp = head; //遍历链表，找到最后 while (true) { //找到链表的最后 if (temp.next == null) { break; } //如果没有找到最后，就讲temp后移 temp = temp.next; } //当退出while循环时，temp就指向了链表的最后 //形成一个双向链表 temp.next = heroNode; heroNode.pre = temp; } //修改思路和单链表一样 public void update1(HeroNode2 heroNode2) { boolean flag = false; HeroNode2 temp = head.next; while (true) { //寻找要修改的结点 if (temp == null) { break; } else if (temp.number == heroNode2.number) { flag = true; break; } temp = temp.next; } if (flag) { temp.next = heroNode2.next; temp.pre = heroNode2.pre; } } public void update(HeroNode2 heroNode) { HeroNode2 temp = head.next; boolean flag = false; while (true) { if (temp.next == null) { break; } //匹配节点 if (temp.number == heroNode.number) { flag = true; break; } temp = temp.next; } if (flag) { temp.name = heroNode.name; temp.nextname = heroNode.nextname; } else { System.out.println("没有找到编号为" + heroNode.number + ""); } } //删除节点 //双向链表找到后可以自我删除不必借助其他结点 public void delete(int number) { HeroNode2 temp = head.next; boolean flag = false; //是否找到 while (true) { if (temp.next == null) { //到最后了 break; } if (temp.number == number) { flag = true; break; } temp = temp.next; //temp后移，遍历链表 } //被删除的结点，不会有其他引用指向，会被垃圾回收机制回收 //这和c语言一模一样啊！ if (flag) {// temp.next = temp.next.next; temp.pre.next = temp.next; //如果是最后一个节点，不需要执行下面这句话，否则会出现空指针 if (temp.next != null) { temp.next.pre = temp.pre; } else { System.out.println("没有找到要删除的结点" + number + "!"); } } }}class HeroNode2 { public int number; public String name; public String nextname; public HeroNode2 next; //指向下一个节点 public HeroNode2 pre;//指向前一个结点，默认为null public HeroNode2(int number, String name, String nextname) { this.number = number; this.name = name; this.nextname = nextname; } @Override public String toString() { return "HeroNode2{" + "number=" + number + ", name='" + name + ''' + ", nextname='" + nextname + ''' + '}'; }}
输出结果为：
HeroNode2{number=1, name='宋江', nextname='及时雨'}HeroNode2{number=2, name='卢俊义', nextname='玉麒麟'}HeroNode2{number=3, name='吴用', nextname='智多星'}修改后的情况为HeroNode2{number=1, name='宋江', nextname='及时雨'}HeroNode2{number=2, name='BB', nextname='CC'}HeroNode2{number=3, name='吴用', nextname='智多星'}
循环链表
将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表（ circuar linkedlist)。
其实循环链表和单链表的主要差异就在于循环的判断条件上，原来是判断p->next是否为空，现在则是p-> next不等于头结点，则循环未结束。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-XcoFO05D-1639655004233)(C:/Users/Jack/AppData/Roaming/Typora/typora-user-images/image-20211216110539595.png)]
约瑟夫环问题
约瑟夫问题是个有名的问题：N个人围成一圈，**从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。**例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3。
环行链表的思路分析：
构建一个单向的环形链表思路
1.先创建第一个节点,让first指向该节点,并形成环形
2.后面当我们每创建一个新的节点，就把该节点，加入到已有的环形链表中即可.
遍历环形链表
1.先让一个辅助指针(变量) curBoy，指向first节点
2.然后通过一个while循环遍历该环形链表即可curBoy.next == first结束
起始
curBoy.next -> newNode
boy.next -> first
curBoy = newNode
约瑟夫环思路分析：
约瑟夫环思
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）