双向链表

ゝ一世哀愁。 2022-11-05 12:57 195阅读 0赞

# 一：双向链表 #

双向链表的节点包含数据域，前置指针域和后置指针域

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70][]

双向链表的增删查改代码实现：

DoubleHeroNode实体类

package com.doublelinklist;
    
    /**
     * @author lizhangyu
     * @date 2021/3/6 16:28
     */
    public class DoubleHeroNode {
    
        public int no;
        public String name;
    
        public DoubleHeroNode next;
        public DoubleHeroNode pre;
    
        public DoubleHeroNode(int no, String name) {
            this.no = no;
            this.name = name;
        }
    
        @Override
        public String toString() {
            return "HeroNode{" +
                    "no=" + no +
                    ", name='" + name + '\'' +
                    '}';
        }
    }

DoubleLinkList实体类

package com.doublelinklist;
    
    /**
     * @author lizhangyu
     * @date 2021/3/6 16:30
     */
    public class DoubleLinkList {
    
        DoubleHeroNode head = new DoubleHeroNode(0, "");
    
        /**
         * 遍历
         */
        public void list() {
            if (head.next == null) {
                System.out.println("链表为空");
                return;
            }
    
            DoubleHeroNode cur = head.next;
    
            while (true) {
                System.out.println(cur);
                if (cur.next == null) {
                    break;
                }
                cur = cur.next;
            }
    
        }
    
        /**
         * 添加
         * @param node
         */
        public void add(DoubleHeroNode node) {
            DoubleHeroNode cur = head;
            while (true) {
                if (cur.next == null) {
                    break;
                }
                cur = cur.next;
            }
            cur.next = node;
            node.pre = cur;
        }
    
        /**
         * 查找
         * @param no
         */
        public DoubleHeroNode find(int no) {
            DoubleHeroNode cur = head.next;
            if (cur == null) {
                System.out.println("链表为空");
                return null;
            }
    
            while (true) {
                if (cur.no == no) {
                    System.out.println("找到对应的节点:" + cur);
                    return cur;
                }
    
                if (cur.next == null) {
                    System.out.println("没有找到对应的节点");
                    break;
                }
    
                cur = cur.next;
            }
    
            return null;
        }
    
        /**
         * 修改
         * @param node
         */
        public void update(DoubleHeroNode node) {
            DoubleHeroNode oldNode = find(node.no);
            if (oldNode != null) {
                oldNode.name = node.name;
            }else {
                System.out.println("由于没有找到对应的节点，所以不能修改");
            }
        }
    
        /**
         * 删除
         * @param node
         */
        public void delete(DoubleHeroNode node) {
            DoubleHeroNode cur = head;
            Boolean flag = false;
            while (true) {
                if (cur.next == null) {
                    System.out.println("链表为空");
                    break;
                }
    
                if (cur.next.no == node.no) {
                    flag = true;
                    break;
                }
    
                cur = cur.next;
            }
    
            if (flag) {
                cur.next = cur.next.next;
                //避免是最后一个节点，从而出现空指针异常
                if (cur.next.next != null) {
                    cur.next.next.pre = cur.next.pre;
                }
                System.out.println("成功删除节点");
            }else {
                System.out.println("没有找到对应的节点");
            }
        }
    
    }

DoubleLinkListDemo实体类

package com.doublelinklist;
    
    /**
     * @author lizhangyu
     * @date 2021/3/6 16:43
     */
    public class DoubleLinkListDemo {
        public static void main(String[] args) {
            //先创建节点
            DoubleHeroNode hero1 = new DoubleHeroNode(1, "宋江");
            DoubleHeroNode hero2 = new DoubleHeroNode(2, "卢俊义");
            DoubleHeroNode hero3 = new DoubleHeroNode(3, "吴用");
            DoubleHeroNode hero4 = new DoubleHeroNode(4, "林冲");
            DoubleLinkList singleLinkList = new DoubleLinkList();
            singleLinkList.add(hero1);
            singleLinkList.add(hero2);
            singleLinkList.add(hero3);
            singleLinkList.add(hero4);
            System.out.println("添加之后的链表为:");
            singleLinkList.list();
            System.out.println("查找编号为1的员工:");
            singleLinkList.find(1);
            singleLinkList.list();
            System.out.println("查找编号为5的员工:");
            singleLinkList.find(5);
            singleLinkList.list();
            DoubleHeroNode hero5 = new DoubleHeroNode(4, "林冲1");
            System.out.println("修改员工信息:");
            singleLinkList.update(hero5);
            singleLinkList.list();
            System.out.println("删除员工信息:");
            singleLinkList.delete(hero2);
            singleLinkList.list();
        }
    }

测试的结果：

添加之后的链表为:
    HeroNode{no=1, name='宋江'}
    HeroNode{no=2, name='卢俊义'}
    HeroNode{no=3, name='吴用'}
    HeroNode{no=4, name='林冲'}
    查找编号为1的员工:
    找到对应的节点:HeroNode{no=1, name='宋江'}
    HeroNode{no=1, name='宋江'}
    HeroNode{no=2, name='卢俊义'}
    HeroNode{no=3, name='吴用'}
    HeroNode{no=4, name='林冲'}
    查找编号为5的员工:
    没有找到对应的节点
    HeroNode{no=1, name='宋江'}
    HeroNode{no=2, name='卢俊义'}
    HeroNode{no=3, name='吴用'}
    HeroNode{no=4, name='林冲'}
    修改员工信息:
    找到对应的节点:HeroNode{no=4, name='林冲'}
    HeroNode{no=1, name='宋江'}
    HeroNode{no=2, name='卢俊义'}
    HeroNode{no=3, name='吴用'}
    HeroNode{no=4, name='林冲1'}
    删除员工信息:
    成功删除节点
    HeroNode{no=1, name='宋江'}
    HeroNode{no=3, name='吴用'}
    HeroNode{no=4, name='林冲1'}
    
    Process finished with exit code 0

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70]: /images/20221023/1171aec3f3594a818144d845e249f402.png