数据结构-链表结构-双向链表

文章目录

• 双向链表
• • 双向链表的定义
  • 双向链表的功能
  • 特点
  • 单向链表和双向链表的区别
  • • MyList
    • MyDoubleLinkedList
    • 测试

双向链表

双向链表的定义

双向链表也叫双链表，与单向链表不同的是，每一个节点有三个区域组成：两个指针域，一个数据域

• 前一个指针域：存储前驱节点的内存地址
• 后一个指针域：存储后继节点的内存地址
• 数据域：存储节点数据

以下就是双向链表的最基本单位

节点的前指针域指向前驱，后指针域执行后继

完整的双向链表

双向链表的功能

• 增

  • 向双向链表的尾节点之后添加节点

    • 尾节点的后指针域存储新添加节点的内存地址

    • 新添加节点的前指针域存储尾节点的内存地址

      注意：此时尾节点就是新添加的这个节点

    

  • 向双向链表的首元节点之前添加节点

    • 新添加节点的后指针域存储首元节点的内存地址

    • 首元节点的前指针域存储新添加节点的内存地址

      注意：此时首元节点就是新添加的这个节点

    

• 删

  • 删除中间节点时修改改节点的前驱和后继的指针方向即可

    注意：被删除的节点称之为：野节点，这并不是真正意义上的删除，它在内存中依旧存在。那么野节点的最终归宿是被JVM的GC（垃圾回收器）所回收，也就是释放该节点的内存空间，这才是真正意义上的删除

    额外知识：java中的垃圾回收器（Garbage Collector，GC）负责管理内存的分配和释放。当一个对象没有任何引用指向它时，它就变得不可达，而垃圾回收器会将其标记为垃圾对象，并在适当的时候回收该对象所占用的内存空间。这个过程称为垃圾回收。

    

• 改

  • 挪动指针找到要修改的节点，之后讲修改节点的数据域中的数据修改掉

• 查

  • 挪动指针找到要所要查找的数据。

特点

• 双向性：
  • 每个节点除了存储自己的数据外，还包含两个指针域，分别存储前驱和后继的内存地址，因此可以在链表中向前或向后遍历。
• 动态性：
  • 双向链表可以在运行时动态地添加、删除和修改节点，相对于数组等静态数据结构更加灵活。
• 插入和删除操作高效：
  • 由于双向链表中的节点包含指向前驱和后继的的指针，因此插入和删除操作只需要调整节点前后的指针，而不需要像数组那样移动大量元素。
• 空间利用率较高：
  • 相比单向链表，双向链表需要额外的指针来表示前一个节点，空间利用率略低一些，但在某些情况下方便了一些操作。
• 双向遍历能力：
  • 双向链表可以从任意节点开始向前或向后遍历，这在某些场景中非常有用，例如需要反向迭代链表。

双向链表在内存开销上相对于单向链表稍高。

由于有两个指针，插入和删除操作涉及到更多的指针修改，相对于单向链表略微复杂。

单向链表和双向链表的区别

单向链表相对于双向链表更简单且节省内存，适用于对内存占用敏感且只需要单向遍历的情况。

而双向链表由于具有双向遍历的能力，适用于需要频繁插入、删除和反向遍历的场景。

在选择使用哪种链表结构时，应根据具体需求权衡其优缺点。

MyList

public interface MyList<E> {
    //添加节点数据
    void add(E element);

    //获取节点数据
    E get (int index);

    //获取链表长度
    int size();

    //根据指针移除节点
    E remove(int index);

    //从头添加元素
    void addFirst(E element);
    
    //从尾添加元素
    void addLast(E element);
}

MyDoubleLinkedList

public class MyDoubleLinkedList<E> implements MyList<E> {

    private int size;//记录元素的个数

    private Node head ;// 记录头节点

    private Node tail;//记录尾节点
    /**
     * 向双向链表中添加元素数据
     * @param element
     */
    @Override
    public void add(E element) {
        this.linkLast(element);
    }

    /**
     * 将节点对象添加到双向链表的尾部
     * @param element
     */
    private void linkLast(E element){
        //获取尾节点
        Node t = this.tail;
        Node<E> node = new Node<>(t,element,null);

        //将新节点定义为尾节点
        this.tail = node;
        if (t == null){//当t等于空的时候说明这个链表是个空链表
            this.head=node;//将向的元素数据赋值到头节点
        }else{
            t.next=node;//否则将新元素赋值到尾节点之后
        }
        this.size++;//添加成功长度自增加一

    }


    /**
     * 根据指针获取对应的元素数据
     * @param index
     * @return
     */
    @Override
    public E get(int index) {
        //对index做合法性校验
        this.rangeCheck(index);
        Node<E> node = this.getNode(index);
        return node.item;
    }

    /**
     * 判断当前index的合法性
     */
    private void rangeCheck(int index){
        if(!(index >=0 && index < this.size)){
            int a = this.size-1;
            throw new IndexOutOfBoundsException("您输入的索引为："+index+"它的指针长度为："+a);
        }
    }

    /**
     * 根据位置获取指定的节点对象
     * @param index
     * @return
     */
    private Node getNode(int index){
        //判断当前输入的指针距离头或者尾哪个节点近
        //如果输入的指针大，从尾部开始找，
        //如果输入的指针小，从头部开始找

        if (index < (this.size >> 1)){
            Node node = this.head;
            //遍历指针
            for(int i =0; i < index;i++){
                //拿到指针处的下一个节点对象赋值node
                node=node.next;
            }
            return node;
        }else {
            Node node = this.tail;
            //从尾节点找指针
            for (int i = this.size-1; i>index; i--){
                node = node.prev;
            }
            return node;
        }
    }

    /**
     * 获取元素的长度（个数）
     * @return
     */
    @Override
    public int size() {
        return this.size;
    }

    /**
     * 根据指定指针删除元素
     * @param index
     * @return
     */
    @Override
    public E remove(int index) {
        //对index指针进行合法性校验
        this.rangeCheck(index);

        //根据index进行获取节点对象，判断从头删还是从尾部删除
        Node<E> node = this.getNode(index);

        //获取index指针处的节点元素数据
        E item = node.item;

        //判断当前节点是否尾头节点
        if (node.prev == null){
            this.head = node.next;
        }else {
            //完成当前节点的直接前驱节点和当前节点的直接后继节点，挂接
            node.prev.next = node.next;
        }
        //当前节点断掉与它直接前驱点的连接
        node.prev = null;
        //当前节点断掉与他直接后继节点的连接
        node.next =null;
        node.item =null;

        //长度自减一
        this.size--;

        //返回被删除的节点元素数据
        return item;
    }

    //从头开始添加元素
    @Override
    public void addFirst(E element) {
        this.linkFirst(element);
    }

    //从尾部添加元素
    @Override
    public void addLast(E element) {
        this.linkLast(element);
    }






    //在链表的头添加元素
    private void linkFirst(E element){
        //获取头节点对象
        Node head = this.head;
        Node node = new Node(null,element,head);

        //将新节点定义为头节点
        this.head = node;

        //判断当前链表中是否有节点，如果没有该节则是头节点也是尾节点
        if(this.head == null){
            this.tail = node;
        }else {
            this.head.prev = node;
        }
        this.size++;//记录链表长度

    }

    /**
     * 创建节点类
     * @param <E>
     */
    class Node<E> {
        private E item;//记录元素
        private Node<E> next; // 下一个节点对象
        private Node<E> prev; // 上一个节点对象

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
}

测试

public class MyLinkedMain {
    public static void main(String[] args) {
        MyDoubleLinkedList linkedList = new MyDoubleLinkedList();

        linkedList.add(12);
        linkedList.add(13);
        linkedList.add(14);
        linkedList.add(15);
        linkedList.add(16);
        System.out.println(linkedList.get(3));//3是指针，从尾部开始找
        System.out.println(linkedList.get(4));//4是指针，从尾部开始找
        System.out.println(linkedList.get(1));//1是指针，从头部开始找
        System.out.println(linkedList.size());//获取linkedList长度
        System.out.println("删除前的指针1处的数据"+linkedList.get(1));
        System.out.println(linkedList.remove(1));
        System.out.println("删除后的指针1处的数据"+linkedList.get(1));

        System.out.println("删除前的指针0处的数据"+linkedList.get(4));
        System.out.println(linkedList.remove(4));
        try {
            System.out.println("删除后的指针0处的数据"+linkedList.get(4));

        }catch (Exception e) {
            e.printStackTrace();
        }finally {
            System.out.println("删除后的链表长度"+linkedList.size());//获取linkedList长度
        }
    }
}