（四）Java数据结构之双链表

我不是女神ヾ 2022-12-13 01:39 150阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWt1bmxvbmc_size_16_color_FFFFFF_t_70][]

其实和单链表差不多，以下代码实现了增删改查：

package top.baikunlong.linkedlist;
    
    /**
     * @author baikunlong
     * @date 2020/10/9 10:56
     */
    public class DoubleLinkedList {
    
        public Node2 head = new Node2(0, "头节点");
    
        /**
         * 在最后添加节点
         *
         * @param node
         */
        public void add(Node2 node) {
            //首先找到最后个节点
            Node2 temp = head;//头节点不能移动，需要临时变量
            while (true) {
                if (temp.next == null) {//如果是最后个则添加
                    temp.next = node;
                    node.pre = temp;//设置前一个节点
                    break;
                } else {
                    temp = temp.next;//否则移动到下一个节点
                }
            }
        }
        /**
         * 根据no删除
         *
         * @param no
         */
        public void deleteByNo(int no) {
            if (head.next == null) {
                System.out.println("链表为空");
                return;
            }
            Node2 temp = this.head.next;//直接自身移除，不需要像单链表那样依赖前一个节点
            while (true) {
                if (temp == null) {
                    System.out.printf("节点为 no=%d 不存在\n", no);
                    return;
                }
                if (temp.no == no) {
                    temp.pre.next=temp.next;//前一个的next指向temp的next
                    //如果删除的是最后一个，next为空，就不能指定pre了
                    if(temp.next!=null){
                        temp.next.pre=temp.pre;//后一个的pre指向temp的pre
                    }
                    return;
                }
                temp = temp.next;
            }
        }
        /**
         * 根据no更新
         *
         * @param node
         */
        public void updateByNo(Node2 node) {
            Node2 temp = this.head.next;
            while (true) {
                if (temp == null) {
                    System.out.printf("节点为 no=%d 不存在\n", node.no);
                    return;
                } else if (temp.no == node.no) {
                    temp.name = node.name;
                    return;
                }
                temp = temp.next;
            }
        }
        /**
         * 根据no获取
         *
         * @param no
         * @return
         */
        public Node2 getNodeByNo(int no) {
            Node2 temp = this.head.next;
            while (true) {
                if (temp == null) {
                    throw new RuntimeException("节点为 no=" + no + " 不存在");
                } else if (temp.no == no) {
                    return temp;
                }
                temp = temp.next;
            }
        }
        /**
         * 打印链表
         */
        public void list() {
            if (head.next == null) System.out.println("链表为空");
            Node2 temp = head.next;
            while (true) {
                if (temp == null) {
                    break;
                } else {
                    System.out.println(temp.toString());
                    temp = temp.next;
                }
            }
        }
    
        public static void main(String[] args) {
            DoubleLinkedList list = new DoubleLinkedList();
            list.add(new Node2(1,"111"));
            list.add(new Node2(2,"222"));
            Node2 node3 = new Node2(3, "333");
            list.add(node3);
            list.add(new Node2(4,"444"));
            list.list();
            list.deleteByNo(1);
            System.out.println("删除1");
            list.list();
            list.deleteByNo(5);
            System.out.println("删除5");
            list.list();
            node3.name="修改过得333";
            list.updateByNo(node3);
            System.out.println("修改333");
            list.list();
            System.out.println("寻找2：");
            System.out.println(list.getNodeByNo(2));
            System.out.println("寻找22：");
            System.out.println(list.getNodeByNo(22));
        }
    }
    /**
     * 节点类
     */
    class Node2 {
        public int no;
        public String name;
        public Node2 next;
        public Node2 pre;
    
        public Node2(int no, String name) {
            this.no = no;
            this.name = name;
        }
    
        @Override
        public String toString() {
            return "Node{" +
                    "no=" + no +
                    ", name='" + name + '\'' +
                    '}';
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWt1bmxvbmc_size_16_color_FFFFFF_t_70]: /images/20221123/4ebede217dbb4c808ee4ddd0ae13bfe7.png