双向链表的建立和使用场景

双向链表（Doubly Linked List）是一种常见的数据结构，它在链表的基础上增加了一个指向前一个节点的指针，这使得在双向链表中可以方便地进行双向遍历。

创建双向链表的步骤：

定义节点类：首先，定义一个节点类，这个节点类通常包含三个属性：数据域（存储数据的部分）、指向下一个节点的指针（通常称为next或forward），以及指向前一个节点的指针（通常称为prev或backward）。

//定义一个节点类
public class Node {
    //数据域
    int data;
    //指向下一个节点的指针
    Node next;
    //指向前一个节点的指针
    Node prev;
    
    public Node(int data) {
        this.data=data;
        this.next=null;
        this.prev=null;
    }
}

创建链表：创建一个链表对象，通常包括一个指向链表头部和尾部的指针。该类包含链表的操作方法，如添加节点、删除节点等。

public class DoublyLinkedList {
    //创建一个链表对象，通常包括一个指向链表头部和尾部的指针
    private Node head;
    private Node tail;
    public DoublyLinkedList() {
        this.head=null;
        this.tail=null;
    }
    //添加节点
    public void append(int data) {
        Node newNode=new Node(data);
        if (tail==null) {
            head=newNode;
            tail=newNode;
        }else {
            //更新 prev 和 next 指针
            tail.next=newNode;
            newNode.prev=tail;
            tail=newNode;
        }
    }
    public void display() {
        Node current=head;
        while(current!=null) {
            System.out.print(current.data+"<->");
            current=current.next;
        }
        System.out.println("null");
    }
    //删除节点
    public void remove(int target) {
        Node current=head;
        while(current!=null) {
            if(current.data==target) {
                //更新相邻节点的指针
                //如果当前结点为头结点，将头结点引用指向下一个
                if(current.prev!=null) {
                    current.prev.next=current.next;
                }else {
                    head=current.next;
                }
                //如果当前结点为尾结点,将尾结点引用指向上一个
                if(current.next!=null) {
                    current.next.prev=current.prev;
                }else {
                    tail=current.prev;
                }
                return;
            }
            current=current.next;
        }
        System.out.println("没找到该结点");
    }
}

链表的使用：添加结点以及删除结点

public class Test {

    public static void main(String[] args) {
        DoublyLinkedList linkedList=new DoublyLinkedList();
        //添加四个结点
        linkedList.append(1);
        linkedList.append(2);
        linkedList.append(3);
        linkedList.append(4);
        linkedList.display();//1<->2<->3<->4<->null
        linkedList.remove(3);
        linkedList.display();//1<->2<->4<->null
    }
}

适用场景：

1. 双向遍历：由于双向链表具有前向和后向指针，可以方便地进行双向遍历，这在某些算法和数据结构操作中很有用。

2. 插入和删除：插入和删除节点的操作在双向链表中通常比单链表更高效，因为它不需要在删除节点时回溯到前一个节点。

3. LRU缓存：双向链表常用于实现LRU（Least Recently Used）缓存淘汰策略，其中最近使用的元素移动到链表的尾部，最不常用的元素位于链表的头部，当缓存满时，可以轻松删除链表头部的元素。

4. 编辑器和浏览器历史：双向链表可以用于实现文本编辑器的撤销和重做功能，以及浏览器历史记录的前进和后退功能，因为用户可以在双向链表中导航到前一个和后一个状态。

总之，双向链表在需要双向遍历、频繁插入和删除节点或实现某些特定数据结构时非常有用。然而，由于它需要额外的指针来维护前向链接，可能会占用更多的内存空间。所以在选择数据结构时，需要根据具体需求权衡其优点和缺点。