2021年继续扬帆起航~~双链表的学习

2021年继续扬帆起航~~双链表的学习

01学习了单链表发现存在以下几点的缺点。

1. 单向链表，查找的方向只能是一个方向吗，而双向链表可以向前或者向后查找。
2. 单向链表不能自我删除，需要靠辅助节点，而双向链表，则可以自我删除，所以前面我们单链表删除时节点，总是找到temp，temp是待删除节点的前一个节点。

02双向链表类

双向链表的组成:data域、next域(指向下一个节点)、pre域(指向前一个节点)
具体代码如下:

//定义DoubleLinkedList
class DoubleLinkedList {//定义头结点 位置保持不变private HeroNode2 head = new HeroNode2(0, "", "");//提供头节点的getter构造器public HeroNode2 getHead() {return head;}//增删改查的方法}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) { = no;this.name = name;this.nickname = nickname;}//展示英雄 重写toString方法@Overridepublic String toString() {return "HeroNode{" +"no=" + no +", name='" + name + ''' +", nickname='" + nickname + ''' +'}';}
}

03双链表的增删改查

3.1遍历

思路分析：

• 双向链表遍历和单链表一样，只是可以向前，也可以向后查找

具体代码:

    //显示链表[遍历]public void list() {//判断链表是否为空if ( == null) {System.out.println("链表为空");return;}//因为头节点不能动，需要一个辅助变量来遍历HeroNode2 temp = ;while (true) {//判断是否到链表最后if (temp == null) {break;}//输出节点信息System.out.println(temp);//循环完第一个节点后应该 指向下一个节点temp = ;}}

3.2添加(默认添加到双向链表的最后)

思路分析：

• 先找到双向链表的最后这个节点
< = newHeroNode;
• newHeroNode.pre = temp;

具体代码:

 //添加节点public void add(HeroNode2 heroNode) {//定义辅助变量指向头节点HeroNode2 temp = head;//找到当前链表的最后节点 需要遍历while (true) {//判断是否存在下一个节点if ( == null) {break;}//如果没有找到temp后移temp = ;}//将最后这个节点的next 指向新节点//形成双向链表 = heroNode;heroNode.pre = temp;}

3.3修改

思路分析：

• 找到要修改的数据的前一个节点
• 只能修改节点的姓名和昵称 不能修改节点的编号如果要修改成了添加一个节点

具体代码:

 public void update(HeroNode2 newHeroNode) {//判断是否为空if ( == null) {System.out.println("链表为空");return;}//辅助变量HeroNode2 temp = ;boolean flag = false;//标记是找到修改的节点//循环判断是否存在要修改的节点信息while (true) {if (temp == null) {break;}if ( == ) {flag = true;break;}//如果上述条件都不满足,则继续循环遍历查找要修改的节点temp = ;}//判断标记是否为trueif (flag) {temp.name = newHeroNode.name;temp.nickname = newHeroNode.nickname;} else {System.out.printf("要修改的节点%d号,不存在n", );}}

3.4删除

思路分析：

• 因为是双向链表，因此，我们可以实现自我删除某个节点
• 直接找到要删除的这个节点吗，比如temp
• = ;

具体代码:

public void delete(int no) {//判断当前链表是否为空if ( == null) {//空链表System.out.println("链表为空，无法删除");return;}//辅助变量HeroNode2 temp = ;boolean flag = false;//循环遍历找出需要删除的节点位置while (true) {if (temp == null) {break;}if ( == no) {flag = true;break;}//后移继续查找要删除节点的位置temp = ;}if (flag) { = ;if ( != null) {pre = temp.pre;}} else {System.out.printf("要删除的节点%d号,不存在n", no);}}

04测试双链表的增删改查

   HeroNode2 hero1 = new HeroNode2(1, "宋江", "及时雨");HeroNode2 hero2 = new HeroNode2(2, "卢俊义", "玉麒麟");HeroNode2 hero3 = new HeroNode2(3, "吴用", "智多星");HeroNode2 hero4 = new HeroNode2(4, "林冲", "豹子头");DoubleLinkedList doubleLinkedList = new DoubleLinkedList();System.out.println("添加后的的情况");doubleLinkedList.add(hero1);doubleLinkedList.add(hero2);doubleLinkedList.add(hero3);doubleLinkedList.add(hero4);doubleLinkedList.list();//修改链表HeroNode2 newHero = new HeroNode2(4, "公孙胜", "入云龙");doubleLinkedList.update(newHero);System.out.println("修改过后的情况");doubleLinkedList.list();//删除链表英雄doubleLinkedList.delete(3);System.out.println("删除过后的情况");doubleLinkedList.list();

结果:

添加后的的情况
HeroNode{no=1, name=‘宋江’, nickname=‘及时雨’}
HeroNode{no=2, name=‘卢俊义’, nickname=‘玉麒麟’}
HeroNode{no=3, name=‘吴用’, nickname=‘智多星’}
HeroNode{no=4, name=‘林冲’, nickname=‘豹子头’}
修改过后的情况
HeroNode{no=1, name=‘宋江’, nickname=‘及时雨’}
HeroNode{no=2, name=‘卢俊义’, nickname=‘玉麒麟’}
HeroNode{no=3, name=‘吴用’, nickname=‘智多星’}
HeroNode{no=4, name=‘公孙胜’, nickname=‘入云龙’}
删除过后的情况
HeroNode{no=1, name=‘宋江’, nickname=‘及时雨’}
HeroNode{no=2, name=‘卢俊义’, nickname=‘玉麒麟’}
HeroNode{no=4, name=‘公孙胜’, nickname=‘入云龙’}