c++ listnode如何實(shí)現(xiàn)高效插入

c++
小樊
86
2024-07-24 14:15:13
欄目: 編程語言

要實(shí)現(xiàn)高效的插入操作，可以使用雙向鏈表（doubly linked list）來實(shí)現(xiàn)ListNode。雙向鏈表可以在O(1)的時(shí)間復(fù)雜度內(nèi)進(jìn)行插入操作。

以下是一個(gè)簡(jiǎn)單的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;
}

在這個(gè)示例中，當(dāng)插入一個(gè)新的節(jié)點(diǎn)時(shí)，只需要將新節(jié)點(diǎn)連接到鏈表的尾部，而不需要遍歷整個(gè)鏈表。這樣就能在O(1)的時(shí)間復(fù)雜度內(nèi)完成插入操作。

0 踩