java实现双向链表的增删改

双向链表是一种经常用于数据结构的数据类型，它允许在两个方向上遍历链表的节点，即从头部向尾部或从尾部向头部。在Java中实现双向链表，需要用到链表节点类和链表类。链表节点类包含了节点自身的数据以及向前向后两个方向的指针，链表类则包含了链表的头部和尾部节点指针，以及对链表节点的增删改查方法。

1. 链表节点类的实现

链表节点类包含了三个属性：前向指针prev、后向指针next和节点值value。其中前向指针和后向指针都是链表节点类的引用类型。

public class Node {
    public Node prev;
    public Node next;
    public int value;
    
    public Node(int value) {
        this.value = value;
    }
    
}

2. 链表类的实现

链表类包含了两个属性：头部节点head和尾部节点tail，以及4个操作方法：在头部插入节点、在尾部插入节点、删除指定节点、根据索引查找节点。

public class DoublyLinkedList {
    private Node head;
    private Node tail;
    
    public DoublyLinkedList() {
        this.head = null;
        this.tail = null;
    }
    
    // 在头部插入节点
    public void addFirst(int value) {
        Node newNode = new Node(value);
        if(head == null) {
            head = newNode;
            tail = newNode;
        } else {
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        }
    }
    
    // 在尾部插入节点
    public void addLast(int value) {
        Node newNode = new Node(value);
        if(tail == null) {
            head = newNode;
            tail = newNode;
        } else {
            tail.next = newNode;
            newNode.prev = tail;
            tail = newNode;
        }
    }
    
    // 删除指定节点
    public void remove(int value) {
        Node current = head;
        while(current != null) {
            if(current.value == value) {
                if(current == head) {
                    head = current.next;
                    if(head != null) {
                        head.prev = null;
                    }
                } else if(current == tail) {
                    tail = current.prev;
                    if(tail != null) {
                        tail.next = null;
                    }
                } else {
                    current.prev.next = current.next;
                    current.next.prev = current.prev;
                }
            }
            current = current.next;
        }
    }
    
    // 根据索引查找节点
    public Node getNode(int index) {
        if(head == null || index < 0) {
            return null;
        }
        
        Node current = head;
        int i = 0;
        while(i < index && current != null) {
            current = current.next;
            i++;
        }
        
        return current;
    }
}

在增删改方面，双向链表的操作与单向链表类似，最大的区别是增加了对前向指针的处理。例如，在头部插入节点时，需要将新节点的后向指针指向头部节点，将头部节点的前向指针指向新节点，然后将头部指针指向新节点即可。

// 在头部插入节点
public void addFirst(int value) {
    Node newNode = new Node(value);
    if(head == null) {
        head = newNode;
        tail = newNode;
    } else {
        newNode.next = head;
        head.prev = newNode;
        head = newNode;
    }
}

在尾部插入节点时，需要将新节点的前向指针指向尾部节点，将尾部节点的后向指针指向新节点，然后将尾部指针指向新节点即可。

// 在尾部插入节点
public void addLast(int value) {
    Node newNode = new Node(value);
    if(tail == null) {
        head = newNode;
        tail = newNode;
    } else {
        tail.next = newNode;
        newNode.prev = tail;
        tail = newNode;
    }
}

在删除指定节点时，需要根据节点是否在头部或者尾部做特殊处理，如果节点处于中间位置，则需要修改前向和后向节点的指针即可。

// 删除指定节点
public void remove(int value) {
    Node current = head;
    while(current != null) {
        if(current.value == value) {
            if(current == head) {
                head = current.next;
                if(head != null) {
                    head.prev = null;
                }
            } else if(current == tail) {
                tail = current.prev;
                if(tail != null) {
                    tail.next = null;
                }
            } else {
                current.prev.next = current.next;
                current.next.prev = current.prev;
            }
        }
        current = current.next;
    }
}

在查找指定节点时，只需要从头部节点开始遍历，将遍历到的节点与目标节点做比较即可。需要注意的是，如果链表为空或者索引小于0，需要返回null。

// 根据索引查找节点
public Node getNode(int index) {
    if(head == null || index < 0) {
        return null;
    }
    
    Node current = head;
    int i = 0;
    while(i < index && current != null) {
        current = current.next;
        i++;
    }
    
    return current;
}

综上，Java实现双向链表的增删改需要实现链表节点类和链表类，并且需要特别注意前向指针的处理。双向链表的优势在于可以从头向尾和从尾向头两个方向遍历链表，这种遍历方式在一些特定场景下非常有用，例如使用LRU缓存算法实现最近最少使用页面置换。