软件公司网站设计与制作,西安做网站哪家比较好,jsp购物网站开发视频,东莞互联网大公司有哪些list的模拟实现一.list与vector1.底层结构的本质区别2.模拟实现的核心差异2.1数据存储的方式2.2 初始化的过程2.3 插入元素的操作2.4 删除元素的操作2.5 访问元素的效率3.总结二.头文件list.h1. **命名空间与模板**2. **核心数据结构**3. **构造函数**4. **模板参数设计**5. **…list的模拟实现一.list与vector1.底层结构的本质区别2.模拟实现的核心差异2.1数据存储的方式2.2 初始化的过程2.3 插入元素的操作2.4 删除元素的操作2.5 访问元素的效率3.总结二.头文件list.h1. **命名空间与模板**2. **核心数据结构**3. **构造函数**4. **模板参数设计**5. **核心成员**6. **构造与析构**7. **操作符重载**8. **类型定义**9. **迭代器接口**10. **内存管理**11. **构造函数**12. **初始化列表构造函数**13. **交换方法**14. **赋值运算符重载**15. **链表初始化**16. **清空操作**17. **首尾操作**18. **插入操作**19. **删除操作**三.头文件test.cpp1. **打印函数**2. **测试函数1**3. **测试函数3迭代器操作测试**4. **测试函数4插入删除测试**
一.list与vector
顺序表与链表因底层结构不同而导致的模拟实现差异。
1.底层结构的本质区别
顺序表像一排连续的“格子”所有元素按顺序依次放进这些格子里每个格子紧挨着下一个中间没有空隙。整个结构占用一整块连续的内存空间元素的位置比如第1个、第2个和它们在内存中的物理位置完全对应。链表像一串“珠子”每个珠子称为“节点”分为两部分一部分装数据另一部分装一个“指向”下一个珠子的“钩子”指针或引用。这些珠子在内存中可能分散在不同位置全靠钩子串联起来形成逻辑上的顺序物理位置和逻辑位置无关。
2.模拟实现的核心差异
基于上述底层结构两者的实现逻辑比如怎么存数据、怎么加元素、怎么删元素完全不同
2.1数据存储的方式顺序表
实现时需要先划定一块固定大小的连续空间比如先准备10个格子用一个“容器”管理这些格子同时记录当前装了多少元素比如已用3个格子和总共能装多少10个。元素的位置可以直接算出来第i个元素一定在第1个元素往后数i个格子的位置所以能直接找到。链表
实现时不需要预先划定空间而是用一个“头指针”记录第一个节点的位置每个节点都是单独创建的需要时才申请内存。每个节点除了数据必须带一个“钩子”指向后面的节点最后一个节点的钩子指向“空”表示结束。元素的位置无法直接算只能从第一个节点开始顺着钩子一个个找。2.2 初始化的过程顺序表
核心是“圈定初始空间”。比如一开始决定能装5个元素就申请一块能放下5个元素的连续内存然后标记“当前装了0个元素”。如果后续元素超过5个就需要“扩容”——重新申请一块更大的连续内存比如能装10个把原来的元素搬过去再用新空间替代旧空间。链表
核心是“确定起点”。通常初始化时要么让头指针指向“空”表示链表为空要么先创建一个“哨兵节点”不存数据专门用来统一操作头指针指向这个哨兵节点同时标记“当前有0个元素”。后续添加元素时再一个个创建新节点用钩子连起来即可不需要提前规划总容量。2.3 插入元素的操作顺序表
如果要在第i个位置插入元素必须先检查当前空间是否够用不够就扩容然后把第i个及之后的所有元素都往后“挪一个位置”腾出第i个格子最后把新元素放进第i个格子再更新“已用元素数”。
比如在“[1,2,3]”的第2个位置插4需要先把2、3往后挪变成“[1, ,2,3]”再放4结果是“[1,4,2,3]”。链表
如果要在第i个位置插入元素不需要挪动其他元素只需要
新建一个节点存入数据找到第i-1个节点把它的钩子从原来指向第i个节点改成指向新节点再让新节点的钩子指向原来的第i个节点。
比如在“1→2→3”的2前面插4只需要让1的钩子指向44的钩子指向2就变成“1→4→2→3”其他节点不需要动。2.4 删除元素的操作顺序表
如果要删除第i个元素需要先把第i个元素去掉然后把第i1个及之后的所有元素往前“挪一个位置”填补空缺最后更新“已用元素数”。
比如删除“[1,2,3,4]”的第2个元素2需要把3、4往前挪变成“[1,3,4]”中间不能留空隙否则不符合连续空间的特性。链表
如果要删除第i个元素只需要找到第i-1个节点把它的钩子从原来指向第i个节点改成指向第i1个节点然后把第i个节点的内存释放掉即可。
比如删除“1→4→2→3”中的4只需要让1的钩子直接指向24就被“摘”下来了其他节点位置不变。2.5 访问元素的效率顺序表
因为元素位置能直接计算第i个元素的位置 起点 i×元素大小所以访问任意位置的元素时一步就能找到效率很高时间复杂度O(1)。链表
因为元素位置靠钩子串联访问第i个元素时必须从第一个节点开始顺着钩子一个个数到第i个效率较低时间复杂度O(n)。3.总结
顺序表的底层是“连续内存”决定了它的实现依赖“空间预分配位置计算”操作时需要挪动元素但访问快
链表的底层是“离散节点指针”决定了它的实现依赖“动态创建指针串联”操作时无需挪动元素但访问慢。
这种底层结构的差异是两者实现方式和性能特性的根本原因。
二.头文件list.h
#pragma once
#includeiostream
using namespace std;namespace yl
{//定义单个结点结构templatetypename Tstruct _list_node{_list_nodeT* _prev;_list_nodeT* _next;T _data;_list_node(const T x):_data(x), _prev(nullptr), _next(nullptr){}};1. 命名空间与模板
代码位于yl命名空间内避免命名冲突使用模板templatetypename T实现泛型支持任意数据类型
2. 核心数据结构
_list_node结构体表示链表的节点包含三个成员变量
_prev指向前驱节点的指针_next指向后继节点的指针_data存储节点数据的模板类型变量3. 构造函数
带参数的构造函数_list_node(const T x)初始化节点数据_data为传入值将_prev和_next指针初始化为nullptr
设计特点
双向链表结构支持双向遍历节点独立管理前后连接关系模板设计保证了良好的扩展性// 链表迭代器模板// T: 数据类型Ref: 引用类型Ptr: 指针类型templatetypename T, class Ref, class Ptrstruct _list_iterator{typedef _list_iteratorT, Ref, Ptr Self; // 自身类型别名typedef _list_nodeT Node; // 节点类型别名Node* _node; // 指向当前节点的指针// 构造函数用节点指针初始化迭代器_list_iterator(Node* node) : _node(node) {}// 解引用操作符返回节点数据的引用Ref operator*() { return _node-_data; }// 箭头操作符返回节点数据的指针Ptr operator-() { return _node-_data; }// const版本箭头操作符用于常量迭代器Ptr operator-() const { return _node-_data; }// 前置移动到下一个节点并返回自身引用Self operator() {_node _node-_next;return *this;}// 后置返回当前迭代器副本然后移动到下一个节点Self operator(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 it) const {return it._node ! this-_node;}// 析构函数迭代器不拥有节点内存无需释放~_list_iterator() {}};
以上这段代码实现了双向链表的迭代器
4. 模板参数设计
三个模板参数T数据类型、Ref引用类型、Ptr指针类型通过分离引用和指针类型支持普通迭代器和常量迭代器
5. 核心成员
Node* _node指向当前节点的指针类型别名Self自身类型和Node节点类型
6. 构造与析构
构造函数接收节点指针初始化迭代器析构函数空实现迭代器不负责内存管理
7. 操作符重载
解引用操作符*返回节点数据引用箭头操作符-返回节点数据指针含const版本自增操作符前置和后置版本支持双向移动自减操作符--前置和后置版本支持双向移动不等比较!比较节点指针是否相等
迭代器特性
双向迭代器支持前后移动符合STL迭代器规范实现必要操作符轻量级设计仅包含一个指针成员
内存管理
迭代器不拥有节点内存节点生命周期由链表容器管理
templatetypename Tclass list {public:typedef _list_nodeT Node; // 链表节点类型typedef _list_iteratorT, T, T* iterator; // 普通迭代器typedef _list_iteratorT, const T, const T* const_iterator; // 常量迭代器// 返回指向第一个元素的迭代器iterator begin() { return _head-_next; }// 返回指向尾后位置的迭代器iterator end() { return _head; }// 常量版本的begin()和end()const_iterator begin() const { return const_iterator(_head-_next); }const_iterator end() const { return const_iterator(_head); }// 默认构造函数list() { empty_init(); }// 析构函数释放链表内存~list() {clear(); // 清空所有数据节点delete _head; // 释放头节点}// 拷贝构造函数list(const listT lt) {empty_init(); // 初始化空链表for (auto e : lt) { // 逐个复制元素push_back(e);}}这段代码实现了双向链表的容器类下面是重点内容概括
8. 类型定义
嵌套类型定义Node节点类型迭代器类型
iterator普通迭代器引用类型T指针类型T*const_iterator常量迭代器引用类型const T指针类型const T*9. 迭代器接口
begin()返回指向第一个元素的迭代器end()返回指向尾后位置的迭代器提供常量版本支持常量对象遍历
10. 内存管理
哨兵节点头节点_head设计
空链表时_head-_next _head简化边界条件处理
析构函数
调用clear()释放所有数据节点释放头节点内存11. 构造函数
默认构造函数调用empty_init()初始化空链表拷贝构造函数
初始化空链表通过范围for循环逐个复制元素. 关键方法
empty_init()初始化头节点构建循环链表clear()清空所有数据节点但保留头节点// 初始化列表构造函数list(initializer_listT il) {empty_init(); // 初始化空链表for (auto e : il) { // 使用初始化列表中的元素填充链表push_back(e);}}// 交换两个链表的内容void swap(listT lt) {std::swap(_head, lt._head); // 交换头节点指针std::swap(_size, lt._size); // 交换元素数量}// 赋值运算符重载listT operator(const listT il) {swap(il); // 通过交换实现拷贝赋值return *this;}// 初始化空链表void empty_init() {_head new Node(T()); // 创建头节点初始化为T的默认值_head-_next _head; // 头节点的next指向自身_head-_prev _head; // 头节点的prev指向自身_size 0; // 链表大小初始化为0}// 清空链表但保留头节点void clear() {iterator it begin();while (it ! end()) { // 遍历所有数据节点it erase(it); // 删除当前节点并获取下一个节点}}以上cpp代码继续完善了双向链表容器类新增了初始化列表构造、赋值运算符等功能
12. 初始化列表构造函数
支持listint lst {1, 2, 3}语法调用empty_init()初始化头节点通过范围for循环和push_back()逐个添加元素
13. 交换方法
swap(listT lt)交换两个链表的内容直接交换头节点指针和元素数量时间复杂度O(1)
14. 赋值运算符重载
采用拷贝并交换(Copy-and-swap)惯用法通过值传递接收参数自动处理自我赋值问题高效释放原有资源并获取新资源
15. 链表初始化
empty_init()
创建头节点初始化为T()构建循环链表结构(_head的prev和next指向自身)初始化_size为016. 清空操作
clear()
使用迭代器遍历所有数据节点调用erase(it)删除节点并更新迭代器保留头节点保持链表结构完整性// 在链表头部插入元素void push_front(const T x) { insert(begin(), x); }// 在链表尾部插入元素void push_back(const T x) { insert(end(), x); }// 删除链表尾部元素void pop_back() { erase(--end()); }// 删除链表头部元素void pop_front() { erase(begin()); }// 在指定位置前插入元素返回新节点的迭代器iterator insert(iterator pos, const T x) {Node* cur pos._node; // 当前位置的节点Node* newnode new Node(x); // 创建新节点Node* prev cur-_prev; // 当前位置的前一个节点// 调整指针连接新节点prev-_next newnode;newnode-_next cur;cur-_prev newnode;newnode-_prev prev;_size; // 更新链表大小return iterator(newnode); // 返回指向新节点的迭代器}// 删除指定位置的节点返回下一个位置的迭代器iterator erase(iterator pos) {Node* cur pos._node; // 当前位置的节点Node* prev cur-_prev; // 前一个节点Node* next cur-_next; // 下一个节点// 调整指针跳过当前节点prev-_next next;next-_prev prev;delete cur; // 释放当前节点内存_size--; // 更新链表大小return iterator(next); // 返回下一个位置的迭代器}private:Node* _head; // 头节点指针哨兵节点size_t _size 0; // 链表元素数量};
}以上代码完善了双向链表的核心操作接口
17. 首尾操作
push_front/push_back通过insert在首尾插入元素pop_front/pop_back通过erase删除首尾元素时间复杂度均为O(1)
18. 插入操作
insert(iterator pos, const T x)
在pos前插入新节点调整四个指针完成插入返回指向新节点的迭代器
保持迭代器有效性除被插入位置外
19. 删除操作
erase(iterator pos)
删除pos指向的节点调整两个指针跳过待删节点释放节点内存并返回下一位置迭代器
注意删除后原迭代器失效
指针调整逻辑
插入时需修改四个指针前驱节点的next、新节点的prev/next、后继节点的prev删除时需修改两个指针前驱节点的next、后继节点的prev头节点参与循环链表维护
数据成员
Node* _head哨兵节点构成循环链表size_t _size记录元素数量插入/删除时维护
三.头文件test.cpp
#includelist.h// 打印链表内容的模板函数
templateclass T
void print(const yl::listT lt) {auto it lt.begin();while (it ! lt.end()) {cout *it ;it;}cout endl;
}// 测试函数1测试基本功能
void test01() {yl::listint lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);lt1.push_back(5);print(lt1);
}// 测试函数2测试拷贝构造和初始化列表
void test02() {yl::listint lt1 { 0, 1, 2, 3, 4, 5 };yl::listint lt2 lt1;print(lt2);
}1. 打印函数
模板函数print(const yl::listT lt)使用迭代器遍历链表并输出元素支持任意可输出类型需重载operator
2. 测试函数1
功能测试基本插入操作步骤
创建空链表lt1尾插5个元素1-5打印链表预期输出1 2 3 4 5
验证点
push_back功能迭代器遍历正确性测试函数2
功能测试初始化列表和拷贝构造步骤
使用初始化列表构造lt1元素0-5通过拷贝构造创建lt2打印lt2预期输出0 1 2 3 4 5
验证点
初始化列表构造函数拷贝构造函数深拷贝// 测试函数3测试迭代器操作
void test03() {yl::listint lt;lt.push_back(10);lt.push_back(20);lt.push_back(30);cout 测试前置: ;auto it lt.begin();it;cout *it endl;cout 测试后置: ;it lt.begin();it;cout *it endl;cout 测试前置--: ;it lt.end();--it;cout *it endl;cout 测试后置--: ;it lt.end();it--;cout *it endl;
}// 测试函数4测试插入和删除操作
void test04() {yl::listint lt;lt.push_back(1);lt.push_back(3);lt.push_back(4);auto it lt.begin();it;lt.insert(it, 2);cout 插入后: ;print(lt);it lt.begin();it;lt.erase(it);cout 删除后: ;print(lt);
}int main() {cout 测试基本功能 endl;test01();cout \n 测试拷贝构造和初始化列表 endl;test02();cout \n 测试迭代器操作 endl;test03();cout \n 测试插入和删除操作 endl;test04();return 0;
}
这段代码新增了迭代器操作和插入删除功能的测试以下是重点内容概括
3. 测试函数3迭代器操作测试
功能验证迭代器自增自减操作步骤
创建链表lt并插入元素10, 20, 30测试前置移动到第二个元素输出20测试后置移动到第二个元素输出20测试前置--从end()移动到最后一个元素输出30测试后置--从end()移动到最后一个元素输出30
验证点
双向迭代器的移动正确性前置/后置操作符的语义差异4. 测试函数4插入删除测试
功能验证插入删除接口步骤
创建链表lt并插入元素1, 3, 4在第二个位置插入2链表变为1, 2, 3, 4删除第二个位置元素链表变为1, 3, 4
验证点
insert在指定位置前插入元素erase正确删除元素并返回下一位置迭代器
