1.链表介绍
image.png
- 链表是以节点的方式存储元素的，是链式存储的
- 每个节点包含data域和next域，data域用来存放数据，next域用来指向下一个节点
- 如图，链表中的节点不一定是连续存储的
- 链表可以分为带头节点和不带头节点的，可以按需求来确定
2.应用实例：给水浒好汉排序
1)完成对人物的增删改查
2)第一种方式：直接将英雄插入到链表末尾
3)第二种方式：将英雄按照排名插入到链表中
image.png
3.思路分析
将元素直接插入到链表末尾
添加：
1.先新建一个head头节点，作用就是表示单链表的头
2.后面每添加一个节点，就直接加入到链表的最后
遍历：
通过一个辅助变量帮助遍历整个链表。
问：为什么需要一个辅助变量？
答：这是因为头节点不能动。
将元素按照编号顺序插入链表
image.png
添加：
1.借助一个辅助变量找到新的元素所在的位置
2.新的节点.next = temp.next
3.temp.next = 新的节点
4.代码实现
package com.yc.day01.linkedlist;
public class SingleListTest {
public static void main(String[] args) {
HeroNode h1 = new HeroNode(1, "宋江", "及时雨");
HeroNode h2 = new HeroNode(2, "卢俊义", "玉麒麟");
HeroNode h3 = new HeroNode(3, "吴用", "智多星");
SingleList singleList = new SingleList();
singleList.add(h1);
singleList.add(h2);
singleList.add(h3);
singleList.print();
}
}
class SingleList{
//初始化一个头节点，头节点不要动，不存放数据
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;
}
//退出循环后表示找到最后一个节点
temp.next = heroNode;
}
//显示链表
public void print(){
//因为头节点不能动，所以需要辅助变量temp
HeroNode temp = head.next;
//遍历输出
while (true){
if(temp==null){
break;
}
System.out.println(temp);
temp = temp.next;
}
}
}
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;
}
public HeroNode() {
}
@Override
public String toString() {
return "HeroNode{" +
"no=" + no +
", name='" + name + '\'' +
", nickName='" + nickName + '\'' +
'}';
}
}
按照顺序添加元素
public void addByOrder(HeroNode heroNode){
//因为头节点不能动，所以需要一个辅助变量去找新节点的位置
HeroNode temp = head;
boolean flag = false;//标识节点是否已存在
while (true){
if(temp.next==null){
break;
}
if(temp.next.no>heroNode.no){//位置找到
break;
}else if(temp.next.no==heroNode.no){
flag = true;
break;
}
//未找到位置，应该继续向下找
temp = temp.next;
}
//循环退出说明已经找到新节点要插入的位置
if(flag){
System.out.printf("要插入的英雄编号%d已存在\n",heroNode.no);
}else {
heroNode.next = temp.next;
temp.next = heroNode;
}
}
修改
public void update(HeroNode heroNode){
HeroNode temp = head.next;
boolean flag = false;//标志是否存在指定节点
while (true){
if(temp==null){
break;
}
if(temp.no==heroNode.no){
flag = true;
break;
}
//指向下一个节点
temp = temp.next;
}
//退出循环表示找到指定节点
if(flag){
temp.name = heroNode.name;
temp.nickName = heroNode.nickName;
}else {
System.out.printf("编号为%d的节点不存在\n",heroNode.no);
}
}
删除
思路分析：
1）通过辅助变量temp遍历找到要删除的指定节点
2）删除操作：temp.next = temp.next.next;
public void del(int no){
HeroNode temp = head;
boolean flag = false;
while (true){
if(temp.next == null){
break;
}
if(temp.next.no==no){
flag = true;
break;
}
temp = temp.next;
}
if(flag){
temp.next = temp.next.next;
}else{
System.out.printf("编号为%d的节点不存在",no);
}
}
问：什么时候将temp初始化为head，而什么时候又将temp初始化为head.next?
答：当需要找到指定元素的前一个节点时就初始化为head,否则为head.next。比如说插入和删除都需要找到指定元素的前一个元素，所以初始化为head。而打印和修改只需要找到指定元素就可以了，所以初始化为head.next
5.面试题
5.1单链表中有效节点个数（不包括头节点）
/**
* 获取有效节点个数
* */
public int length(){
HeroNode temp = head;
int count = 0;
while (true){
if(temp.next==null){
break;
}
temp = temp.next;
count++;
}
return count;
}
5.2获取单链表中倒数第n个节点
/**
* 获取链表中倒数第n个节点
* */
public HeroNode getTargetIndexNode(int index){
HeroNode temp = head.next;
int length = length();
if(index<=0||index>length){
return null;
}
for (int i=0;i<length-index;i++){
temp = temp.next;
}
return temp;
}
5.3单链表反转
/**
* 单链表反转
* */
public void reverse(){
HeroNode temp = head.next;
//链表为空或者只有一个元素时，不用做操作
if(temp==null||temp.next==null){
return;
}
HeroNode reverseHead = new HeroNode(0,"","");
HeroNode next = null;
while(temp!=null){
next = temp.next;
temp.next = reverseHead.next;//把reverseHead这条链表中当前元素和它的下一个元素连接起来
reverseHead.next = temp;
temp = next;
}
head.next = reverseHead.next;
}
解释下代码
while(temp!=null){
next = temp.next;
temp.next = reverseHead.next;//把reverseHead这条链表中当前元素和它的下一个元素连接起来
reverseHead.next = temp;
temp = next;
}
第一次进入循环时,执行前两步：temp为宋江，next为卢俊义，reverseHead.next为null,所以temo.next也为null
第二次进入循环时，执行前两步：temp为卢俊义，next为吴用，reverseHead.next为宋江，temo.next也为宋江，此时就将卢俊义和宋江连起来了
5.4逆序打印单链表
利用栈先进后出的特点
/**
* 逆序打印单链表
* */
public void reversePrint(){
HeroNode temp = head.next;
if(temp==null){
return;
}
Stack<HeroNode> heroNodes = new Stack<HeroNode>();
while (temp!=null){
heroNodes.push(temp);
temp = temp.next;
}
while (heroNodes.size()>0){
System.out.println(heroNodes.pop());
}
}
