链表

手写双链表：

#include <iostream>

// 链表节点结构体
struct ListNode {
    int value;
    ListNode* prev;
    ListNode* next;

    ListNode(int v, ListNode* p = nullptr, ListNode* n = nullptr) : value(v), prev(p), next(n) {}
};

class LinkedList {
public:
    LinkedList() : head(nullptr), tail(nullptr), size(0) {}
    ~LinkedList() { clear(); }

    // 在链表末尾添加元素
    void push_back(int value) {
        if (size == 0) {
            head = tail = new ListNode(value);
        } else {
            tail->next = new ListNode(value, tail);
            tail = tail->next;
        }
        ++size;
    }

    // 删除链表末尾元素
    void pop_back() {
        if (size == 0) return;
        ListNode* temp = tail;
        if (size == 1) {
            head = tail = nullptr;
        } else {
            tail = tail->prev;
            tail->next = nullptr;
        }
        delete temp;
        --size;
    }

    // 清空链表
    void clear() {
        while (size > 0) {
            pop_back();
        }
    }

    // 获取链表长度
    int get_size() const { return size; }

    // 打印链表元素
    void print() const {
        ListNode* temp = head;
        while (temp) {
            std::cout << temp->value << " ";
            temp = temp->next;
        }
        std::cout << std::endl;
    }

private:
    ListNode* head;
    ListNode* tail;
    int size;
};

int main() {
    LinkedList list;
    list.push_back(1);
    list.push_back(2);
    list.push_back(3);
    list.push_back(4);
    list.push_back(5);

    std::cout << "List: ";
    list.print();
    std::cout << "Size: " << list.get_size() << std::endl;

    list.pop_back();
    std::cout << "List after pop_back: ";
    list.print();
    std::cout << "Size: " << list.get_size() << std::endl;

    return 0;
}