在C语言中我们已经模拟实现了list,现在对比c++看看二者的区别
双链表————详讲
个人博客主页:
个人主页
个人码云
码云代码
文章目录
-
目录
文章目录
编辑
前言
一、list是什么?
二、list的使用
三、模拟实现list和搭建list的结构
1.节点结构
2.迭代器的详讲(这是和vector的区别)
3.list基础结构
4.修改器
四、测试list
总结
链表就像这个火车
前言
1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。
2. list的底层是双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向 其前一个元素和后一个元素。
3. list与forward_list非常相似:最主要的不同在于forward_list是单链表,只能朝前迭代,已让其更简单高 效。
4. 与其他的序列式容器相比(array,vector,deque),list通常在任意位置进行插入、移除元素的执行效率 更好。
5. 与其他序列式容器相比,list和forward_list最大的缺陷是不支持任意位置的随机访问,比如:要访问list 的第6个元素,必须从已知的位置(比如头部或者尾部)迭代到该位置,在这段位置上迭代需要线性的时间 开销;list还需要一些额外的空间,以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这 可能是一个重要的因素)
一、list是什么?
list就是带头双向链表,头节点存有链表的最后一个节点的地址和第一个节点的地址(链表的物理空间是不连续的,每一个节点的物理空间都是独立的),每一个节点中都存有上一个节点的地址和下一个节点的地址。
二、list的使用
list中的接口比较多,此处类似,只需要掌握如何正确的使用,然后再去深入研究背后的原理,已达到可扩展 的能力。以下为list中一些常见的重要接口。
#include
#include - #include
#include using namespace std; #include void test_list1() { //定义链表和插入数据 list lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); //迭代器的遍历 list ::iterator it = lt.begin(); while (it != lt.end()) { cout << *it << " "; ++it; } cout << endl; for (auto e : lt) { cout << e <<" "; } cout << endl; //查找节点插入数据 list ::iterator pos = find(lt.begin(), lt.end(), 3); if (pos != lt.end()) { lt.insert(pos, 30); } for (auto e : lt) { cout << e << " "; } cout << endl; } 这里的迭代器的使用和vector一样但是这两个迭代器底层有着非常大的差距 ,在下面的模拟实现中会非常细致的讲解
思考:pos1++和pos2++的区别,这两个指针哪一个可以找到下一个元素的地址???
提示:曾经的顺序表和链表的关系。
void test_list2() { list
lt; lt.push_back(10); lt.push_back(2); lt.push_back(5); lt.push_back(3); lt.push_back(4); lt.push_back(4); lt.push_back(6); lt.push_back(4); lt.push_back(0); for (auto e : lt) { cout << e << " "; } cout << endl; lt.sort(); // 迭代器功能分类 // 1、单向 ++ // 2、双向 ++ -- // 3、随机 ++ -- + - //sort(lt.begin(), lt.end()); for (auto e : lt) { cout << e << " "; } cout << endl; } 三、模拟实现list和搭建list的结构
1.节点结构
代码如下(示例):
template
//用到了类模板,由于我们想要插入任意类型的数据 struct list_node { list_node * _next; list_node * _prev; T _data; list_node(const T& x = T())//对成员的默认初始化,这个也是一个匿名构造。 :_next(nullptr)//初始化时将节点的下一个节点个下一个节点都置空 , _prev(nullptr) , _data(x)//插入x {} }; 1.在c语言中,结构体用的是struct,而在c++中我们也可以使用,它和calss相似,如果在一个类里面不需要区分共有成员和私有成员,我们就可以用struct。因为都是自定义类型所以我们需要对它进行成员的初始化。
2.在这个节点中我们存在着后面对成员的访问权限问题,所以我们选择使用struct。
2.迭代器的详讲(这是和vector的区别)
代码如下(示例):
// 1、迭代器要么就是原生指针 // 2、迭代器要么就是自定义类型对原生指针的封装,模拟指针的行为 template
//类模板可以有多个参数,T是原生类型,也就是普通类型 //ref是const类型,不可进行修改;ptr是指针类型。 struct __list_iterator { typedef list_node node; typedef __list_iterator self; node* _node; __list_iterator(node* n) :_node(n) {} Ref operator*()//对*的重载,返回为const类型。 { return _node->_data; } Ptr operator->()//对->的重载,->用在对地址的访问,也就是见引用node地址处的date { return &_node->_data; } self& operator++()//这里的++是前置++,返回的类型是节点类型,而不是节点的指针,在C语言中是一个地址 { _node = _node->_next; return *this; } self operator++(int)//后置++,+了一个int类型进行对前置++的区分 { self tmp(*this); _node = _node->_next; return tmp; } self& operator--() { _node = _node->_prev; return *this; } self operator--(int) { self tmp(*this); _node = _node->_prev; return tmp; } bool operator!=(const self& s) { return _node != s._node; } bool operator==(const self& s) { return _node == s._node; } }; 1.类模板中提到过,一个模板可以有多个模板参数,每一个模板可以控制某一种类型。
2.我们的类模板功能非常强大,到我们想要写一个类,但是这个类要写两者类型时,我们需要写两个类出来,但是用了模板我们只需要加一个模板参数即可;
3.“->”用于地址访问和见引用,而“."用于类的成员访问,二者都是见引用的作用。
template
class list { typedef list_node node; public: typedef __list_iterator iterator; typedef __list_iterator const_iterator; iterator begin() { //iterator it(_head->_next); //return it; return iterator(_head->_next); } const_iterator begin() const { return const_iterator(_head->_next); } iterator end() { return iterator(_head); } const_iterator end() const { //iterator it(_head->_next); //return it; return const_iterator(_head); } 因为在迭代器中我们的”*“重载即用了普通类型,也用了const类型,所以我们单独给它一个名字Ref,当我们用const类型迭代器时,传递过来的模板参数是const。这是*重载就是const类型。
3.list基础结构
template
class list { typedef list_node node; public: typedef __list_iterator iterator; typedef __list_iterator const_iterator; list(const list & lt)//拷贝构造 { empty_init(); list tmp(lt.begin(), lt.end()); swap(tmp); } void empty_init() { _head = new node; _head->_next = _head; _head->_prev = _head; } list()//默认构造 { empty_init(); } template list(Iterator first, Iterator last)//区间拷贝构造 { empty_init(); while (first != last) { push_back(*first); ++first; } ~list() { clear(); delete _head; _head = nullptr; } private: node* _head; }; 4.修改器
void swap(list
& tmp)//交换两个节点 { std::swap(_head, tmp._head); } void clear()//清空内容 { iterator it = begin(); while (it != end()) { //it = erase(it); erase(it++); } } void push_back(const T& x)//尾插 { /*node* tail = _head->_prev; node* new_node = new node(x); tail->_next = new_node; new_node->_prev = tail; new_node->_next = _head; _head->_prev = new_node;*/ insert(end(), x); } void push_front(const T& x)//头插 { insert(begin(), x); } void pop_back()//尾删 { erase(--end()); } void pop_front()//头删 { erase(begin()); } void insert(iterator pos, const T& x)//任意位置插入 { node* cur = pos._node; node* prev = cur->_prev; node* new_node = new node(x); prev->_next = new_node; new_node->_prev = prev; new_node->_next = cur; cur->_prev = new_node; } iterator erase(iterator pos)//任意位置删除 { assert(pos != end()); node* prev = pos._node->_prev; node* next = pos._node->_next; prev->_next = next; next->_prev = prev; delete pos._node; return iterator(next); } 有了insert函数,我们就不需要push_back和push_front函数了,erase也是;
四、测试list
void test_list1() { const list
lt1; const int n = 10; //n = 11; list lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); // int* list ::iterator it = lt.begin(); while (it != lt.end()) { (*it) *= 2; cout << *it << " "; ++it; } cout << endl; for (auto e : lt) { cout << e << " "; } cout << endl; print_list(lt); } struct AA { int _a1; int _a2; AA(int a1 = 0, int a2 = 0) :_a1(a1) , _a2(a2) {} }; void test_list2() { list lt; lt.push_back(AA(1, 1)); lt.push_back(AA(2, 2)); lt.push_back(AA(3, 3)); // AA* ptr list::iterator it = lt.begin(); while (it != lt.end()) { //cout << (*it)._a1 << ":" << (*it)._a2 << endl; cout << it->_a1 << ":" << it->_a2 << endl; //cout << it.operator->()->_a1 << ":" << it.operator->()->_a1 << endl; ++it; } cout << endl; } void test_list3() { list lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); for (auto e : lt) { cout << e << " "; } cout << endl; auto pos = lt.begin(); ++pos; lt.insert(pos, 20); for (auto e : lt) { cout << e << " "; } cout << endl; lt.push_back(100); lt.push_front(1000); for (auto e : lt) { cout << e << " "; } cout << endl; lt.pop_back(); lt.pop_front(); for (auto e : lt) { cout << e << " "; } cout << endl; } void test_list4() { list lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); for (auto e : lt) { cout << e << " "; } cout << endl; lt.clear(); for (auto e : lt) { cout << e << " "; } cout << endl; lt.push_back(10); lt.push_back(2); lt.push_back(3); lt.push_back(40); for (auto e : lt) { cout << e << " "; } cout << endl; } void test_list5() { list lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); for (auto e : lt) { cout << e << " "; } cout << endl; list lt2(lt); for (auto e : lt2) { cout << e << " "; } cout << endl; list lt3; lt3.push_back(10); lt3.push_back(20); lt3.push_back(30); for (auto e : lt3) { cout << e << " "; } cout << endl; lt2 = lt3; for (auto e : lt2) { cout << e << " "; } cout << endl; for (auto e : lt3) { cout << e << " "; } cout << endl; }
总结
迭代器中的类模板
修改器的insert和erase
了解list的基本结构