C++ list容器-52-链表基本概念和构造函数/赋值

待我称王封你为后i 2023-03-04 14:27 14阅读 0赞

前面学习的容器或叫数据结构都是连续存储的空间。例如数组和vector都是在一块连续的内存空间去存储数据。既然有连续存储当然也就有非连续存储。这里开始学习非连续存储的数据结构，list，也叫链表

**1.list的基本概念**

list是一种将数据进行链式存储的数据结构，也叫链表。list是一种物理存储单元上非连续的存储结构，将数据元素的逻辑顺序是通过链表中的指针链接实现的。

链表的组成：链表由一系列结点组成。

结点的组成：一个存储数据元素的数据域，另一个是存储下一个结点地址的指针域

链表有单链表和双链表区别，在C++中STL中的链表是一个**双向循环链表**。

**2.list的数据结构图**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1NDE5NDY_size_16_color_FFFFFF_t_70][]

上面图结构，可以看出是一个双向的链表结构，有两头，结点和结点之间通过指针可以找前一个和后一个，这个就是双向的意思。什么是循环呢，也就是链表头尾两个结点进行连接成一个环，头结点的前一个结点是尾结点，尾结点的下一个节点是头结点，这个就是循环链表。

**3.list的优缺点**  
list优点  
采用动态存储分配，不会造成内存浪费和溢出  
链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素

list缺点  
链表灵活，但是空间（指针域）和时间（遍历）额外耗费较大

list有一个重要的性质，插入操作和删除操作都不会造成原有list迭代器的失效，这在vector是不成立的

**4.list的构造函数**

函数原型：

![20200804225649941.png][]

根据前面容器的构造练习，这些构造前面都学习过，下面直接代码来练习下

#include <iostream>
    #include <string>
    #include <list>
    using namespace std;
    
    
    void printList(const list<int> &l)
    {
        for(list<int>::const_iterator it = l.begin(); it != l.end(); it++)
        {
            cout << *it << " ";
        }
        cout << endl;
    
    }
    
    void test01()
    {
        // list 构造函数
        list<int> li;   // 默认构造函数
    
        // 添加数据
        li.push_back(10);
        li.push_back(20);
        li.push_back(30);
        li.push_back(40);
        li.push_back(50);
    
        printList(li);
    
        // 第二种构造，使用迭代区间
        list<int> li2(li.begin(), li.end());
        printList(li2);
    
        // 第三中构造 n个ele
        list<int> li3(6, 80);
        printList(li3);
    
        // 第四种，拷贝构造
        list<int> li4(li3);
        printList(li4);
    
    
    }
    
    
    int main()
    {
        test01();
        system("pause");
        return 0;
    }

上面介绍了遍历，新增元素和链表构造基本使用

![20200804233914509.png][]

**5.list的赋值和交换**

赋值和交换函数原型

![20200804234421390.png][]

练习代码

#include <iostream>
    #include <string>
    #include <list>
    using namespace std;
    
    
    void printList(const list<int> &l)
    {
        for(list<int>::const_iterator it = l.begin(); it != l.end(); it++)
        {
            cout << *it << " ";
        }
        cout << endl;
    
    }
    
    void test01()
    {
        // list 构造函数
        list<int> li;   // 默认构造函数
    
        // 添加数据
        li.push_back(10);
        li.push_back(20);
        li.push_back(30);
        li.push_back(40);
        li.push_back(50);
    
        printList(li);
    
        // list 赋值
        list<int> li2;
        li2 = li;
        printList(li2);
    
        // list 赋值2
        list<int> li3;
        li3.assign(li2.begin(), li2.end());
        printList(li3);
    
        // list 赋值3
        list<int> li4;
        li4.assign(6, 100);
        printList(li4);
    
        cout << "after swap: " << endl;
        li4.swap(li);
        printList(li);
        printList(li4);
    
    }
    
    
    int main()
    {
        test01();
        system("pause");
        return 0;
    }

运行结果

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1NDE5NDY_size_16_color_FFFFFF_t_70 1][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1NDE5NDY_size_16_color_FFFFFF_t_70]: /images/20230208/dba116b4696143bfb2e6c8a97131dd42.png
[20200804225649941.png]: /images/20230208/c413a0dc9b834b30891749c86c864abd.png
[20200804233914509.png]: /images/20230208/cb6f597dae0e444d9ceecfdabe930e89.png
[20200804234421390.png]: /images/20230208/2c1a4f2a04864995b4fd0683d32b9598.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1NDE5NDY_size_16_color_FFFFFF_t_70 1]: /images/20230208/91368e9d687d48e48b1d1f170b9f6fca.png