C++ 模拟实现 list：双向链表构建与解析

这里将 iterator 定义为指向节点的指针。在实际工程中，为了更严格的类型安全，通常会封装成类，但为了演示底层逻辑，直接使用裸指针更为直观。

2. 构造与析构

默认构造函数初始化空链表。拷贝构造函数需要深拷贝，遍历源链表逐个创建新节点。

template<typename T> MyList<T>::MyList() : head(nullptr), tail(nullptr), size_(0) {}

template<typename T> MyList<T>::MyList(size_t n, const T& value) : head(nullptr), tail(nullptr), size_(0) {
    for (size_t i = 0; i < n; ++i) {
        push_back(value);
    }
}

template<typename T> MyList<T>::MyList(const MyList<T>& other) : head(nullptr), tail(nullptr), size_(0) {
    for (ListNode* node = other.head; node != nullptr; node = node->next) {
        push_back(node->data);
    }
}

析构函数负责清理所有节点。注意遍历顺序，先保存下一个节点指针再释放当前节点，防止断链。

template<typename T> MyList<T>::~MyList() {
    while (head != nullptr) {
        ListNode* next = head->next;
        delete head;
        head = next;
    }
}

3. 核心增删操作

头尾插入与删除

push_front 和 push_back 是基础操作。处理空表情况时需同时更新 head 和 tail。

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

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

删除操作同理，需注意边界条件。例如 pop_front 删除最后一个节点时，需将 tail 置空。

template<typename T> void MyList<T>::pop_front() {
    if (head != nullptr) {
        ListNode* next = head->next;
        if (next != nullptr) {
            next->prev = nullptr;
        } else {
            tail = nullptr;
        }
        delete head;
        head = next;
        --size_;
    }
}

指定位置插入与删除

insert 和 erase 需要处理中间节点的情况。插入时调整前后节点的指针指向；删除时跳过目标节点并释放内存。

template<typename T> void MyList<T>::insert(iterator pos, const T& value) {
    if (pos == begin()) {
        push_front(value);
        return;
    }
    if (pos == end()) {
        push_back(value);
        return;
    }
    ListNode* newNode = new ListNode(value);
    newNode->prev = pos->prev;
    newNode->next = pos;
    pos->prev->next = newNode;
    pos->prev = newNode;
    ++size_;
}

template<typename T> void MyList<T>::erase(iterator pos) {
    if (pos == head) {
        pop_front();
        return;
    }
    if (pos == tail) {
        pop_back();
        return;
    }
    pos->prev->next = pos->next;
    pos->next->prev = pos->prev;
    delete pos;
    --size_;
}

4. 迭代器支持

迭代器本质是指针。begin() 返回头节点，end() 返回 nullptr 作为哨兵。遍历时检查是否等于 end() 即可终止。

template<typename T> typename MyList<T>::iterator MyList<T>::begin() {
    return head;
}

template<typename T> typename MyList<T>::iterator MyList<T>::end() {
    return nullptr;
}

总结

通过上述步骤，我们完成了一个具备基本功能的双向链表实现。关键点在于：

• 指针维护：任何修改都必须同步更新 prev 和 next，否则会导致链表断裂。
• 边界处理：空表、单节点、头尾节点的操作逻辑往往不同，需单独分支处理。
• 资源管理：遵循 RAII 原则，确保析构时释放所有动态内存。

掌握这些底层机制，有助于更好地使用 STL 容器，并在遇到性能瓶颈时进行针对性的优化。