C++基础：STL之双向链表list

╰半橙微兮° 2022-12-18 02:57 154阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdW1pYW9jbg_size_16_color_FFFFFF_t_70_pic_center]  
这篇文章介绍一下STL中list的基本使用方法。

### 目录 ###

*  双向链表list
 *  头文件和命名空间
 *  常用的成员函数
 *  list vs vector
 *  代码使用示例
 *  示例执行结果
 *  总结

--------------------

# 双向链表list #

> 相较于数组，链表也是一种非常常见的数据结构，链表的特点主要如下所示：

*  物理存储上非连续，数组为顺序存储，需要大段空间，而链表则体现为随机存储，可见缝插针地使用空间
 *  一般分为双向链表或者单向链表
 *  链表的元素一般称为节点，节点由存放数据的部分和存放链接信息的指针数据组成
 *  单向链表一般保存next指针关联后续节点，双向链表还需要previous指针指向前面的节点
 *  关于对于数组和链表的说明内容可参看：[https://blog.csdn.net/liumiaocn/article/details/108088361][https_blog.csdn.net_liumiaocn_article_details_108088361]

# 头文件和命名空间 #

> \#include <list>  
> using namespace std;

# 常用的成员函数 #

<table> 
 <thead> 
  <tr> 
   <th>函数名</th> 
   <th>用途</th> 
   <th>功能说明</th> 
   <th>时间复杂度</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>size()</td> 
   <td>查询遍历</td> 
   <td>获取元素个数</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>begin()</td> 
   <td>查询遍历</td> 
   <td>获取指向第一个元素的迭代器</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>end()</td> 
   <td>查询遍历</td> 
   <td>获取末尾的迭代器</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>insert(position,x)</td> 
   <td>插入</td> 
   <td>在position位置插入数据x</td> 
   <td>O(1)/O(n)</td> 
  </tr> 
  <tr> 
   <td>erase(position)</td> 
   <td>删除</td> 
   <td>删除position位置上的元素</td> 
   <td>O(1)/O(n)</td> 
  </tr> 
  <tr> 
   <td>push_back(x)</td> 
   <td>插入</td> 
   <td>在末尾插入数据x</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>pop_back()</td> 
   <td>删除</td> 
   <td>删除最后一个元素</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>clear()</td> 
   <td>删除</td> 
   <td>删除所有元素</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>push_front(x)</td> 
   <td>插入</td> 
   <td>在表头插入数据x</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>pop_front</td> 
   <td>删除</td> 
   <td>删除表头元素</td> 
   <td>O(1)</td> 
  </tr> 
 </tbody> 
</table>

> 注：因为对于末尾的元素的插入和删除不涉及元素的连锁移动，所以复杂度为O(1)，另外成员函数中似乎未涉及更新，这是因为vecotr可以像数组一样直接使用下标方式访问和修改，其复杂度当然也是O(1)。

--------------------

# list vs vector #

常用函数比较如下所示，简单来说，基本一致，list由于其链表的特性，在插入和删除的时候只需要断链和重链即可，所以复杂度也是常数级别的O(1)。另外由于其双向的特性，所以还存在一个在表头进行插入和删除的函数，此函数由于vector是变长数组的实现，所以是没有这种函数的。

<table> 
 <thead> 
  <tr> 
   <th>list函数名</th> 
   <th>vector函数名</th> 
   <th>用途</th> 
   <th>功能说明</th> 
   <th>时间复杂度</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>size()</td> 
   <td>size()</td> 
   <td>查询遍历</td> 
   <td>获取元素个数</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>begin()</td> 
   <td>begin()</td> 
   <td>查询遍历</td> 
   <td>获取指向第一个元素的迭代器</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>end()</td> 
   <td>end()</td> 
   <td>查询遍历</td> 
   <td>获取末尾的迭代器</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>insert(position,x)</td> 
   <td>insert(position,x)</td> 
   <td>插入</td> 
   <td>在position位置插入数据x</td> 
   <td>O(1)/O(n)</td> 
  </tr> 
  <tr> 
   <td>erase(position)</td> 
   <td>erase(position)</td> 
   <td>删除</td> 
   <td>删除position位置上的元素</td> 
   <td>O(1)/O(n)</td> 
  </tr> 
  <tr> 
   <td>push_back(x)</td> 
   <td>push_back(x)</td> 
   <td>插入</td> 
   <td>在末尾插入数据x</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>pop_back</td> 
   <td>pop_back()</td> 
   <td>删除</td> 
   <td>删除最后一个元素</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>clear()</td> 
   <td>clear()</td> 
   <td>删除</td> 
   <td>删除所有元素</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>push_front(x)</td> 
   <td>-</td> 
   <td>插入</td> 
   <td>在表头插入数据x</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>pop_front</td> 
   <td>-</td> 
   <td>删除</td> 
   <td>删除表头元素</td> 
   <td>O(1)</td> 
  </tr> 
 </tbody> 
</table>

# 代码使用示例 #

#include <iostream>
    #include <list>
    using namespace std;
    
    void print_list_data(list <char> l) {
        list <char>::iterator it = l.begin();
    
        while (it != l.end()) cout << *it++;
    
        cout << endl;
    }
    
    int main() {
        list <char> l;
    
        cout << "Size of list l : " << l.size() << endl;
        l.push_back('L');
        l.push_back('i');
        l.push_back('u');
        l.push_back('C');
        l.push_back('N');
        cout << "Size of list l : " << l.size() << endl;
        for (list<char>::iterator it = l.begin(); it != l.end(); it++) cout << *it;
        cout <<endl;
    
        list<char>::iterator it = l.begin();
        cout << "begin(): [" << *it << "]" << endl;
        it = l.end();
        cout << "end():   [" << *it << "]" << endl;
        it--;
        cout << "end():   [" << *it << "]" << endl;
    
        it = l.begin(); it++; it++; it++;
        l.insert(it, 'M');
        int offset = 4;
        it=l.begin();for (int i=0; i<offset; i++) it++;
        l.insert(it, 'i');
        offset++; it=l.begin();for (int i=0; i<offset; i++) it++;
        l.insert(it, 'a');
        offset++;it=l.begin();for (int i=0; i<offset; i++) it++;
        l.insert(it, 'o');
        offset++;it=l.begin();for (int i=0; i<offset; i++) it++;
    
        print_list_data(l);
    
        it = l.begin(); it++; it++; it++;
        l.insert(it,' ');
        it = l.begin();
        while (it != l.end()) cout << *it++;
        cout << endl;
    
        it = l.begin(); it++; it++; it++;
        *it = '*';
        print_list_data(l);
    
        it = l.begin(); it++; it++; it++;
        l.erase(it);
        print_list_data(l);
    
        l.push_back('!');
        print_list_data(l);
    
        l.pop_back();
        print_list_data(l);
    
        l.push_front('i');
        print_list_data(l);
        l.push_front('H');
        print_list_data(l);
        l.push_front('*');
        print_list_data(l);
        l.pop_front();
        print_list_data(l);
    
        cout << "Size of list l : " << l.size() << endl;
        l.clear();
        cout << "Size of list l : " << l.size() << endl;
    }

# 示例执行结果 #

Size of list l : 0
    Size of list l : 5
    LiuCN
    begin(): [L]
    end():   []
    end():   [N]
    LiuMiaoCN
    Liu MiaoCN
    Liu*MiaoCN
    LiuMiaoCN
    LiuMiaoCN!
    LiuMiaoCN
    iLiuMiaoCN
    HiLiuMiaoCN
    *HiLiuMiaoCN
    HiLiuMiaoCN
    Size of list l : 11
    Size of list l : 0

# 总结 #

变长支持、泛化类型、常用功能函数内嵌、可以使用其他多种STL的函数、使用简单，更新和删除操作的复杂度都是O(1)，都是list被广泛使用的原因，但是链表方式查询效率较低是无法绕开的一个要素，也是需要注意的。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdW1pYW9jbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221122/82a292b99f1848d18cc209cabea75551.png
[https_blog.csdn.net_liumiaocn_article_details_108088361]: https://blog.csdn.net/liumiaocn/article/details/108088361