java双向链表详解

1.概述

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

2.逻辑结构

3.双向链表优点

1. 拥有着前驱和后继，可往前往后遍历，多样化。
2. 在修改和删除时拥有着较好的性能，在查询时也有着不错的速度
3. 可以不需要从头结点开始访问，提高了检索性能

4.双向链表缺点

1. 相较于单向链表，多了一个pre节点占据了更多的空间
2. 因为除了一个data域存数据外，其他两个pre和next域不存放数据，空间利用率低
3. 两个指针在维护时比较麻烦。

5.java代码实现双向链表

5.1 创建节点类

    @Data
    class Person{
        private int no;//编号
        private String name;//名字
        private Person pre;//上一个节点
        private Person next;//下一个节点

        public Person(int no, String name) {
            this.no = no;
            this.name = name;
        }

        @Override
        public String toString() {
            return "Person{" +
                    "no=" + no +
                    ", name='" + name + '\'' +
                    '}';
        }
    }

5.2 创建双向链表类

   class DoubleLinkedList{
        Person head=new Person(0,"");//头结点初始化

        public Person getHead() {
            return head;
        }

        /**
         * 新增节点
         * @param person
         */
        public void add(Person person){
            Person temp=head;
            while (true){
                if (temp.next==null){//到达链表尾返回
                    break;
                }
                temp=temp.next;
            }
            temp.next=person;//将最后一个元素的next域指向person
            person.pre=temp;//将person的pre域指向上一个元素
            System.out.println("添加节点成功");
        }

        /**
         * 遍历节点
         */
        public void list(){
            Person temp=head;
            while (true){
                if (temp.next==null){
                    break;
                }
                System.out.println(temp.next);
                temp=temp.next;
            }
            System.out.println("查询节点完毕");
        }

        /**
         * 删除节点
         * @param person
         */
        public void delete(Person person){
            Person temp=head;
            while (true){
                if (temp.next==null){
                    System.out.println("未找到需要删除的节点");
                    break;
                }
                if (temp.next.no==person.no){
                    temp.next=temp.next.next;
                    if (temp.next.next!=null){
                        temp.next.next.pre=temp;
                    }
                    System.out.println("删除完成");
                    break;
                }
            }
        }

        /**
         * 修改节点
         * @param person
         */
        public void update(Person person){
            Person temp=head;
            while (true){
                if (temp.next==null){
                    System.out.println("未找到需要修改的节点");
                    break;
                }
                if (temp.next.no==person.no){
                    temp.next.name= person.name;
                    System.out.println("修改节点完成");
                    break;
                }
            }
        }
    }

5.3 创建测试方法

    @Test
    public void test(){
        DoubleLinkedList list = new DoubleLinkedList();
        Person person = new Person(1, "赵子龙");
        Person person1 = new Person(2, "刘备");
        Person person2 = new Person(3, "黄忠");
        list.add(person);
        list.add(person1);
        list.add(person2);
        list.list();
        list.delete(person);
        list.list();
        list.update(new Person(2,"马超"));
        list.list();

    }

5.4 测试返回