迹忆客 专注技术分享

这个简短的编程教程将讨论 C++ 中广泛使用的数据结构，即 List。在 C++ 标准模板库 (STL) 中，我们有一个可用于此数据结构的类 list。

里面打包了一堆函数，可以用来对列表执行多个操作。在本文后面，我们将讨论如何遍历列表并查看或编辑列表。

C++ 中的列表

列表，或称链接列表，是一种线性数据结构，可以作为数据容器，将数据存储在内存中。与向量和数组不同，列表中的数据不存储在连续的内存位置。

相反，数据保存在随机内存位置。插入列表中的每个元素称为节点。

列表中的每个节点都包含一个指向列表下一个元素的指针。这就是为什么列表的元素没有保存在连续位置的原因；因此，它也被称为链表。

列表可以分为两种类型：

1. 单链表
2. 双向链表

单链表

在这种类型的链表中，所有的节点有 2 个部分，一个用于数据，一个用于存储指向下一个节点的指针。第二部分存储列表的下一个节点的地址。

双向链表

在这种类型的链表中，所有节点都有 3 部分，第一部分是指向前一个节点的指针，第二部分是存储数据，第三部分包含引用链表下一个元素的指针。

STL 中的 list 类包含一个双向链表。像数组一样，这种列表类型的插入和删除需要线性时间。

但是，列表不需要传染性内存块。此外，通过一次附加单个列表节点来增长列表比重新分配整个动态数组（如向量所做的）更容易和更合理。

因此，它被认为是比数组和向量等其他数据结构更灵活的数据结构。

另一种数据结构 forward_list 只能遍历一个方向并且是一个单链表。与其他数据结构相比，列表和前向列表的主要缺点是我们不能像在数组中一样通过给出其位置来直接访问任何列表元素。

例如，要访问列表中的第 5 个元素，必须从某个端点开始，无论是开始还是结束到该位置，这需要线性时间。列表还使用额外的 RAM 来存储每个元素的连接信息。

遍历 C++ 中的列表

我们可以使用标准模板库 C++ 的 iterator 类来遍历列表元素。其语法如下：

std::list<int>::iterator itr;

列表中有不同的迭代方法：

让我们看看下面的代码，它使用了列表类的不同功能。

#include <iostream>
#include <iterator>
#include <list>
#include<cstdlib>
using namespace std;

void displaylist(list<int> l) //print function to show list
{
    list<int>::iterator myitr;
    for (myitr = l.begin(); myitr != l.end(); ++myitr)
        cout<<"  "<< *myitr;
    cout<<endl;
}
int main(){

    list<int> mylist1;
    for (int a = 0; a < 10; ++a) {
         int r = 1+ (rand() % 50);
        mylist1.push_back(r);
    }
    cout << "\nData of List 1 : ";
    displaylist(mylist1);
    cout << "\nList first element : " << mylist1.front();
    cout << "\nAfter we pop first element: ";
    mylist1.pop_front();
    displaylist(mylist1);

    cout << "\nWhen we sort the list: ";
    mylist1.sort();
    displaylist(mylist1);

    return 0;
}

输出：

Data of List 1 :   34  37  28  16  44  36  37  43  50  22

List first element : 34
After we pop first element:   37  28  16  44  36  37  43  50  22

When we sort the list:   16  22  28  36  37  37  43  44  50