实现一个简单地list类

港控/mmm° 2023-01-16 11:13 131阅读 0赞

![在这里插入图片描述][2021042516372558.png]

### 实现简单的list ###

*  原理:
 *  代码实现:

# 原理: #

list的储存原理其实就是储存在一个双向带头循环链表,我们只要根据这个进行实现就可以了.  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70]

# 代码实现: #

**对于简单的list的实现=构造函数+析构函数+输入函数**

#include<string> 
    using namespace std;
    
    
    template <class T>		
    struct ListNode{ 			//这里是类的私有类的体现,我们简化类的private进行了封装
    	T _data;		//存放的数据
    	ListNode<T>* _next;		//对应的next节点
    	ListNode<T>* _prev;		//对应的prev节点
    
    	ListNode(const T& val = T())		//输入一个值,对其中的next和prev进行简单的创建节点
    		:_data(val)
    		, _next(nullptr)
    		, _prev(nullptr)
    	{ }
    
    };
    
    
    template<class T>
    class List{ 		//list类
    
    private:
    	ListNode<T>* _header;		//这里的私有的,也就是上面封装出去的函数
    
    
    public:	//公有类
    
    	typedef ListNode<T> Node;
    	typedef Node* pNode;
    
    	List()	//构造函数对双向带头循环链表进行初始化
    		:_header(new Node())
    	{ 	//对于一个简单的list的创建,要让其内部的两个指针指向自己,才能完成初始化
    
    		_header->_next = _header->_prev = _header;
    	}
    
    	List(size_t n, const T& val = T())		//构造函数的赋值操作
    		:_header(new Node())
    	{ 
    		_header->_next = _header->_prev = _header;		//对应的节点的指向
    
    		for (size_t i = 0; i < n; ++i){ 		//循环语句按个进行插入
    
    			pushBack(val);
    		}
    	}
    
    	template<class inputIterator>	//运用迭代器使用
    	List(inputIterator first, inputIterator last)
    		:_header(new Node())
    	{ 
    		_header->_next = _header->_prev = _header;		//节点的指向
    		while (first != last){ 
    
    			pushBack(*first);		//解引用进行尾插
    			++first;
    		}
    	}
    
    
    	void pushBack(const T& val){ 
    
    		Node* prev = _header->_prev;
    		Node* newNode = new Node(val);
    
    		prev->_next = newNode;	//和上一个元素之间的指向
    		newNode->_prev = prev;
    
    		newNode->_next = _header; //和下一个元素,也就是对应的头结点之间的指向
    		_header->_prev = newNode;
    	}
    
    	~List(){ 	//析构函数
    
    		if (_header){ 		//存在头节点 
    
    			Node* node = _header->_next;	//取出头结点指向的下一个数据
    			while (node != _header){ 		//循环遍历头结点后面指向的数据
    
    				Node* next = node->_next;	//1.先让节点指向下一位,获取下一位的起始地址
    				delete node;				//2.删除上面的节点
    				node = next;				//3.让node指向下一位
    			}
    			delete _header;		//最后将后面的数据删除完毕后再将头结点进行删除
    			_header = nullptr;	//将头结点变为空
    		}
    	}
    };

对于尾插的逻辑有点难理解,我们要画图进行理解,我在这里给出步骤,大家自己画图理解:

**1.要尾插数据,首先获取到头结点和最后一个数据的地址  
2.将原来的数据末尾的next节点和新的末尾数据的prev进行互相的指向  
3.将头结点的prev节点和新插入的数据的next节点进行互相的指向**

使用:

void test(){ 
    
    	List<int>lst;
    	lst.pushBack(1);
    	lst.pushBack(2);
    	lst.pushBack(3);
    	lst.pushBack(4);
    
    	List<int>lst2((size_t)10, 5);
    
    	string str = "123456";
    	List<char>lst3(str.begin(), str.end());
    
    }

简单的list的实现.

[2021042516372558.png]: /images/20221022/537e006bee014f559d5e0d9ead638387.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70]: /images/20221022/582c7cb6a59841a7b2325820c24710ea.png