c++ listnode如何实现高效插入

avatar
作者
猴君
阅读量:0

要实现高效的插入操作,可以使用双向链表(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)的时间复杂度内完成插入操作。

广告一刻

为您即时展示最新活动产品广告消息,让您随时掌握产品活动新动态!