数据结构双链表（5）

朱雀 2022-11-24 14:18 131阅读 0赞

### 双向链表 ###

#### 1、单链表&双链表区别 ####

*  单向链表，在查找的方向只能是一个方向，而双向链表可以向前或者向后查找
 *  单向链表不能自我删除，需要靠辅助节点。而双向链表能自我删除

#### 2、分析双向链表的遍历，添加，删除的操作思路 ####

*  1）遍历方式和单链表一样，可以向前也可以向后查找
 *  2）添加（默认添加到双向链表的最后
    
     *  先找到双向链表的最后这个节点
     *  temp.next = newHeroNode
     *  newHeroode.pre = temp
 *  3）修改思路和单链表一样
 *  4）删除
    
     *  因为双向链表，因此可以实现自我删除某个节点
     *  直接找到要删除的节点，比如temp
     *  让temp.pre.next = temp.next
     *  Temp.next.pre = temp.pre

#### 3、代码实现 ####

public class DoubleLinkedListDemo1 { 
        public static void main(String[] args) { 
            //测试双链表
            HeroNode2 hero1 = new HeroNode2(1, "科比", "NBA射手");
            HeroNode2 hero2 = new HeroNode2(2, "浓眉", "湖人三分射手");
            HeroNode2 hero3 = new HeroNode2(3, "詹姆斯", "NBA优秀创元");
            DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
            doubleLinkedList.add(hero1);
            doubleLinkedList.add(hero2);
            doubleLinkedList.add(hero3);
            doubleLinkedList.list();
            System.out.println("修改后～");
            //修改
            HeroNode2 hero4 = new HeroNode2(3, "易建联", "NBA优秀创元");
            doubleLinkedList.update(hero4);
            doubleLinkedList.list();
            //删除
            System.out.println("删除后");
            doubleLinkedList.del(2);
            doubleLinkedList.list();
    
        }
    }
    //创建一个双向链表类
    class DoubleLinkedList{ 
        //1,先初始化头节点，头节点不能动
        private HeroNode2 head = new HeroNode2(0,"","");
        //返回头节点
        public HeroNode2 getHead(){ 
            return head;
        }
        //============================添加方法====================================
        //2,添加节点到单向链表
        public void add(HeroNode2 heroNode2){ 
            //head节点不能动，则需要一个辅助节点
            HeroNode2 temp = head;
            //遍历链表，找到链表的最后
            while (true){ 
                if (temp.next == null){ //说明找到最后节点
                    break;
                }
                //如果没有找到最后节点，则需要将temp往后移
                temp = temp.next;
            }
            //当退出while时，temp就指向类链表的最后，最后将这个节点next指向新的节点
            temp.next = heroNode2;
            heroNode2.pre = temp;
        }
        //===============================更新方法=================================
        //修改节点信息，根据no编写来修改，即no编号不能该
        public void update(HeroNode2 newheroNode2) { 
            //判断是否为空
            if (head.next == null){ 
                System.out.println("链表为空");
                return;
            }
            //不为空则需要找到要修改的节点，根据no编号
            HeroNode2 temp = head.next;
            boolean flag = false;//表示是否找到该节点
            while (true){ 
                if (temp == null){ 
                    break;
                }
                if (temp.no == newheroNode2.no){ 
                    flag = true;//找到
                    break;
                }
                temp = temp.next;
            }
            //根据flag判断是否需要修改节点
            if (flag){ 
                temp.name = newheroNode2.name;
                temp.nickname = newheroNode2.nickname;
            } else { 
                System.out.printf("没有找到编号%d 的节点，不能修改\n",newheroNode2.no);
            }
        }
        //=========================删除=======================================
        public void del(int no){ 
            if (head.next == null){ 
                System.out.println("链表为空");
                return;
            }
            HeroNode2 temp = head.next;
            boolean flag = false;
            while (true){ 
                if (temp == null){ 
                    break;
                }
                if (temp.no == no){ 
                    flag = true;
                    break;
                }
                temp = temp.next;
            }
            if (flag){ 
                //temp.next = temp.next.next;//单链表的删除方式
                temp.pre.next = temp.next;
                if (temp.next != null){ 
                    temp.next.pre = temp.pre;
                }
            }else { 
                System.out.printf("要删除的%d节点不存在\n",no);
            }
        }
        //=========================显示方法=======================================
        //显示链表
        public void list(){ 
            if (head.next == null){ 
                System.out.println("链表为空");
                return;
            }
            //如果链表不为空，则需要一个辅助变量帮助遍历
            HeroNode2 temp = head.next;
            while (true){ 
                if (temp == null){ 
                    break;
                }
                //如果temp不为空，则输入节点信息即可
                System.out.println(temp);
                //将temp后移，否则死循环
                temp = temp.next;
            }
        }
    }
    //================================================================
    //定义HeroNode类，每一个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.no = no;
            this.name = name;
            this.nickname = nickname;
        }
        //方便显示
        @Override
        public String toString() { 
            return "HeroNode{" +
                    "no=" + no +
                    ", name='" + name + '\'' +
                    ", nickname='" + nickname + '\'' +
                    '}';
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JlYWxpemVfZHJlYW0_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JlYWxpemVfZHJlYW0_size_16_color_FFFFFF_t_70]: /images/20221124/27c7c5c3aef741cba0ee271d39b68760.png