如何高效将链表删除节点存入栈并实现撤销恢复操作？

要实现从LinkedList删除节点后存入栈，后续能撤销恢复到原位置，核心是记录删除节点的上下文信息（前驱、后继节点），而非仅存节点本身。你当前用ArrayList的方式无法满足精准恢复需求，因为ArrayList是数组结构，删除后元素位置会偏移，且无法直接获取节点的前后关联。以下是基于双向链表的实现方案：

核心思路 #

• 用双向链表存储数据，便于直接操作节点的前驱(prev)和后继(next)指针
• 定义一个栈，栈中存储的不是单个节点，而是包含「被删节点、前驱节点、后继节点」的上下文对象，确保恢复时能精准还原节点位置
• 删除节点时，将上下文信息压入栈；撤销时弹出栈顶上下文，重新建立节点的前后连接

完整实现代码 #

package DataStructure.LinkedListPractise;

import java.util.Stack;

// 自定义双向链表节点
class ListNode {
    int val;
    ListNode prev;
    ListNode next;

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

// 自定义带撤销功能的双向链表
class UndoableLinkedList {
    private ListNode head;
    private ListNode tail;
    // 存储删除操作的上下文：被删节点、前驱、后继
    private Stack<DeleteContext> undoStack;

    // 记录删除上下文的内部类
    private static class DeleteContext {
        ListNode deletedNode;
        ListNode prevNode;
        ListNode nextNode;

        public DeleteContext(ListNode deletedNode, ListNode prevNode, ListNode nextNode) {
            this.deletedNode = deletedNode;
            this.prevNode = prevNode;
            this.nextNode = nextNode;
        }
    }

    public UndoableLinkedList() {
        this.head = null;
        this.tail = null;
        this.undoStack = new Stack<>();
    }

    // 添加节点到链表尾部
    public void add(int val) {
        ListNode newNode = new ListNode(val);
        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            tail.next = newNode;
            newNode.prev = tail;
            tail = newNode;
        }
    }

    // 根据索引删除节点，并将上下文存入栈
    public boolean delete(int index) {
        ListNode current = head;
        int currentIndex = 0;

        // 找到目标节点
        while (current != null && currentIndex < index) {
            current = current.next;
            currentIndex++;
        }

        if (current == null) {
            return false; // 索引无效，删除失败
        }

        ListNode prev = current.prev;
        ListNode next = current.next;

        // 从链表中移除当前节点
        if (prev == null) {
            // 删除的是头节点
            head = next;
        } else {
            prev.next = next;
        }

        if (next == null) {
            // 删除的是尾节点
            tail = prev;
        } else {
            next.prev = prev;
        }

        // 将删除上下文压入栈
        undoStack.push(new DeleteContext(current, prev, next));
        return true;
    }

    // 撤销最后一次删除操作，恢复节点到原位置
    public boolean undoDelete() {
        if (undoStack.isEmpty()) {
            return false; // 没有可撤销的操作
        }

        DeleteContext context = undoStack.pop();
        ListNode deletedNode = context.deletedNode;
        ListNode prev = context.prevNode;
        ListNode next = context.nextNode;

        // 恢复节点的前后连接
        deletedNode.prev = prev;
        deletedNode.next = next;

        if (prev == null) {
            // 恢复的是头节点
            head = deletedNode;
        } else {
            prev.next = deletedNode;
        }

        if (next == null) {
            // 恢复的是尾节点
            tail = deletedNode;
        } else {
            next.prev = deletedNode;
        }

        return true;
    }

    // 打印链表所有元素
    public void printList() {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val + " ");
            current = current.next;
        }
        System.out.println();
    }
}

public class PractiseLinkedList {
    public static void main(String[] args) {
        UndoableLinkedList list = new UndoableLinkedList();
        list.add(32);
        list.add(388);
        list.add(129);

        System.out.println("初始链表:");
        list.printList();

        // 删除索引1的节点（值为388）
        list.delete(1);
        System.out.println("删除节点后链表:");
        list.printList();

        // 撤销删除操作
        list.undoDelete();
        System.out.println("撤销后链表:");
        list.printList();
    }
}

代码说明 #

• ListNode：自定义双向链表节点，包含值、前驱和后继指针
• DeleteContext：内部类，存储删除操作的关键上下文，确保恢复时能精准还原节点位置
• UndoableLinkedList：封装了添加、删除、撤销、打印方法，内部维护栈来记录删除操作
• 撤销操作时，直接从栈中取出上下文，重新建立节点的前后连接，时间复杂度为O(1)，效率很高

内容的提问来源于stack exchange，提问作者sarim nadeem