数据结构05 链表list

list的定义

由于链表的存储方式并不是连续的内存空间，因此链表list中的迭代器只支持前移和后移，属于双向迭代器

list的优缺点

优点：采用动态存储分配，不会造成内存浪费和溢出。

链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素。

缺点：list链表遍历速度不快，同时占用空间大。

与vector容器相比，因为不用保持内存空间的连续性，所以list的插入删除更为方便快捷。但是list容器所占用的内存空间比vector容器大，遍历速度慢。

插入和输出链表中的内容

#include <list> //头文件
list<int>::iterator it; //迭代器
//输出链表中的内容，构造print_l函数
void print_l(list<int> l)
{
    for (auto it = l.begin(); it != l.end(); it++)
    {
        cout << *it << "  ";
    }
    cout << endl;
}

list容器的构造与初始化

构造函数 :list<参数类型> 链表名

list<int> l; //构造一个链表l，其中存储int型的数据。
list<int> l(起始迭代器 start，终止迭代器 end)；//将起始迭代器和终止迭代器之间的元素赋给链表l。
list<int> l(int n, int elem);  //创建并将n个元素elem存入链表l中。
list<int> l(const list<int> &l1)； //将l1拷贝构造给l。
list<int> l;

l.push_back(1);
print_l(l);

list<int> l1(l.begin(), l.end());
print_l(l1);

list<int> l2(3, 4);
print_l(l2);

list<int> l3(l);
print_l(l3);

list常用函数

一、给list容器重新赋值

assign
assign(起始迭代器 start，终止迭代器 end);  //将起始迭代器到终止迭代器之间的内容赋值给l。

assign(int n, int elem);  //将n 个元素elem赋给l。

list<int> l;
l.push_back(1);
print_l(l);

l.assign(3, 5);
print_l(l);

list<int> l1(2, 3);
l.assign(l1.begin(), l1.end());
print_l(l);

二、list容器的大小

size函数可以查看list容器的大小（存储元素的数量）。

empty函数可以查看list容器是否为空（大小是否为0）。

resize函数用于重新设置容器大小。

resize(int n, int elem);若n大于容器的大小，则将容器大小设为n，且多出的部分用elem补上（若第二个参数为0则用默认值补上）；若n小于容器的大小，则删去多于n的元素。

list<int> l(4, 5);
print_l(l);
if (l.empty()) cout << "容器为空" << endl;
else cout << "容器的大小为：" << l.size() << endl;
l.resize(3, 4);
print_l(l);
l.resize(6);
print_l(l);

三、容器的插入与删除

头、尾插法：

头插法：push_front。

尾插法：push_back。

list<int> l(1,5);
//头插法
l.push_front(2);
//尾插法
l.push_back(4);
print_l(l);

头删、尾删法：

头删法：pop_front。

尾删法：pop_back。

list<int> l(1, 3);
l.insert(l.begin(), 1);
l.insert(l.end(), 5);
print_l(l);

l.pop_front();
print_l(l);
l.pop_back();
print_l(l);

四、数据存取

读取第一个元素：front。

读取最后一个元素：back。

list<int> l(1, 3);
l.push_back(4);
l.push_back(2);
print_l(l);
cout << "第一个元素为：" << l.front() << endl;
cout << "最后一个元素为：" << l.back() << endl;