双向链表反向遍历实现及排序后元素删除与展示问题咨询

1. Implement Reverse Traversal & Print #

双向链表的反向遍历核心就是利用每个节点的prev指针，从tail节点出发，一步步往前跳转直到遍历完所有节点。首先得确保你的链表节点结构包含prev和next指针，并且tail指针始终正确指向链表的最后一个节点。

给你举个C++的实现例子（如果用Java/其他语言，逻辑完全一致，只是语法调整）：

// 先定义节点结构
struct Node {
    int data;
    Node* prev;
    Node* next;
    Node(int val) : data(val), prev(nullptr), next(nullptr) {}
};

// 反向遍历打印函数
void printReverse(Node* tail) {
    if (tail == nullptr) {
        cout << "List is empty!" << endl;
        return;
    }
    Node* current = tail;
    cout << "Reverse traversal result: ";
    while (current != nullptr) {
        cout << current->data << " ";
        current = current->prev; // 跳转到前一个节点
    }
    cout << endl;
}

2. Implement Element Deletion in Sorted Doubly Linked List #

排序后的链表删除元素，核心是先定位目标节点，再调整前后节点的指针关系，同时要处理三种边界情况：删除头节点、删除尾节点、删除中间节点。步骤拆解如下：

1. 遍历链表找到要删除的节点（因为链表已排序，也可以用二分查找优化，小链表线性查找足够）
2. 如果没找到目标，提示元素不存在
3. 根据节点位置调整指针：
   • 若为头节点：更新head为原头的next，新head的prev设为null；如果链表只剩这一个节点，tail也要置空
   • 若为尾节点：更新tail为原尾的prev，新tail的next设为null
   • 若为中间节点：让前节点的next指向当前节点的next，后节点的prev指向当前节点的prev
4. 释放目标节点的内存（Java等语言自动回收，C++手动释放）

C++实现示例（封装成链表类更清晰）：

class DoublyLinkedList {
public:
    Node* head;
    Node* tail;
    DoublyLinkedList() : head(nullptr), tail(nullptr) {}

    // 删除指定值的元素
    void deleteElement(int val) {
        Node* current = head;
        // 查找目标节点
        while (current != nullptr && current->data != val) {
            current = current->next;
        }
        if (current == nullptr) {
            cout << "Element " << val << " not found in the list!" << endl;
            return;
        }

        // 处理三种边界情况
        if (current == head) {
            head = head->next;
            if (head != nullptr) {
                head->prev = nullptr;
            } else {
                // 链表为空了，tail也要置空
                tail = nullptr;
            }
        } else if (current == tail) {
            tail = tail->prev;
            tail->next = nullptr;
        } else {
            current->prev->next = current->next;
            current->next->prev = current->prev;
        }

        delete current; // 释放内存
        cout << "Element " << val << " deleted successfully!" << endl;
    }
};

3. Display Content After Deletion #

删除元素后，直接调用你已经实现的正向遍历打印函数，或者上面的反向打印函数，就能展示当前链表的内容了。比如删除后执行：

// 正向打印函数（你已实现，这里贴出来参考）
void printForward(Node* head) {
    if (head == nullptr) {
        cout << "List is empty!" << endl;
        return;
    }
    Node* current = head;
    cout << "Forward traversal result: ";
    while (current != nullptr) {
        cout << current->data << " ";
        current = current->next;
    }
    cout << endl;
}

// 删除后调用展示
DoublyLinkedList dll;
// 假设已经完成排序操作
dll.deleteElement(5);
dll.printForward(dll.head);
dll.printReverse(dll.tail);

Key Reminders #

• 操作链表时一定要检查nullptr（或null），避免空指针异常
• 排序后的链表如果数据量较大，可以用二分查找优化目标节点的定位
• 修改head或tail指针后，务必确认它们的指向正确，比如删除最后一个节点时，tail必须置空

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