C++ list链表模拟实现

这篇具有很好参考价值的文章主要介绍了C++ list链表模拟实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

前言:

模拟实现:

迭代器的实现:

list类功能函数实现:

 初始化成空函数(empty_init):

构造函数:

 拷贝构造函数:

尾插(push_back):

插入(insert):

删除(erase):

 尾删(pop_back):

头插(push_front):

头删(pop_front):

 清理(clear):

 交换(swap):

赋值重载:

析构:

代码


前言:

  在学习完list的基本功能后,我自己模拟实现了一个list,具备一些常用的基本功能,这篇博客用来分享并记录,方便后续复习。

模拟实现:

因为list中可以存很多种类型,比如int,char,float,等,还可能是自定义类型,所以我打算使用类模板,先把简单的节点弄成类模板:

C++ list链表模拟实现,数据结构,c++,c++,链表,开发语言,List模拟实现,标准库,STL

接下来就是list的类模板:

C++ list链表模拟实现,数据结构,c++,c++,链表,开发语言,List模拟实现,标准库,STL

迭代器的实现:

  这里迭代器的模拟实现不能像vector一样简单的使用原生指针,因为链表的地址不是连续的,我们在进行原生指针的++或者--操作时,是无法实现访问下一个或者上一个元素的,那该怎样实现简单的对迭代器++或者--就能实现访问下一个或者上一个元素呢?

  这里有一个巧妙地方法就是借助类,没错,我们将原生指针放入一个名为Listiterator的类里面,然后在这个类中,使用运算符重载,重载++,--,*,->等运算符,就能像库里面一样使用迭代器了。

C++ list链表模拟实现,数据结构,c++,c++,链表,开发语言,List模拟实现,标准库,STL

 上图的Ref和Ptr模板分别是传引用和传指针,用于应对const 迭代器的使用 ,保证const迭代器可以修改迭代器,但不能修改该迭代器指向的内容。接下来开始在这个类中重载各种运算符:

C++ list链表模拟实现,数据结构,c++,c++,链表,开发语言,List模拟实现,标准库,STL

这几个运算符重载都很简单,应该都能看懂,接下来进入list类模板中,就行list的功能函数实现:

list类功能函数实现:

先来几个简单但又很重要的函数实现:

C++ list链表模拟实现,数据结构,c++,c++,链表,开发语言,List模拟实现,标准库,STL

 初始化成空函数(empty_init):

C++ list链表模拟实现,数据结构,c++,c++,链表,开发语言,List模拟实现,标准库,STL

构造函数:

有了上面这个函数后,构造函数就简单了,直接复用即可:

C++ list链表模拟实现,数据结构,c++,c++,链表,开发语言,List模拟实现,标准库,STL

 拷贝构造函数:

C++ list链表模拟实现,数据结构,c++,c++,链表,开发语言,List模拟实现,标准库,STL

尾插(push_back):

C++ list链表模拟实现,数据结构,c++,c++,链表,开发语言,List模拟实现,标准库,STL

插入(insert):

C++ list链表模拟实现,数据结构,c++,c++,链表,开发语言,List模拟实现,标准库,STL

删除(erase):

C++ list链表模拟实现,数据结构,c++,c++,链表,开发语言,List模拟实现,标准库,STL

 尾删(pop_back):

C++ list链表模拟实现,数据结构,c++,c++,链表,开发语言,List模拟实现,标准库,STL

头插(push_front):

C++ list链表模拟实现,数据结构,c++,c++,链表,开发语言,List模拟实现,标准库,STL

头删(pop_front):

C++ list链表模拟实现,数据结构,c++,c++,链表,开发语言,List模拟实现,标准库,STL

 清理(clear):

C++ list链表模拟实现,数据结构,c++,c++,链表,开发语言,List模拟实现,标准库,STL

 交换(swap):

C++ list链表模拟实现,数据结构,c++,c++,链表,开发语言,List模拟实现,标准库,STL

赋值重载:

C++ list链表模拟实现,数据结构,c++,c++,链表,开发语言,List模拟实现,标准库,STL

 此处传值传参的妙处:

list1=iist2,进入函数此时lt是list2的拷贝,因为swap是成员函数,所以有一个隐含的this指针,此时只需传参lt就可以完成lt和list1交换,间接完成对list1的赋值,同时没有改变list2,只是改变了lt,而lt出作用域后就会消失。

析构:

C++ list链表模拟实现,数据结构,c++,c++,链表,开发语言,List模拟实现,标准库,STL文章来源地址https://www.toymoban.com/news/detail-848910.html

代码:

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
namespace sxk
{   
	template<class T>
	struct ListNode
	{
		ListNode<T>* next;//下一个节点的地址
		ListNode<T>* prev;//上一个节点的地址
		T val;//数据

		ListNode(const T& x = T())//节点的构造函数
			:next(nullptr)
			, prev(nullptr)
			, val(x)
		{}
	};
	template<class T,class Ref,class Ptr>
	struct Listiterator
	{
		typedef ListNode<T> Node;
		typedef Listiterator<T, Ref, Ptr> Self;
		typedef Listiterator<T, T&, T*> iterator;
		typedef Listiterator<T, const T&, const T*> const_iterator;

		Node* _node;

		Listiterator(Node* node)//迭代器的构造函数
			:_node(node)
		{}

		Ref operator*()
		{
			return _node->val;
		}

		Ptr operator->()
		{
			return &_node->val;
		}

		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)
		{
			return _node == it._node;
		}

		bool operator!=(const Self& it)
		{
			return _node != it._node;
		}
	};
	template<class T>
	class list
	{
	public:
		typedef ListNode<T> Node;
		typedef Listiterator<T, T&, T*> iterator;
		typedef Listiterator<T, const T&, const T*> const_iterator;
		iterator begin()
		{
			return _head->next;
		}

		iterator end()
		{
			return _head;
		}

		const_iterator begin()const
		{
			return _head->next;
		}

		const_iterator end()const
		{
			return _head;
		}

		size_t size()
		{
			return _size;
		}

		bool empty()
		{
			return _size == 0;
		}

		void empty_init()
		{
			_head = new Node;//new出头节点
			_head->next = _head;//头节点下一个指向自己
			_head->prev = _head;//头节点上一个指向自己

			_size = 0;
		}


		list()//构造函数
		{
			empty_init();
		}

		list(const list<T>& lt)//拷贝构造函数
		{
			empty_init();//先初始化成只有一个头节点
			for (auto& x : lt)
			{
				push_back(x);//直接尾插即可
			}
		}

		list<T>& operator=(const list<T> lt)//lt是赋值类的拷贝
		{
			swap(lt);//交换lt和this,可以完成赋值并不影响赋值类
			return *this;
		}

		void swap(const list<T>& lt)
		{
			std::swap(_head, lt._head);//直接调用库里的swap交换两个成员变量即可
			std::swap(_size, lt._size);
		}

		void clear()
		{
			iterator it = begin();
			while (it != end())//遍历删除
			{
				it = erase(it);//更新it,防止erase后迭代器失效
				it++;
			}
		}

		~list()
		{
			clear();//先清理,只保留一个头节点
			delete _head;//释放头节点
			_head = nullptr;
		}

		void push_back(const T& x)
		{
			Node* newnode = new Node;//new出新节点
			newnode->val = x;//给新节点赋值
			Node* tail = _head->prev;//记录尾节点

			tail->next = newnode;//尾节点的下一个指向新节点
			newnode->next = _head;//新节点的next指向头节点
			newnode->prev = tail;//新节点的prev指向之前旧的尾节点
			_head->prev = newnode;//头节点的prev指向新节点
			_size++;
		}

		void push_front()
		{
			insert(begin());
		}

		void pop_back()
		{
			erase(--end());//直接复用erase,注意end指向的是头节点,所以要--
		}

		void pop_front()
		{
			erase(begin());
		}

		void insert(iterator pos, const T& x)//在pos位置前插入x
		{
			Node* newnode = new Node;//new出新节点
			newnode->val = x;//给新节点赋值
			Node* cur = pos._node;//记录当前pos位置
			Node* prev = cur->prev;//记录pos前一个

			prev->next = newnode;//pos前一个节点的next指向新节点
			newnode->next = cur;//新节点的next指向pos节点
			newnode->prev = prev;//新节点的prev指向pos前一个节点
			cur->prev = newnode;//pos的prev指向新节点
			_size++;
		}

		iterator erase(iterator pos)//删除pos位置的值
		{
			Node* cur = pos._node;//记录pos位置的节点
			Node* prev = cur->prev;//记录pos的前一个节点
			Node* next = cur->next;//记录pos的下一个节点

			prev->next = cur->next;//pos的前一个节点的next指向pos的下一个节点
			next->prev = prev;//pos的下一个节点的prev指向pos的前一个节点
			delete cur;//释放pos位置的节点
			cur = nullptr;//置为空
			_size--;
			return iterator(next);//防止erase后迭代器失效,更新迭代器
		}

	private:
		Node* _head;
		size_t _size;
	};

	void Print_List(const list<int>& lt)
	{
		list<int>::const_iterator it = lt.begin();
		while (it != lt.end())
		{
			cout << (*it) << " ";
			it++;
		}
		cout << endl;
	}
}

到了这里,关于C++ list链表模拟实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C++ list链表模拟实现

    目录 前言: 模拟实现: 迭代器的实现: list类功能函数实现:  初始化成空函数(empty_init): 构造函数:  拷贝构造函数: 尾插(push_back): 插入(insert): 删除(erase):  尾删(pop_back): 头插(push_front): 头删(pop_front):  清理(clear):  交换(swap): 赋值重载:

    2024年04月12日
    浏览(40)
  • Redis数据结构——链表list

    链表是一种常用的数据结构,提供了顺序访问的方式,而且高效地增删操作。 Redis中广泛使用了链表,例如:列表的底层实现之一就是链表。 在Redis中,链表分为两部分:链表信息 + 链表节点。 链表节点用来表示链表中的一个节点,基础的值和指向前和后的指针 链表信息,

    2024年02月13日
    浏览(39)
  • 【数据结构篇C++实现】- 线性表 - 顺序表和链表

    友情链接:C/C++系列系统学习目录 故事导入: 幼儿园放学时,一个班级的小朋友,一个跟着一个排队出校,有一个打头,有一个收尾,当中的小朋友每一个都知道他前面和后面的一个是谁,就如同一根线把他们串联了起来。如此具有像线一样的性质的表就叫线性表 线性表(

    2024年02月07日
    浏览(57)
  • 【C++】list链表容器功能模拟实现

    目录 介绍 一,容器的结构设计 二,构造函数与赋值运算符 三,析构函数 四,list容器接口 1,begin和end 2,insert和erase 3,其它常用接口函数         上一次介绍了list双向链表容器的迭代器模拟,这次模拟实现list的简单功能,尤其要注意 构造函数、析构函数、以及赋值运算

    2024年02月20日
    浏览(41)
  • [数据结构 C++] AVL树的模拟实现

    问题引入: 在上一篇文章中,我们提到了二叉搜索树在插入时,可能会形成单边树,会降低二叉搜索的性能。因此我们需要平衡二叉搜索树,降低二叉搜索树的高度,使得二叉搜索树趋于一颗完全二叉树的样子,这样就可以提高二叉搜索树的性能。本篇文章就来介绍一种平衡

    2024年02月03日
    浏览(52)
  • 数据结构与算法 | 链表(Linked List)

    链表(Linked List)是一种线性数据结构,它由一系列节点(Node)组成,每个节点包含两部分:数据和指向下(上)一个节点的引用(或指针)。链表中的节点按照线性顺序连接在一起(相邻节点不需要存储在连续内存位置),不像数组一样存储在连续的内存位置。链表通常由

    2024年02月08日
    浏览(50)
  • C++数据结构与算法详解:链表、栈、队列、树、二叉树和图结构的实现与应用

    链表是一种常见的数据结构由一系列节点按顺序连接而成,一般每个节点包含一个数据元素和一个指向下一个节点的引用。 链表有多种类型: 单向链表:每个节点只有一个指向下一个节点的引用 双向链表:每个节点有一个指向前一个节点和一个指向后一个节点的引用 循环链

    2024年02月04日
    浏览(51)
  • 数据结构英文习题解析-第二章 链表List

    前言:最近快到FDS考试了,po重刷了一下学校的题目,自己整理了一些解析orz 因为po在自己找解析和学习的过程中非常痛苦,所以在此共享一下我的题目和自己写的解题思路,欢迎各位指出错误~全章节预计会陆续更新,可在专栏查看~ HW2 1. For a sequentially stored linear list of leng

    2024年04月11日
    浏览(53)
  • [数据结构进阶 C++] 二叉搜索树(BinarySearchTree)的模拟实现

    二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树: 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值 它的左右子树也分别为二叉搜索树 我们先给出两个示例: 此

    2024年02月04日
    浏览(42)
  • 【数据结构】栈和队列(链表模拟队列)

      学习本章节必须具备 单链表的前置知识, 建议提前学习:点击链接学习:单链表各种功能函数 细节 详解 本章节是学习用 单链表模拟队列 1. 单链表实现队列 思路如下 队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先 进先出

    2024年04月27日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包