STL-List模拟

1.List是一个双向循环链表：

常用知识

• 基本特性：list是一个双向链表容器，这意味着其内存空间不连续。在任何位置进行插入和删除操作都能在常数时间（O (1)）内完成，但不支持像数组那样的随机存取（访问某个位置元素的时间复杂度为 O (n) ，需要从链表头或尾开始遍历）。
• 迭代器：
  • 提供了begin()和end()用于正向遍历，rbegin()和rend()用于反向遍历。
  • 在list上进行插入和删除操作后，除了指向被删除元素的迭代器失效外，其他迭代器仍然有效，因为节点的内存地址没有发生整体变动。
• 常用成员函数：
  • 插入相关：push_back()在链表尾部插入元素；push_front()在链表头部插入元素；insert()可以在指定迭代器位置插入一个或多个元素。
  • 删除相关：pop_back()删除链表尾部元素；pop_front()删除链表头部元素；erase()删除指定迭代器位置或指定范围内的元素；clear()清空整个链表。
  • 其他：size()获取链表中元素的个数；empty()判断链表是否为空。
• 适用场景：当需要频繁地在容器中间进行插入和删除操作，而对随机访问元素的需求较少时，list是一个很好的选择。例如，实现一个任务队列，新任务可以随时插入，已完成的任务可以随时删除。

 其次需要注意的一个常用的小地方：

list中它用的sort是自己带的：

链表是不能用sort的，因为sort参数需要的是底层是随机的迭代器 ，而list是底层是双向的迭代器。所以list的自己给自己做了一个排序函数sort用法

模拟函数常用代码：

namespace hush
{
	template<class T>
	struct list_node
	{
		T _data;
		list_node<T>* next;
		list_node<T>* prev;

		//构造函数
		list_node(const T&x=T()):_data(x),next(nullptr),prev(next)
		{

		}
	};
	template<class T>
	struct __list_iterator 
	{
		// 将list_node<T> 类型重命名为Node
		typedef list_node<T> Node;
		// 将__list_iterator<T> 类型重命名为self
		typedef __list_iterator<T> self;
		// 成员变量，指向链表节点
		Node* _node;

		// 构造函数，接受一个Node指针初始化_node
		__list_iterator(Node* node) : _node(node) 
		{}

		// 前置递增运算符重载
		self& operator++() 
		{
			_node = _node->_next;
			return *this;
		}

		T& operator*()
		{
			return _node->_data;
		}

		bool operator!=(const self& s)
		{
			return _node != s._node;
		}
	};
	template<class T>
	class list
	{
		typedef list_node<T> Node;
	public:
		typedef __list_iterator<T> iterator;
		/*list() : _head(new Node) {
			_head->_next = _head;
			_head->_prev = _head;
		}*/

		iterator begin()
		{
			return _head->next;
		}
		iterator end()
		{
			return _head->prev;
		}
		void empty_init()
		{
			_head = new Node;
			_head->next = _head;
			_head->prev = _head;
		}
		list()
		{
			empty_init();
		}
		void push_back(const T& x) 
		{
			双向循环链表的结构特点
			//双向循环链表有一个头哨兵节点_head ，它并不存储实际的数据。从逻辑结构上看，
			//_head->next指向的是链表中的第一个有效数据节点（如果链表不为空），
			//而_head->_prev指向的是链表的最后一个节点 。
			//Node* tail = _head->_prev;
			Node* newnode = new Node(x);

			tail->_next = newnode;
			newnode->_prev = tail;

			newnode->_next = _head;
			_head->_prev = newnode;
		}

		iterator insert(iterator pos, const T& x) 
		{
			Node* cur = pos._node;
			Node* newnode = new Node(x);
			Node* prev = cur->_prev;

			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;

			return iterator(newnode);
		}
		void erase(iterator pos) 
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;

			delete cur;
			prev->_next = next;
			next->_prev = prev;
		}

		void clear()
		{
			iterator it = begin();
			while (it!=end())
			{
				it=erase(it);
			}
		}

		list(const list<T>& it)
		{
			empty_init();
			for (auto I : it)
			{
				push_back(I);
			}

			
		}

		//lt1=lt3
		list<int>& operator=(const list<int>& lt) 
		{
			if (this != &lt) 
			{
				clear();
				for (auto e : lt) 
				{
					push_back(e);
				}
			}
			return *this;
		}

		void swap(list<T>& lt)
		{
			std::swap(_head, lt._head);
		}
		size_t size()
		{
			return _size;
		}

		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}

	private:

		Node* _head;
		size_t _size;
	};
}

常见面试题

• 请描述list和vector的区别
  • 底层实现：vector底层是动态数组，内存连续；list是双向链表，内存不连续。
  • 访问方式：vector支持随机访问，通过下标访问元素时间复杂度为 O (1)；list不支持随机访问，访问元素需遍历链表，时间复杂度为 O (n)。
  • 插入和删除操作：vector在尾部插入和删除元素效率较高，时间复杂度为 O (1) ，但在中间插入或删除元素时，需要移动后续元素，时间复杂度为 O (n)；list在任何位置插入和删除元素时间复杂度都是 O (1) ，不需要移动其他元素。
  • 内存管理：vector有容量的概念，当元素数量超过容量时会自动扩容，扩容涉及内存分配和数据拷贝；list每个节点单独分配内存，没有容量限制。
  • 迭代器特性：vector在插入或删除元素后，迭代器可能失效；list插入或删除元素后，除了指向被删除元素的迭代器外，其他迭代器通常不会失效。
• list进行插入和删除操作的时间复杂度是常数，原因是什么：因为list是双向链表结构，插入时只需修改插入位置前后节点的指针指向；删除时，只需修改被删除节点前后节点的指针，将它们直接相连，这两个操作都与链表中元素的数量无关，所以时间复杂度是 O (1)。

练习题：

• 实现一个函数，使用list统计字符串中每个字符出现的次数

#include <list>
#include <string>
#include <iostream>

void countChars(const std::string& str) {
    std::list<std::pair<char, int>> charCountList;
    for (char c : str) {
        bool found = false;
        for (auto it = charCountList.begin(); it != charCountList.end(); ++it) {
            if (it->first == c) {
                it->second++;
                found = true;
                break;
            }
        }
        if (!found) {
            charCountList.push_back({c, 1});
        }
    }
    for (const auto& pair : charCountList) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
}

使用方式：countChars("hello"); 。该函数通过遍历字符串，利用list存储每个字符及其出现的次数。

• 如何对list中的元素进行排序
  list类模板提供了成员函数sort() ，可直接对链表进行排序。例如std::list<int> myList = {3, 1, 2}; myList.sort();。此外，也可以将list的元素拷贝到vector中，利用std::sort算法排序后再拷贝回list ，但这种方式会增加额外的空间和时间开销。