链表基本操作
定义类
双向链表有专门的头文件
#include <list>
// 当然如果你用<bits/stdc++.h>的话就也无所谓了
忽然想到一件事情, 不会有人不知道bits/stdc++.h是什么吧?传送!
双向链表这样定义
list<type> name;
// type: 链表每个元素的数据类型
// name: 链表名
// 下面是一个例子:
list<int> ls; // 后面讲操作的时候就以ls为例
使用类
常规
增删改查都在下面:
// 对链表开头操作
ls.push_front(x); // 在ls开头添加x
ls.front(); // 返回ls开头元素
ls.pop_front(); // 删除ls开头元素
// 对链表末尾进行操作
ls.push_back(x); // 在ls末尾添加x
ls.back(); // 返回ls末尾元素
ls.pop_back(); // 删除ls末尾元素
一些特殊的方法:
ls.size(); // 返回ls的元素个数
ls.empty(); // 返回ls是否为空(空返回false, 否则true)
ls.clear(); // 清空ls
排序
ls.sort(); // 升序
// 可以把一个函数当作参数传入, 传入则按照函数实现的排序规则来排序, 类似algorithm中的sort
ls.sort(greater</*type*/>()); // 降序
// type替换为ls对应的数据类型
// 如果不是在std命名空间中, 则需要使用以下方法
ls.sort(std::greater</*type*/>());
遍历
由于链表没有索引, 我们使用迭代器(iterator)进行元素的访问, 进而实现遍历的功能.
ls.begin(); // 返回指向ls开头的迭代器
ls.end(); // 返回指向ls结尾的迭代器(最后一个元素的下一个位置)
这里比较难理解, 特别是end, 所以给大家配了一幅图
理解到这里后, 就可以开始讲遍历了:
for(auto pos = ls.begin(); pos != ls.end(); pos++){
// 元素使用*pos来访问
}
这里我们使用了C++11(或以上)特有的auto, 如果版本较旧的话需要替换为list<type>::iterator, 把type替换为ls对应的数据类型.
如果你使用的是C++11(或以上), 推荐你使用一种更简便的方法:
for(int num : ls){
// 元素为num
}
这种方法有一个弊端, 就是不能局部遍历.
链表存储原理
