c++ listnode如何實現高效插入

要實現高效的插入操作，可以使用雙向鏈表（doubly linked list）來實現ListNode。雙向鏈表可以在O(1)的時間復雜度內進行插入操作。

以下是一個簡單的C++示例代碼：

#include <iostream>

struct ListNode {
    int val;
    ListNode* prev;
    ListNode* next;
    
    ListNode(int x) : val(x), prev(nullptr), next(nullptr) {}
};

class LinkedList {
public:
    LinkedList() : head(nullptr), tail(nullptr) {}

    void insert(int val) {
        ListNode* newNode = new ListNode(val);
        if (head == nullptr) {
            head = newNode;
            tail = newNode;
        } else {
            tail->next = newNode;
            newNode->prev = tail;
            tail = newNode;
        }
    }

    void print() {
        ListNode* current = head;
        while (current != nullptr) {
            std::cout << current->val << " ";
            current = current->next;
        }
        std::cout << std::endl;
    }

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

int main() {
    LinkedList list;
    list.insert(1);
    list.insert(2);
    list.insert(3);
    
    list.print();
    
    return 0;
}

在這個示例中，當插入一個新的節點時，只需要將新節點連接到鏈表的尾部，而不需要遍歷整個鏈表。這樣就能在O(1)的時間復雜度內完成插入操作。