C++第二十四弹---从零开始模拟STL中的list(上)
✨个人主页： 熬夜学编程的小林
💗系列专栏： 【C语言详解】 【数据结构详解】【C++详解】
目录
1、基本结构
2、基本函数实现
2.1、默认构造函数
2.2、尾插数据
3、迭代器的封装
3.1、迭代器的基本结构
3.2、迭代器重载函数的实现
4、迭代器与list进行关联
4.1、使用迭代器打印链表数据
4.2、其他相关函数
总结
1、基本结构
namespace lin
{
template
struct ListNode//双向循环链表的基本结构
{
ListNode* _prev;//前驱指针
ListNode* _next;//后继指针
T _data;//数据值
//不传值时使用T()默认值构造，传值则传值构造
ListNode(const T& val = T())//默认构造 + 传值构造
:_prev(nullptr)
,_next(nullptr)
,_data(val)
{}
};
template
struct ListIterator//迭代器封装类，成员都会被调用，因此使用struct
{
typedef ListNode Node;
Node* _node;//结点指针
}
template
class list//链表模板类，成员变量定义及函数封装
{
typedef ListNode Node;//将链表结构取别名，简化代码
public:
typedef ListIterator iterator;//迭代器重命名
private:
Node* _head;//链表头指针
size_t size;//链表长度
}
}
上述代码实现了双向循环链表的基本结构，其中包含了四个部分：
1.namespace lin，命令空间 lin 是用于封装代码，避免同名类型和函数冲突。
2.在命名空间中，定义了模板类ListNode(双向循环链表基本结构)，该类包含三个成员变量：
- _prev : 存储指向前一个结点的指针
- _next : 存储指向后一个结点的指针
- _data : 存储数据
ListNode类还实现一个有缺省值(T())的构造函数，如果构造函数没有提供参数，则使用T类型的默认构造来初始化_data，如果传值则使用该值来初始化_data，该构造函数也会将_prev和_next指针指向nullptr。
3.模板类ListIterator(迭代器封装)，该类包含一个成员变量，即链表的结点指针：
为什么链表需要封装一个迭代器的类呢？？？
- 链表的物理空间是不连续的，是通过结点的指针依次链接。
- 不能像string和vector一样直接解引用去访问其数据。
- 结点的指针解引用还是结点，结点指针++还是结点指针。
- 在string和vector的物理空间是连续的，所以这俩不需要实现迭代器类，可以直接使用。
4.模板类list(链表的基本成员变量及其函数接口)，该类包含两个成员变量：
- _head : 链表的头结点指针
- _size : 链表的长度
2、基本函数实现
注意：我们实现的是带头双向循环链表。
2.1、默认构造函数
list()
默认构造的函数功能是构造一个没有元素的空容器。
思路：我们实现的是带头双向循环链表，因此默认构造时我们需要创建(new)一个头结点，并将链表长度初始化为0。
//构造头结点函数 void empty_init() { _head = new Node;//创建新结点 _head->_next = _head; _head->_prev = _head; _size = 0; } //默认构造 构造一个头结点 list() { empty_init(); }为了后序使用方便，我们将构造头结点封装成了一个函数。
2.2、尾插数据
为什么在第二个函数就写尾插呢？因为后面的函数会大量用到尾插函数。
push_back()
思想：
- 先找到尾结点，即头结点的前一个结点。
- 然后将尾结点，新结点以及头结点进行链接。
void push_back(const T& val) { //tail _head->_prev Node* tail = _head->_prev; Node* newnode = new Node(val);//创建一个值为val的新结点 //tail newnode _head //链接关系的顺序 tail->_next = newnode; newnode->_prev = tail; newnode->_next = _head; _head->_prev = newnode; _size++;//尾插之后长度要++ }
我们尾插完数据之后，想要遍历整个链表怎么遍历呢？？？
我们在使用链表的时候是通过迭代器进行遍历，如下代码：
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 _data;//访问链表的data数据 }operator!=
重载两个迭代器不相等，指针不相等则返回true，相等则返回false。
bool operator!=(const Self& lt) { return _node != lt._node;//两个迭代器不相等即指针不相等 }operator==
bool operator==(const Self& lt) { return _node == lt._node; }注意：比较迭代器是否相等比较的是的地址。
4、迭代器与list进行关联
4.1、使用迭代器打印链表数据
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 _prev; Node* newnode = new Node(val); //prev newnode cur prev->_next = newnode; newnode->_prev = prev; newnode->_next = cur; cur->_prev = newnode; _size++; }
erase()
删除pos位置的值，并返回删除前的下一个结点的地址。
思路：
- 先获取当前结点的地址
- 然后通过前驱指针找到前一个结点地址，通过后继指针找到后一个结点的地址
- 将prev 前驱指针与后继指针建立链接关系
- 释放当前结点
- 返回next结点
iterator erase(iterator pos)//删除pos位置值，迭代器失效问题 { Node* cur = pos._node; Node* prev = cur->_prev; Node* next = cur->_next; //prev next prev->_next = next; next->_prev = prev; delete cur; _size--; return iterator(next);//返回迭代器中结点指针 }头插尾插头删尾删
复用insert()函数和erase()函数实现。
void push_back(const T& val) { insert(end(), val);//end()之前插入 } void push_front(const T& val) { insert(begin(),val);//begin()之前插入 } void pop_back() { erase(--end());//删除end前面一个结点 } void pop_front() { erase(begin());//删除begin位置结点 }总结
本篇博客就结束啦，谢谢大家的观看，如果公主少年们有好的建议可以留言喔，谢谢大家啦！
