AB9[模板]链表

[题](【模板】链表_牛客题霸_牛客网 (nowcoder.com))

1. 代码

   #include "iostream"
   #include "string"
   #include "list"
   #include "algorithm"
   
   
   int main(){
       int x{0},y{0},num{0};
       std::list<int> list;
       std::string str{};
       std::cin>>num;
       auto item=list.begin();
       while(num--){
           std::cin>>str;
   
           if(str=="insert"){
               std::cin>>x>>y;
               //下面两行如果不存在将返回最后一个迭代器，也就是实现了如果不存在插入到最后一个
               auto item1=std::find(list.begin(),list.end(),x);
               list.insert(item1,y);
             
           }else if(str=="delete"){
               std::cin>>y;
               auto item1=std::find(list.begin(),list.end(),y);
               
               //下面的if-else 实现的是如果有重复的删除一个
               //如果使用remove(value)将会删除所有的与value相同的
               if(item1!=list.end()) {
                   
                   list.erase(item1);//参数必须是迭代器
               }else {
                   
                   list.remove(y);//不能是迭代器
               }
           }
       }
       if(list.empty()){
           std::cout<<"NULL";
       }else {
           for(const auto& item1: list){
               std::cout<<item1<<" ";
           }
       }
   }

2. 提示

   • int x{0},y{0},num{0}

     这只是一种初始化方式

   • list是一个双向的链表

     • insert()

       插入元素，有两个参数，有4个重载函数

       但是第一个元素只能是迭代器

     • erase()

       删除迭代器的元素

     • remove(value)

       删除所有的与value相等的节点

   • find()

     返回迭代器，如何存在法返回该元素的迭代器，不存在返回最后一个迭代器

3. 理解

   因为list封装了双向链表，所以直接拿来用

   但是使用find可以查找有没有元素

4. 问题

   • c++封装的链表调用起来会不会时间复杂度很大？

     一般情况下，C++ STL 的 list 库的效率要优于手写的链表。这是因为 std::list 不仅实现了常见的操作，例如在任意位置插入/删除元素、遍历/查找列表、反转/排序列表等等，而且还通常采用指针来实现，比手写链表更加高效。

     另外，在 STL 的 list 中，封装程序员带来的好处是程序员不需要设计和编写具体的数据结构，也无需理解底层实现细节。所有 STL 集合类都已经实现了大量的算法和数据结构以及相应的纠错代码，因此能够保证高效、稳定和安全。

     当然，对于一些特殊情况和特定应用场景，手写链表可能会比 C++ STL 的 list 更有效率。但这需要根据具体的实际情况来进行评估和验证。

     总之，在大多数情况下，使用 C++ STL 的 list 库更方便、更高效、更容易维护和调试。