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

双向链表

双向链表的定义

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

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

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

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

完整的双向链表

双向链表的功能

• 增

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

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

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

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

    

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

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

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

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

    

• 删

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

    注意：被删除的节点称之为：野节点，这并不是真正意义上的删除，它在内存中依旧存在。那么野节点的最终归宿是被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