一、单链表介绍
- 链表是有序的列表；
- 以节点的方式来存储；
- 每个节点包含data域，next域：指向下一个节点；
- 链表的各个节点不一定是连续存放；
- 链表分为带头节点的和不带头节点的链表；
package 数据结构;
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(hero3);
// singleLinkedList.add(hero2);
//
// singleLinkedList.add(hero4);
//按顺序添加节点
singleLinkedList.addByOrder(hero4);
singleLinkedList.addByOrder(hero1);
singleLinkedList.addByOrder(hero3);
singleLinkedList.addByOrder(hero2);
//测试修改节点
HeroNode newHeroNode=new HeroNode(1, "zhangsan", "法外狂徒");
singleLinkedList.update(newHeroNode);
//删除节点
singleLinkedList.del(1);
singleLinkedList.del(3);
//显示节点
singleLinkedList.list();
}
}
class SingleLinkedList{
//定义一个头节点，不存放具体数据
private HeroNode head=new HeroNode(0, "", "");
/*
* 添加节点到单链表
* 当不考虑编号顺序时，找到当前链表的最后节点，然后将最后节点的next指向新的节点
*/
public void add(HeroNode heroNode) {
HeroNode temp=head;//头节点不能动
while(true) {
//找到链表的最后
if(temp.next==null) {
break;
}
//没有找到则将temp后移
temp=temp.next;
}
//将最后节点的next指向新的节点
temp.next=heroNode;
}
//显示链表
public void list() {
//先判断是否为空
if(head.next==null) {
System.out.println("empty");
return;
}
HeroNode temp=head.next;
while(true) {
//退出循环条件
if(temp.next==null) {
break;
}
System.out.println(temp);
temp=temp.next;
}
}
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;//位置找到，在temp后面插入
}else if(temp.next.no==heroNode.no) {
flag=true;//说明编号已经存在
break;
}
temp=temp.next;
}
if(flag) {
System.out.println("编号已存在");
}else {
//可以插入到链表中temp的后面
heroNode.next=temp.next;
temp.next=heroNode;
}
}
public void update(HeroNode newHeroNode) {
if(head.next==null) {
System.out.println("empty");
return;
}
boolean flag=false;
HeroNode temp=head.next;
while(true) {
if(temp.next==null) {
break;
}else if(temp.no==newHeroNode.no) {
flag=true;//找到了要修改的节点
break;
}
temp=temp.next;
}
if(flag) {
temp.name=newHeroNode.name;
temp.nickname=newHeroNode.nickname;
}else {
System.out.println("未找到");
}
}
public void del(int no) {
HeroNode temp=head;
boolean flag=false;
while(true) {
if(temp.next==null) {
break;
}else if(temp.next.no==no) {
flag=true;//找到待删除节点的前一个节点temp
break;
}
temp=temp.next;
}
if(flag) {
temp.next=temp.next.next;
}else {
System.out.println("未找到");
}
}
}
//每一个HeroNode对象就是一个节点
class HeroNode{
public int no;
public String name;
public String nickname;
public HeroNode next;//指向下一个节点
//创建构造器
public HeroNode(int no,String name,String nickname) {
this.name=name;
this.no=no;
this.nickname=nickname;
}
//重写toString
@Override
public String toString() {
return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
}
}单链表注意事项：
- 头节点不能改动，因此引入临时节点temp;
- 判断链表是否为空：head.next==null;
- 判断是否到达链表尾部：temp.next==null;
- 删除节点：要找到待删除节点的前一个节点。
二、双向链表介绍
- 单向链表的查找方向只能是一个方向，而双向链表可以向前或则向后查找；
- 单链表需要依靠辅助节点来删除节点，而双向链表可以自我删除。
- 双向链表与单向链表的最大不同操作是：删除节点。
package 数据结构;
public class DoubleLinkedListDemo {
public static void main(String[] args) {
// TODO 自动生成的方法存根
//创建节点进行测试
HeroNode2 hero1=new HeroNode2(1, "宋江", "及时雨");
HeroNode2 hero2=new HeroNode2(2, "吴用", "智多星");
HeroNode2 hero3=new HeroNode2(3, "鲁智深", "花和尚");
HeroNode2 hero4=new HeroNode2(4, "林冲", "豹子头");
//创建链表
DoubleLinkedList doubleLinkedList=new DoubleLinkedList();
//添加节点
doubleLinkedList.add(hero4);
doubleLinkedList.add(hero1);
doubleLinkedList.add(hero2);
doubleLinkedList.add(hero3);
//显示链表
doubleLinkedList.list();
//删除节点
doubleLinkedList.del(4);
doubleLinkedList.list();
}
}
//创建一个双向链表
class DoubleLinkedList{
//定义一个头节点，不存放具体数据
private HeroNode2 head=new HeroNode2(0, "", "");
//得到头节点
public HeroNode2 getHead() {
return head;
}
//添加节点
public void add(HeroNode2 heroNode) {
HeroNode2 temp=head;//头节点不能动
while(true) {
//找到链表的最后
if(temp.next==null) {
break;
}
//没有找到则将temp后移
temp=temp.next;
}
//两步：将最后节点的next指向新的节点,新节点的pre指向temp.
temp.next=heroNode;
heroNode.pre=temp;
}
//修改节点
public void update(HeroNode2 newHeroNode) {
if(head.next==null) {
System.out.println("empty");
return;
}
boolean flag=false;
HeroNode2 temp=head.next;
while(true) {
if(temp.next==null) {
break;
}else if(temp.no==newHeroNode.no) {
flag=true;//找到了要修改的节点
break;
}
temp=temp.next;
}
if(flag) {
temp.name=newHeroNode.name;
temp.nickname=newHeroNode.nickname;
}else {
System.out.println("未找到");
}
}
//删除节点
public void del(int no) {
HeroNode2 temp=head.next;//temp是第一个节点
boolean flag=false;
while(true) {
if(temp==null) {
break;
}else if(temp.no==no) {
flag=true;//找到待删除节点
break;
}
temp=temp.next;
}
if(flag) {
temp.pre.next=temp.next;
//如果是最后一个节点则不需要执行第二句
if(temp.next!=null) {
temp.next.pre=temp.pre;
}
}else {
System.out.println("未找到");
}
}
//显示链表
public void list() {
//先判断是否为空
if(head.next==null) {
System.out.println("empty");
return;
}
HeroNode2 temp=head.next;
while(true) {
//退出循环条件
if(temp.next==null) {
break;
}
System.out.println(temp);
temp=temp.next;
}
}
}
//每一个HeroNode对象就是一个节点
class HeroNode2{
public int no;
public String name;
public String nickname;
public HeroNode2 next;//指向下一个节点
public HeroNode2 pre;//指向前一个节点
//创建构造器
public HeroNode2(int no,String name,String nickname) {
this.name=name;
this.no=no;
this.nickname=nickname;
}
//重写toString
@Override
public String toString() {
return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
}
}