java实现双向链表的增删改

Java语言中实现双向链表的增删改可以通过以下步骤进行。

一、创建双向链表节点类

首先，需要创建一个双向链表节点类，该类包含节点值以及指向前驱节点和后继节点的指针。以下是该类的代码实现。

public class DoublyListNode {
    public int val;
    public DoublyListNode prev;
    public DoublyListNode next;

    public DoublyListNode(int val) {
        this.val = val;
        this.prev = null;
        this.next = null;
    }
}

二、双向链表的插入操作

1.头部插入

头部插入操作比较简单，只需要将新节点的后继指针指向链表的头节点，而原来的头节点的前驱指针指向新节点即可。以下是头部插入的示例代码实现。

public void insertAtHead(int val) {
    DoublyListNode newNode = new DoublyListNode(val);
    if (head == null) {
        tail = newNode;
    } else {
        head.prev = newNode;
    }
    newNode.next = head;
    head = newNode;
}

2.尾部插入

尾部插入操作也比较简单，只需要将新节点的前驱指针指向链表的尾节点，而原来的尾节点的后继指针指向新节点即可。以下是尾部插入的示例代码实现。

public void insertAtTail(int val) {
    DoublyListNode newNode = new DoublyListNode(val);
    if (tail == null) {
        head = newNode;
    } else {
        tail.next = newNode;
    }
    newNode.prev = tail;
    tail = newNode;
}

3.任意位置插入

任意位置插入操作比较复杂，需要先找到要插入位置的前驱节点和后继节点，然后进行指针的修改。以下是任意位置插入的示例代码实现。

public void insertAtPos(int val, int pos) {
    DoublyListNode newNode = new DoublyListNode(val);
    if (pos <= 0) {
        insertAtHead(val);
    } else {
        DoublyListNode curr = head;
        for (int i = 0; i < pos - 1 && curr != null; i++) {
            curr = curr.next;
        }
        if (curr == null) {
            insertAtTail(val);
        } else {
            newNode.prev = curr;
            newNode.next = curr.next;
            curr.next = newNode;
            newNode.next.prev = newNode;
        }
    }
}

三、双向链表的删除操作

1.头部删除

头部删除操作比较简单，只需要将头节点的后继节点的前驱指针指向空，再将头指针指向后继节点即可。以下是头部删除的示例代码实现。

public void deleteAtHead() {
    if (head == null) {
        return;
    }
    head = head.next;
    if (head == null) {
        tail = null;
    } else {
        head.prev = null;
    }
}

2.尾部删除

尾部删除操作也比较简单，只需要将尾节点的前驱节点的后继指针指向空，再将尾指针指向前驱节点即可。以下是尾部删除的示例代码实现。

public void deleteAtTail() {
    if (tail == null) {
        return;
    }
    tail = tail.prev;
    if (tail == null) {
        head = null;
    } else {
        tail.next = null;
    }
}

3.任意位置删除

任意位置删除操作比较复杂，需要先找到要删除的节点，然后进行指针的修改。以下是任意位置删除的示例代码实现。

public void deleteAtPos(int pos) {
    if (pos <= 0) {
        deleteAtHead();
    } else {
        DoublyListNode curr = head;
        for (int i = 0; i < pos && curr != null; i++) {
            curr = curr.next;
        }
        if (curr == null) {
            return;
        }
        if (curr == head) {
            deleteAtHead();
        } else if (curr == tail) {
            deleteAtTail();
        } else {
            curr.prev.next = curr.next;
            curr.next.prev = curr.prev;
        }
    }
}

四、双向链表的修改操作

双向链表的修改操作比较简单，只需要找到要修改的节点，然后修改节点的值即可。以下是修改节点的示例代码实现。

public void modify(int val, int pos) {
    DoublyListNode curr = head;
    for (int i = 0; i < pos && curr != null; i++) {
        curr = curr.next;
    }
    if (curr != null) {
        curr.val = val;
    }
}

五、完整示例代码

public class DoublyList {

    private DoublyListNode head;
    private DoublyListNode tail;

    public DoublyList() {
        head = null;
        tail = null;
    }

    public void insertAtHead(int val) {
        DoublyListNode newNode = new DoublyListNode(val);
        if (head == null) {
            tail = newNode;
        } else {
            head.prev = newNode;
        }
        newNode.next = head;
        head = newNode;
    }

    public void insertAtTail(int val) {
        DoublyListNode newNode = new DoublyListNode(val);
        if (tail == null) {
            head = newNode;
        } else {
            tail.next = newNode;
        }
        newNode.prev = tail;
        tail = newNode;
    }

    public void insertAtPos(int val, int pos) {
        DoublyListNode newNode = new DoublyListNode(val);
        if (pos <= 0) {
            insertAtHead(val);
        } else {
            DoublyListNode curr = head;
            for (int i = 0; i < pos - 1 && curr != null; i++) {
                curr = curr.next;
            }
            if (curr == null) {
                insertAtTail(val);
            } else {
                newNode.prev = curr;
                newNode.next = curr.next;
                curr.next = newNode;
                newNode.next.prev = newNode;
            }
        }
    }

    public void deleteAtHead() {
        if (head == null) {
            return;
        }
        head = head.next;
        if (head == null) {
            tail = null;
        } else {
            head.prev = null;
        }
    }

    public void deleteAtTail() {
        if (tail == null) {
            return;
        }
        tail = tail.prev;
        if (tail == null) {
            head = null;
        } else {
            tail.next = null;
        }
    }

    public void deleteAtPos(int pos) {
        if (pos <= 0) {
            deleteAtHead();
        } else {
            DoublyListNode curr = head;
            for (int i = 0; i < pos && curr != null; i++) {
                curr = curr.next;
            }
            if (curr == null) {
                return;
            }
            if (curr == head) {
                deleteAtHead();
            } else if (curr == tail) {
                deleteAtTail();
            } else {
                curr.prev.next = curr.next;
                curr.next.prev = curr.prev;
            }
        }
    }

    public void modify(int val, int pos) {
        DoublyListNode curr = head;
        for (int i = 0; i < pos && curr != null; i++) {
            curr = curr.next;
        }
        if (curr != null) {
            curr.val = val;
        }
    }

    class DoublyListNode {
        public int val;
        public DoublyListNode prev;
        public DoublyListNode next;

        public DoublyListNode(int val) {
            this.val = val;
            this.prev = null;
            this.next = null;
        }
    }
}

六、示例说明

以下示例代码演示了如何创建一个双向链表实例并进行插入、删除和修改操作。

public static void main(String[] args) {
    DoublyList list = new DoublyList();
    list.insertAtHead(1);
    list.insertAtHead(2);
    list.insertAtTail(3);
    list.insertAtPos(4, 1);
    list.modify(5, 2);
    list.deleteAtHead();
    list.deleteAtTail();
    list.deleteAtPos(1);
}

在这个示例中，首先创建了一个双向链表实例，然后进行了头部插入、尾部插入、任意位置插入、修改、头部删除、尾部删除和任意位置删除操作。