面试题：C++ 实现自定义双向迭代器并用于自定义链表

#include <iostream>

// 双向链表节点结构
template <typename T>
struct DoublyLinkedListNode {
    T data;
    DoublyLinkedListNode* prev;
    DoublyLinkedListNode* next;
    DoublyLinkedListNode(const T& value) : data(value), prev(nullptr), next(nullptr) {}
};

// 双向链表自定义容器
template <typename T>
class MyDoublyLinkedList {
private:
    DoublyLinkedListNode<T>* head;
    DoublyLinkedListNode<T>* tail;
    size_t size_;

public:
    MyDoublyLinkedList() : head(nullptr), tail(nullptr), size_(0) {}

    ~MyDoublyLinkedList() {
        while (head != nullptr) {
            DoublyLinkedListNode<T>* temp = head;
            head = head->next;
            delete temp;
        }
    }

    void push_back(const T& value) {
        DoublyLinkedListNode<T>* newNode = new DoublyLinkedListNode<T>(value);
        if (tail == nullptr) {
            head = tail = newNode;
        } else {
            newNode->prev = tail;
            tail->next = newNode;
            tail = newNode;
        }
        size_++;
    }

    void push_front(const T& value) {
        DoublyLinkedListNode<T>* newNode = new DoublyLinkedListNode<T>(value);
        if (head == nullptr) {
            head = tail = newNode;
        } else {
            newNode->next = head;
            head->prev = newNode;
            head = newNode;
        }
        size_++;
    }

    void pop_back() {
        if (tail == nullptr) return;
        DoublyLinkedListNode<T>* temp = tail;
        if (tail == head) {
            head = tail = nullptr;
        } else {
            tail = tail->prev;
            tail->next = nullptr;
        }
        delete temp;
        size_--;
    }

    void pop_front() {
        if (head == nullptr) return;
        DoublyLinkedListNode<T>* temp = head;
        if (head == tail) {
            head = tail = nullptr;
        } else {
            head = head->next;
            head->prev = nullptr;
        }
        delete temp;
        size_--;
    }

    size_t size() const {
        return size_;
    }

    // 双向迭代器类
    class MyBidirectionalIterator {
    private:
        DoublyLinkedListNode<T>* current;
        MyDoublyLinkedList<T>* list;

    public:
        MyBidirectionalIterator(DoublyLinkedListNode<T>* node, MyDoublyLinkedList<T>* list) : current(node), list(list) {}

        T& operator*() {
            return current->data;
        }

        MyBidirectionalIterator& operator++() {
            if (current->next == nullptr) {
                current = nullptr; // 表示迭代器无效
            } else {
                current = current->next;
            }
            return *this;
        }

        MyBidirectionalIterator operator++(int) {
            MyBidirectionalIterator temp = *this;
            if (current->next == nullptr) {
                current = nullptr;
            } else {
                current = current->next;
            }
            return temp;
        }

        MyBidirectionalIterator& operator--() {
            if (current == nullptr || current->prev == nullptr) {
                current = list->tail; // 当到达链表头部再--，将迭代器设为链表尾部（可根据需求调整）
            } else {
                current = current->prev;
            }
            return *this;
        }

        MyBidirectionalIterator operator--(int) {
            MyBidirectionalIterator temp = *this;
            if (current == nullptr || current->prev == nullptr) {
                current = list->tail;
            } else {
                current = current->prev;
            }
            return temp;
        }

        bool operator==(const MyBidirectionalIterator& other) const {
            return current == other.current;
        }

        bool operator!=(const MyBidirectionalIterator& other) const {
            return current != other.current;
        }
    };

    MyBidirectionalIterator begin() {
        return MyBidirectionalIterator(head, this);
    }

    MyBidirectionalIterator end() {
        return MyBidirectionalIterator(nullptr, this);
    }

    MyBidirectionalIterator rbegin() {
        return MyBidirectionalIterator(tail, this);
    }

    MyBidirectionalIterator rend() {
        return MyBidirectionalIterator(nullptr, this);
    }
};

以上代码实现了双向链表自定义容器MyDoublyLinkedList及其双向迭代器MyBidirectionalIterator，满足题目要求的各种操作。当链表节点被删除时，迭代器的处理方式是将current指针设为nullptr表示迭代器无效，后续操作会根据这种无效状态进行处理（如operator++操作，若current为nullptr则不移动）。在operator--操作中，当到达链表头部再--，将迭代器设为链表尾部，这种处理方式可根据实际需求进一步调整。

星途面试题库

面试题：C++ 实现自定义双向迭代器并用于自定义链表

知识考点

面试题答案