双向链表：
单向链表只能单向查找，双向链表可以双向查找。
啥是双向链表？
image-20200713203325695.png
双向链表可以双向查数据，所以就不存在单向链表中链表反转的操作。
双向链表的节点：
- data 数据
- next 指向下一个节点
- pre 指向上一个节点
public class HeroDoubleNode {
private int no;
private String name;
private String nickname;
private HeroDoubleNode next;
private HeroDoubleNode pre;
public HeroDoubleNode(int no, String name, String nickname) {
this.no = no;
this.name = name;
this.nickname = nickname;
}
public void setNo(int no) {
this.no = no;
}
public void setName(String name) {
this.name = name;
}
public void setNickname(String nickname) {
this.nickname = nickname;
}
public void setNext(HeroDoubleNode next) {
this.next = next;
}
public void setPre(HeroDoubleNode pre) {
this.pre = pre;
}
public int getNo() {
return no;
}
public String getName() {
return name;
}
public String getNickname() {
return nickname;
}
public HeroDoubleNode getNext() {
return next;
}
public HeroDoubleNode getPre() {
return pre;
}
@Override
public String toString() {
return "HeroDoubleNode{" +
"no=" + no +
", name='" + name + '\'' +
", nickname='" + nickname +'}';
}
}
双向链表 基本操作
- 遍历双向链表
从head开始顺着 .next 一直遍历下去
//遍历双向链表
public void showLinked(){
// 判断链表是否为空
if (head.getNext()==null){
System.out.println("链表为空");
return;
}
// 链表不为空循环遍历打印输出
HeroDoubleNode temp = head.getNext();
while (true){
//判断是否为尾节点
if (temp==null) {
break;
}
//不是则打印下一个节点
System.out.println(temp);
//指针后移
temp = temp.getNext();
}
}
- 添加节点（默认添加在最后）
最后一个节点的next指针指向新节点，新节点的pre指向temp
image-20200713203759090.png
// 添加节点
public void addNode(HeroDoubleNode heroNode){
//先找到尾部节点再进行插入
//创建一个temp指针进行遍历,这里我就直接让temp指向头结点的下一个节点
HeroDoubleNode temp = head;
while (true){
//判断节点是否为空
if (temp.getNext()==null){
break;
}
//不是尾节点指针后移
temp = temp.getNext();
}
//经过遍历temp就是尾部节点
temp.setNext(heroNode);
heroNode.setPre(temp);
}
- 修改
通过next一直找到要修改的节点直接修改
/**
* 根据no来修改节点信息,即no 不能发生改变
*/
public void update(HeroDoubleNode heroNode){
//判断练表是否为空
if (head.getNext()==null){
System.out.println("链表为空");
return;
}
HeroDoubleNode temp = head.getNext();
boolean flag = false; //判断链表是否找到这个节点
while (true){
//判断链表是否为空
if (temp == null){
break;
}
// 判断链表是否找到这个节点
if (temp.getNo()==heroNode.getNo()){
flag=true;
break;
}
temp = temp.getNext();
}
//判断链表是否找到这个节点
if (flag){
temp.setName(heroNode.getName());
temp.setNickname(heroNode.getNickname());
}else {
System.out.println("链表不存在此节点:"+heroNode);
}
}
- 按照顺序添加
- 先将节点挂在前后两个节点上
添加（1）
- 前后两个节点断开连接，连接到新节点上
添加（2）
/**
* 按照编号添加节点
*/
public void addByOrder(HeroDoubleNode heroNode){
//由于是单链表temp只能在插入节点之前！！！
HeroDoubleNode temp = head;
boolean flag = false;//判断插入的编号是否存在
while (true){
// 查看是不是最后一个节点
if (temp.getNext()==null){break;}
// 查看插入的位置
if (temp.getNext().getNo()>heroNode.getNo()){
//位置找到就应该在temp的后面添加
break;
}else if(temp.getNext().getNo() == heroNode.getNo()){
//说明编号已经存在
flag = true;
break;
}
temp = temp.getNext();
}
if (flag){
//不能插入文字提示
System.out.printf("待插入的英雄（编号：%d）已经存在\n",heroNode.getNo());
}else {//插入内容
heroNode.setPre(temp);
heroNode.setNext(temp.getNext());
temp.setNext(heroNode);
if (temp.getNext()!=null){//防止空指针异常
temp.getNext().setPre(heroNode);
}
}
}
- 删除
- temp.pre.next = temp.next
- temp.next.pre = temp.pre
temp没有被引用会被垃圾回收机制回收
删除
/**
* 根据no删除节点
* temp.next = temp.next.next
* 未被引用的节点会被JVM的垃圾回收机制回收
* 1. 双向链表我们直接找到要删除的这个节点
* 2. 找到后在进行删除
*/
public void delete(int no){
if (head.getNext()==null){
System.out.println("链表为空，无法删除");
return;
}
HeroDoubleNode temp = head.getNext();
//是否找到删除节点
boolean flag = false;
while (true){
//判断链表是否为空
if (temp==null){
break;
}
if (temp.getNo()==no){
//找到节点
flag = true;
break;
}
temp = temp.getNext();//指针后移，继续遍历
}
if (flag){
temp.getPre().setNext(temp.getNext());
if (temp.getNext()!=null){//防止最后一个节点出现空指针异常！！！
temp.getNext().setPre(temp.getPre());
}
}else {
System.out.println("删除====该节点值不存在");
}
}
public class DoubleLinkedList {
public HeroDoubleNode head = new HeroDoubleNode(0,"","");
public HeroDoubleNode getHead() {
return head;
}
//遍历双向链表
public void showLinked(){
// 判断链表是否为空
if (head.getNext()==null){
System.out.println("链表为空");
return;
}
// 链表不为空循环遍历打印输出
HeroDoubleNode temp = head.getNext();
while (true){
//判断是否为尾节点
if (temp==null) {
break;
}
//不是则打印下一个节点
System.out.println(temp);
//指针后移
temp = temp.getNext();
}
}
// 添加节点
public void addNode(HeroDoubleNode heroNode){
//先找到尾部节点再进行插入
//创建一个temp指针进行遍历,这里我就直接让temp指向头结点的下一个节点
HeroDoubleNode temp = head;
while (true){
//判断节点是否为空
if (temp.getNext()==null){
break;
}
//不是尾节点指针后移
temp = temp.getNext();
}
//经过遍历temp就是尾部节点
temp.setNext(heroNode);
heroNode.setPre(temp);
}
/**
* 根据no来修改节点信息,即no 不能发生改变
*/
public void update(HeroDoubleNode heroNode){
//判断练表是否为空
if (head.getNext()==null){
System.out.println("链表为空");
return;
}
HeroDoubleNode temp = head.getNext();
boolean flag = false; //判断链表是否找到这个节点
while (true){
//判断链表是否为空
if (temp == null){
break;
}
// 判断链表是否找到这个节点
if (temp.getNo()==heroNode.getNo()){
flag=true;
break;
}
temp = temp.getNext();
}
//判断链表是否找到这个节点
if (flag){
temp.setName(heroNode.getName());
temp.setNickname(heroNode.getNickname());
}else {
System.out.println("链表不存在此节点:"+heroNode);
}
}
/**
* 根据no删除节点
* temp.next = temp.next.next
* 未被引用的节点会被JVM的垃圾回收机制回收
* 1. 双向链表我们直接找到要删除的这个节点
* 2. 找到后在进行删除
*/
public void delete(int no){
if (head.getNext()==null){
System.out.println("链表为空，无法删除");
return;
}
HeroDoubleNode temp = head.getNext();
//是否找到删除节点
boolean flag = false;
while (true){
//判断链表是否为空
if (temp==null){
break;
}
if (temp.getNo()==no){
//找到节点
flag = true;
break;
}
temp = temp.getNext();//指针后移，继续遍历
}
if (flag){
temp.getPre().setNext(temp.getNext());
if (temp.getNext()!=null){//防止最后一个节点出现空指针异常！！！
temp.getNext().setPre(temp.getPre());
}
}else {
System.out.println("删除====该节点值不存在");
}
}
/**
* 按照编号添加节点
*/
public void addByOrder(HeroDoubleNode heroNode){
//由于是单链表temp只能在插入节点之前！！！
HeroDoubleNode temp = head;
boolean flag = false;//判断插入的编号是否存在
while (true){
// 查看是不是最后一个节点
if (temp.getNext()==null){break;}
// 查看插入的位置
if (temp.getNext().getNo()>heroNode.getNo()){
//位置找到就应该在temp的后面添加
break;
}else if(temp.getNext().getNo() == heroNode.getNo()){
//说明编号已经存在
flag = true;
break;
}
temp = temp.getNext();
}
if (flag){
//不能插入文字提示
System.out.printf("待插入的英雄（编号：%d）已经存在\n",heroNode.getNo());
}else {//插入内容
heroNode.setPre(temp);
heroNode.setNext(temp.getNext());
temp.setNext(heroNode);
if (temp.getNext()!=null){//防止空指针异常
temp.getNext().setPre(heroNode);
}
}
}
}
网友评论