【C++】list的使用及底层实现原理

爱被打了一巴掌 2024-04-22 22:18 32阅读 0赞

![a518bd4c19214f9bb3c98fd6f6ef8796.gif][]

> 本篇文章对list的使用进行了举例讲解。同时也对底层实现进行了讲解。底层的实现关键在于迭代器的实现。希望本篇文章会对你有所帮助。

> **文章目录**
> 
> 一、list的使用
> 
> 1、1 list的介绍
> 
> 1、2 list的使用
> 
> 1、2、1 list的常规使用 
> 
> 1、2、2 list的sort讲解
> 
> 二、list的底层实现
> 
> 2、1 初构list底层模型
> 
> 2、2 迭代器的实现
> 
> 2、2、1 普通迭代器
> 
> 2、2、2 const 迭代器
> 
> 2、3 完善其他底层实现
> 
> 三、总结
> 
> --------------------
> 
> **?♂️ 作者：@Ggggggtm ?♂️**
> 
> **? 专栏：C++ ?**
> 
> **? 标题：list****讲解?**
> 
>  **❣️ 寄语：与其忙着诉苦，不如低头赶路，奋路前行，终将遇到一番好风景 ❣️**
> 
> ![27194d7384804799a5a468422891bff4.png][]

## 一、list的使用 ##

### 1、1 list的介绍 ###

> C++中的标准模板库（STL）提供了许多容器类来处理不同类型的数据，其中之一就是list。list是一个**双向链表容器**，它可以在其内部存储各种类型的元素，并且支持**动态地添加、删除和修改元素**。

> 以下是list的几个主要特点：
> 
> 1.   list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
> 2.  list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
> 3.  list与forward\_list非常相似：最主要的不同在于forward\_list是单链表，只能朝前迭代，已让其更简单高效。
> 4.  与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
> 5.  与其他序列式容器相比，list和forward\_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素）。
> 
> list的特点主要是基于**list底层实现是双向带头循环链表**。

### 1、2 list的使用 ###

#### 1、2、1 list的常规使用 ####

> 使用list容器时，可以使用其公共接口提供的各种方法来执行常见的操作，如插入、删除、访问等。常用的成员函数包括：
> 
>  *  push\_back(element)：将element添加到列表的末尾。
>  *  push\_front(element)：将element添加到列表的开始位置。
>  *  pop\_back()：从列表的末尾删除元素。
>  *  pop\_front()：从列表的开始位置删除元素。
>  *  insert(position, element)：在指定位置插入element。
>  *  erase(position)：删除指定位置上的元素。
>  *  size()：返回列表中的元素数量。
>  *  empty()：检查列表是否为空。
>  *  clear()：清空列表中的所有元素。
>  *  sort()：对列表元素排序。
> 
> 除了以上常用函数外，list还提供了许多其他功能，如合并、翻转等。下面我们结合实际例子来理解以下上述的list的使用。

> 具体代码如下：
> 
>     void test_list()
>     {
>     	// 创建一个列表
>     	list<int> numbers;
>     
>     	// 添加元素到列表末尾
>     	numbers.push_back(1);
>     	numbers.push_back(2);
>     	numbers.push_back(3);
>     	numbers.push_back(4);
>     	numbers.push_back(5);
>     
>     	//打印链表中的元素
>     	list<int>::iterator it = numbers.begin();
>     	while (it != numbers.end())
>     	{
>     		cout << *it << " ";
>     		++it;
>     	}
>     	cout << endl;
>     
>     	//添加元素到列表头部
>     	numbers.push_front(10);
>     	numbers.push_front(20);
>     	numbers.push_front(30);
>     	numbers.push_front(40);
>     	
>     	//删除链表尾部元素
>     	numbers.pop_back();
>     
>     	for (auto e : numbers)
>     	{
>     		cout << e << " ";
>     	}
>     	cout << endl;
>     
>     	// 插入元素到指定位置
>     	auto pos = find(numbers.begin(), numbers.end(), 3);
>     	if (pos != numbers.end())
>     	{
>     		// pos是否会失效？不会
>     		numbers.insert(pos, 30); 
>     	}
>     
>     	for (auto e : numbers)
>     	{
>     		cout << e << " ";
>     	}
>     	cout << endl;
>     
>     	//删除指定位置元素
>     	pos = find(numbers.begin(), numbers.end(), 4);
>     	if (pos != numbers.end())
>     	{
>     		// pos是否会失效？会 删除后pos位置直接会被释放
>     		numbers.erase(pos);
>     		// cout << *pos << endl;
>     	}
>     
>     	for (auto e : numbers)
>     	{
>     		cout << e << " ";
>     	}
>     	cout << endl;
>     
>     	// 对列表进行升序排序
>     	numbers.sort();
>     
>     	// 输出列表元素
>     	for (int number : numbers) {
>     		cout << number << " ";
>     	}
>     	cout << endl;
>     
>     }
>     int main()
>     {
>     	test_list();
>     	return 0;
>     }
> 
> 我们再看一下实际的运行结果：
> 
> ![3e2108a410aa418daf05b89937b31803.png][]
> 
> 如上结果可以对应着代码一起看，对list的使用理解会容易一点。

#### 1、2、2 list的sort讲解 ####

> list容器内部自己提供了sort函数。为什么呢？我们知道，STL中有一个重要组件就是算法，其中提供了sort函数，那这两者又有什么区别呢？
> 
> 首先**STL中的算法库中提供的sort函数底层使用的是快排**。list中的迭代器并不支持随机访问迭代器，所以不能使用STL算法库中提供的sort。**list容器中的sort函数底层使用的是归并排序**。两者是有所区别的。
> 
> 我们先来测试一下两者的效率，看看是否属于一个级别的。测试代码如下：
> 
>     void test_op()
>     {
>     	srand(time(0));
>     	const int N = 100000;
>     	vector<int> v;
>     	v.reserve(N);
>     
>     	list<int> lt1;
>     	list<int> lt2;
>     
>     	for (int i = 0; i < N; ++i)
>     	{
>     		auto e = rand();
>     		//v.push_back(e);
>     		lt1.push_back(e);
>     		lt2.push_back(e);
>     	}
>     
>     	// 拷贝到vector排序，排完以后再拷贝回来
>     	int begin1 = clock();
>     	for (auto e : lt1)
>     	{
>     		v.push_back(e);
>     	}
>     	sort(v.begin(), v.end());
>     	size_t i = 0;
>     	for (auto& e : lt1)
>     	{
>     		e = v[i++];
>     	}
>     	int end1 = clock();
>     
>     	int begin2 = clock();
>     	// sort(lt.begin(), lt.end());
>     	lt2.sort();
>     	int end2 = clock();
>     
>     	printf("copy vector sort:%d\n", end1 - begin1);
>     	printf("list sort:%d\n", end2 - begin2);
>     }
>     int main()
>     {
>     	test_op();
>     	return 0;
>     }
> 
> 针对上述代码，讲解一下比较的思路。首先我们创建两个链表。随机生成一百万个元素加入到链表中。一个链表用于把元素拷贝到vector排序，然后调用STL算法库中的sort函数，排完以后再拷贝回来，计算此过程的时间。另一个链表直接调用自己容器内的sort进行排序，计算排序时间。我们看一下时间对比：
> 
> ![151a7d74187842d2897e767aa1c56672.png][]
> 
> 我们发现，在debug版本下调试，差距基本上不大。但是在release版本下调试，还是有一定差距的。发现在release版本下，拷贝到vector中排序更快。数据量越大，效果会越明显。所以，当数据量大的时候，我们尽量去使用拷贝到vector中，调用STL算法库中的sort函数去排序。

## 二、list的底层实现 ##

### 2、1 初构list底层模型 ###

> 我们知道list底层是带头双向循环列表后，我们可大概构建一个模型。如下：
> 
>     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(nullptr)
>     		{}
>     	};
>     
>         template<class T>
>     	class list
>     	{
>     		typedef list_node<T> Node;
>     	public:
>     		list()
>     		{
>     			_head = new Node;
>     			_head->_next = _head;
>     			_head->_prev = _head;
>     		}
>     
>     		void push_back(const T& x)
>     		{
>     			Node* tail = _head->_prev;
>     			Node* newnode = new Node(x);
>     
>     			tail->_next = newnode;
>     			newnode->_prev = tail;
>     			newnode->_next = _head;
>     			_head->_prev = newnode;
>     		}
>     	private:
>     		Node* _head;
>     	};
> 
> 上述代码中，也实现了尾插。尾插来说相对简单，这里就不再做过解释。关键是list的迭代器的底层实现。

### 2、2 迭代器的实现 ###

#### 2、2、1 普通迭代器 ####

> 我们先想一下vector和string的迭代器。 vector和string的迭代器底层无非就是指针，该指针指向元素内容。支持++、--、解引用等操作。
> 
> list的迭代器底层能直接是Node\* 指针吗？假如是Node\* 指针，我们 ++ 和 -- 操作，是不能够找到下一个元素的。因为链表本身每个节点的地址不是连续的。其次，我们解引用操作并不是找到节点所存储的值，而是找到的是该节点。
> 
> 综上主要原因，为了解决上述情况，C++ list 的底层迭代器采用了把 Node\* 封装成了一个类。在该类中重载运算符，以达到我们想要的效果。我们可结合如下代码理解一下：
> 
>     template<class T>
>     	struct __list_iterator
>     	{
>     		typedef list_node<T> Node;
>     		Node* _node;
>             
>             // 构造函数
>     		__list_iterator(Node* node)
>     			:_node(node)
>     		{}
>     
>             // 解引用操作，返回节点所存储的值
>     		T& operator*()
>     		{
>     			return _node->_val;
>     		}
>     
>             // 前置++
>             __list_iterator<T>& operator++()
>     		{
>     			_node = _node->_next;
>     			return *this;
>     		}
>     
>             // 后置++ 返回 ++前的结果
>     		__list_iterator<T> operator++(int)
>     		{
>     			__list_iterator<T> tmp(*this);
>     
>     			_node = _node->_next;
>     
>     			return tmp;
>     		}
>             
>             // 比较的节点的地址是够相同
>     		bool operator!=(const __list_iterator<T>& it)
>     		{
>     			return _node != it._node;
>     		}
>     
>     		bool operator==(const __list_iterator<T>& it)
>     		{
>     			return _node == it._node;
>     		}
>     	};

> 我们再把封装后的迭代器类融入到 list 类中。为什么还要融入到 list 类中呢？融入到 list 中又该怎么使用呢？我们先看如下代码：
> 
>     list<int> lt;
>     		lt.push_back(1);
>     		lt.push_back(2);
>     		lt.push_back(3);
>     		lt.push_back(4);
>             list<int>::iterator it = lt.begin();
> 
> 我们定义 list 迭代器时，是根据 list 对象 lt，通过调用该类的成员函数 begin（）或者end（）来创建的。那我们自己实现时，在**list中提供这两个成员函数**即可。代码如下：
> 
>     template<class T>
>     	struct list_node
>     	{
>     		list_node<T>* _next;
>     		list_node<T>* _prev;
>     		T _val;
>     
>     		list_node(const T& val = T())
>     			:_next(nullptr)
>     			, _prev(nullptr)
>     			, _val(val)
>     		{}
>     	};
>     
>     	template<class T>
>     	struct __list_iterator
>     	{
>     		typedef list_node<T> Node;
>     		Node* _node;
>     
>     		__list_iterator(Node* node)
>     			:_node(node)
>     		{}
>     
>     		T& operator*()
>     		{
>     			return _node->_val;
>     		}
>     
>     		__list_iterator<T>& operator++()
>     		{
>     			_node = _node->_next;
>     			return *this;
>     		}
>     
>     		__list_iterator<T> operator++(int)
>     		{
>     			__list_iterator<T> tmp(*this);
>     
>     			_node = _node->_next;
>     
>     			return tmp;
>     		}
>     
>     		bool operator!=(const __list_iterator<T>& it)
>     		{
>     			return _node != it._node;
>     		}
>     
>     		bool operator==(const __list_iterator<T>& it)
>     		{
>     			return _node == it._node;
>     		}
>     	};
>     
>     
>     	template<class T>
>     	class list
>     	{
>     		typedef list_node<T> Node;
>     
>     	public:
>     		typedef __list_iterator<T> iterator;
>     
>     
>     		iterator begin()
>     		{
>                 //单参数的构造函数支持隐式类型转换
>                 //  Node* 会进行隐式类型转换，中间会生成一个匿名对象作为临时变量
>     			//return _head->_next;
>              
>     			return iterator(_head->_next);
>     		}
>     
>     		iterator end()
>     		{
>     			return _head;
>     			//return iterator(_head);
>     		}
>     
>     		list()
>     		{
>     			_head = new Node;
>     			_head->_prev = _head;
>     			_head->_next = _head;
>     		}
>     
>     
>     		void push_back(const T& x)
>     		{
>     			Node* tail = _head->_prev;
>     			Node* newnode = new Node(x);
>     
>     			tail->_next = newnode;
>     			newnode->_prev = tail;
>     
>     			newnode->_next = _head;
>     			_head->_prev = newnode;
>     		}
>     
>     	private:
>     		Node* _head;
>     	};

#### 2、2、2 const 迭代器 ####

> 我们实现的普通的迭代器，那const 修饰的迭代器，不就是在普通的迭代器上加上一个指针就可以了。代码如下：
> 
>     // const 迭代器
>     const __list_iterator<T> 
>     typedef const __list_iterator<T> const_iterator;
> 
> 注意：上述的 const 修饰的是这个类型，这个类型是自定义类型，并不是我们之前学的指针。我们也可结合如下代码理解：
> 
>     //const __list_iterator<T> 
>     //typedef const __list_iterator<T> const_iterator;
>     
>     	const list<int> numbers;
>     
>     	// 添加元素到列表末尾
>     	numbers.push_back(1);
>     	numbers.push_back(2);
>     	numbers.push_back(3);
>     	numbers.push_back(4);
>     	numbers.push_back(5);
>     
>         list<int>::const_iterator cit=numbers.begin();
>         // const int a = 10;
> 
> 上述的 const 是修饰的迭代器本身，并不是迭代器指向的内容。这样修饰只是迭代器本身不能修改。而我们想要是**迭代器指向的内容不能被修改**。也就是**解引用返回的值不能被修改**。当然，我们可以再封装一个const迭代器类，代码如下：
> 
>     template<class T>
>     	struct __list_const_iterator
>     	{
>     		typedef list_node<T> Node;
>     		Node* _node;
>     
>     		__list_const_iterator(Node* node)
>     			:_node(node)
>     		{}
>     
>     		const T& operator*()
>     		{
>     			return _node->_val;
>     		}
>     
>     		__list_const_iterator<T>& operator++()
>     		{
>     			_node = _node->_next;
>     			return *this;
>     		}
>     
>     		__list_const_iterator<T> operator++(int)
>     		{
>     			__list_const_iterator<T> tmp(*this);
>     
>     			_node = _node->_next;
>     
>     			return tmp;
>     		}
>     
>     		bool operator!=(const __list_const_iterator<T>& it)
>     		{
>     			return _node != it._node;
>     		}
>     
>     		bool operator==(const __list_const_iterator<T>& it)
>     		{
>     			return _node == it._node;
>     		}
>     	};
> 
> 这样我们发现会不会设计的代码优点冗余了。C++ STL中，list底层实现也并非如此，而是通过增加**模板参数选择复用代码**。如下图：
> 
> ![608bf97bdda24cf185f1c7d9b55e2b8f.png][]
> 
> 我们可以通过增加模板参数（第三个模板参数我们后面也会讲到），来控制解引用返回的是否是用const修饰的引用。代码如下：
> 
>     template<class T, class Ref, class Ptr>
>     	struct __list_iterator
>     	{
>     		typedef list_node<T> Node;
>     		typedef __list_iterator<T, Ref, Ptr> iterator;
>     
>     		Node* _node;
>     
>     		__list_iterator(Node* node)
>     			:_node(node)
>     		{}
>     
>     		bool operator!=(const iterator& it) const
>     		{
>     			return _node != it._node;
>     		}
>     
>     		bool operator==(const iterator& it) const
>     		{
>     			return _node == it._node;
>     		}
>     
>     		// *it  it.operator*()
>     		// const T& operator*()
>     		// T& operator*()
>     		Ref operator*()
>     		{
>     			return _node->_data;
>     		}
>     
>     
>     		// ++it
>     		iterator& operator++()
>     		{
>     			_node = _node->_next;
>     			return *this;
>     		}
>     		
>     		// it++
>     		iterator operator++(int)
>     		{
>     			iterator tmp(*this);
>     			_node = _node->_next;
>     			return tmp;
>     		}
>     
>     	};
>         template<class T>
>     	class list
>     	{
>     		typedef list_node<T> Node;
>     	public:
>     		typedef __list_iterator<T, T&, T*> iterator;
>     		typedef __list_iterator<T, const T&, const T*> const_iterator;
>     
>     		const_iterator begin() const
>     		{
>     			return const_iterator(_head->_next);
>     		}
>     
>     		const_iterator end() const
>     		{
>     			return const_iterator(_head);
>     		}
>     
>     		iterator begin()
>     		{
>     			return iterator(_head->_next);
>     		}
>     
>     		iterator end()
>     		{
>     			return iterator(_head);
>     		}
>     
>     		list()
>     		{
>     			_head = new Node;
>     			_head->_next = _head;
>     			_head->_prev = _head;
>     		}
>     
>     		void push_back(const T& x)
>     		{
>     			//Node* tail = _head->_prev;
>     			//Node* newnode = new Node(x);
>     
>     			 _head          tail  newnode
>     			//tail->_next = newnode;
>     			//newnode->_prev = tail;
>     			//newnode->_next = _head;
>     			//_head->_prev = newnode;
>     
>     			insert(end(), x);
>     		}
>     
>     	private:
>     		Node* _head;
>     	};
> 
> 我们在 list 类中添加 const 迭代器的返回即可。**当我们定义const对象时，会自动调用const修饰的迭代器。当调用const修饰的迭代器时，\_\_list\_iterator的模板参数就会实例化为const T&。**实际上在实例化时，const和非const修饰的还是两个不同类，只不过是实例化的代码工作交给了编译器处理了。

> 以上就是迭代器的底层实现。list底层中，关键重点就是迭代器的实现。其他部分相对来说简单。接下来我们完善剩余的底层实现部分。

### 2、3 完善其他底层实现 ###

> 我们上述代码中有尾插，再把常用接口和拷贝构造、赋值重载实现即可。代码如下：
> 
>     void push_front(const T& x)
>     		{
>     			insert(begin(), x);
>     		}
>     
>     		iterator insert(iterator pos, const T& x)
>     		{
>     			Node* cur = pos._node;
>     			Node* prev = cur->_prev;
>     
>     			Node* newnode = new Node(x);
>     
>     			// prev newnode cur
>     			prev->_next = newnode;
>     			newnode->_prev = prev;
>     			newnode->_next = cur;
>     			cur->_prev = newnode;
>     
>     			return iterator(newnode);
>     		}
>     
>     		iterator erase(iterator pos)
>     		{
>     			assert(pos != end());
>     
>     			Node* cur = pos._node;
>     			Node* prev = cur->_prev;
>     			Node* next = cur->_next;
>     
>     			prev->_next = next;
>     			next->_prev = prev;
>     			delete cur;
>     
>     			return iterator(next);
>     		}
>     
>     		void pop_back()
>     		{
>     			erase(--end());
>     		}
>     
>     		void pop_front()
>     		{
>     			erase(begin());
>     		}
>     
>             void empty_init()
>     		{
>     			// 创建并初始化哨兵位头结点
>     			_head = new Node;
>     			_head->_next = _head;
>     			_head->_prev = _head;
>     		}
>     
>     		template <class InputIterator>  
>     		list(InputIterator first, InputIterator last)
>     		{
>     			empty_init();
>     
>     			while (first != last)
>     			{
>     				push_back(*first);
>     				++first;
>     			}
>     		}
>     
>     		list()
>     		{
>     			empty_init();
>     		}
>     
>     		void swap(list<T>& x)
>     		//void swap(list& x)
>     		{
>     			std::swap(_head, x._head);
>     		}
>     
>     		// lt2(lt1)
>     		list(const list<T>& lt)
>     		{
>     			empty_init();
>     			list<T> tmp(lt.begin(), lt.end());
>     			swap(tmp);
>     		}
>     
>     		// lt1 = lt3
>     		list<T>& operator=(list<T> lt)
>     		{
>     			swap(lt);
>     			return *this;
>     		}
>     
>     		~list()
>     		{
>     			clear();
>     			delete _head;
>     			_head = nullptr;
>     		}
>     
>     		void clear()
>     		{
>     			iterator it = begin();
>     			while (it != end())
>     			{
>     				it = erase(it);
>     			}
>     		}
> 
> 上述代码，把初始化的代码再次封装了一个函数。list初始化构造也可用一段区间来初始化，这个区间可以是vector迭代器区间，或者数组的指针区间等等。其他实现均较为简单。

## 三、总结 ##

> 我们之前是由顺序表和链表的对比，现在我们再对比一下vector和list的优缺点。如下：
> 
> <table style="width:500px;"> 
>  <tbody> 
>   <tr> 
>    <td style="width:41px;"></td> 
>    <td style="width:287px;"><span style="color:#333333;"><strong>vector</strong></span></td> 
>    <td style="width:171px;"><span style="color:#333333;"><strong>list</strong></span></td> 
>   </tr> 
>   <tr> 
>    <td style="width:41px;"> 
>     <div> 
>      <span style="color:#333333;"><strong>底 </strong></span> 
>     </div> 
>     <div> 
>      <span style="color:#333333;"><strong>层 </strong></span> 
>     </div> 
>     <div> 
>      <span style="color:#333333;"><strong>结 </strong></span> 
>     </div> 
>     <div> 
>      <span style="color:#333333;"><strong>构</strong></span> 
>     </div> </td> 
>    <td style="width:287px;"> 
>     <div> 
>      <span style="color:#333333;"><strong>动态顺序表，一段连续空间 </strong></span> 
>     </div> </td> 
>    <td style="width:171px;"> 
>     <div> 
>      <span style="color:#333333;"><strong>带头结点的双向循环链表</strong></span> 
>     </div> </td> 
>   </tr> 
>   <tr> 
>    <td style="width:41px;"> 
>     <div> 
>      <span style="color:#333333;"><strong>随 </strong></span> 
>     </div> 
>     <div> 
>      <span style="color:#333333;"><strong>机 </strong></span> 
>     </div> 
>     <div> 
>      <span style="color:#333333;"><strong>访 </strong></span> 
>     </div> 
>     <div> 
>      <span style="color:#333333;"><strong>问 </strong></span> 
>     </div> </td> 
>    <td style="width:287px;"> 
>     <div> 
>      <span style="color:#333333;"><strong>支持随机访问，访问某个元素效率O(1)</strong></span> 
>     </div> </td> 
>    <td style="width:171px;"> 
>     <div> 
>      <span style="color:#333333;"><strong>不支持随机访问，访问某个元素效率O(N)</strong></span> 
>     </div> </td> 
>   </tr> 
>   <tr> 
>    <td style="width:41px;"> 
>     <div> 
>      <span style="color:#333333;"><strong>插 </strong></span> 
>     </div> 
>     <div> 
>      <span style="color:#333333;"><strong>入 </strong></span> 
>     </div> 
>     <div> 
>      <span style="color:#333333;"><strong>和 </strong></span> 
>     </div> 
>     <div> 
>      <span style="color:#333333;"><strong>删 </strong></span> 
>     </div> 
>     <div> 
>      <span style="color:#333333;"><strong>除</strong></span> 
>     </div> </td> 
>    <td style="width:287px;"> 
>     <div> 
>      <span style="color:#333333;"><strong>任意位置插入和删除效率低，需要搬移元素，时间复杂度为O(N)，插入时有可能需要增容，增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低 </strong></span> 
>     </div> </td> 
>    <td style="width:171px;"> 
>     <div> 
>      <span style="color:#333333;"><strong>任意位置插入和删除效率高，不需要搬移元素，时间复杂度为 </strong></span> 
>     </div> 
>     <div> 
>      <span style="color:#333333;"><strong>O(1）</strong></span> 
>     </div> </td> 
>   </tr> 
>   <tr> 
>    <td style="width:41px;"> 
>     <div> 
>      <span style="color:#333333;"><strong>空 </strong></span> 
>     </div> 
>     <div> 
>      <span style="color:#333333;"><strong>间 </strong></span> 
>     </div> 
>     <div> 
>      <span style="color:#333333;"><strong>利 </strong></span> 
>     </div> 
>     <div> 
>      <span style="color:#333333;"><strong>用 </strong></span> 
>     </div> 
>     <div> 
>      <span style="color:#333333;"><strong>率 </strong></span> 
>     </div> </td> 
>    <td style="width:287px;"> 
>     <div> 
>      <span style="color:#333333;"><strong>底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高</strong></span> 
>     </div> </td> 
>    <td style="width:171px;"> 
>     <div> 
>      <span style="color:#333333;"><strong>底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低</strong></span> 
>     </div> </td> 
>   </tr> 
>   <tr> 
>    <td style="width:41px;"> 
>     <div> 
>      <span style="color:#333333;"><strong>迭 </strong></span> 
>     </div> 
>     <div> 
>      <span style="color:#333333;"><strong>代 </strong></span> 
>     </div> 
>     <div> 
>      <span style="color:#333333;"><strong>器 </strong></span> 
>     </div> </td> 
>    <td style="width:287px;"> 
>     <div> 
>      <span style="color:#333333;"><strong>原生态指针</strong></span> 
>     </div> </td> 
>    <td style="width:171px;"> 
>     <div> 
>      <span style="color:#333333;"><strong>对原生态指针(节点指针)进行封装</strong></span> 
>     </div> </td> 
>   </tr> 
>   <tr> 
>    <td style="width:41px;"> 
>     <div> 
>      <span style="color:#333333;"><strong>迭 </strong></span> 
>     </div> 
>     <div> 
>      <span style="color:#333333;"><strong>代 </strong></span> 
>     </div> 
>     <div> 
>      <span style="color:#333333;"><strong>器 </strong></span> 
>     </div> 
>     <div> 
>      <span style="color:#333333;"><strong>失 </strong></span> 
>     </div> 
>     <div> 
>      <span style="color:#333333;"><strong>效 </strong></span> 
>     </div> </td> 
>    <td style="width:287px;"> 
>     <div> 
>      <span style="color:#333333;"><strong>在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效 </strong></span> 
>     </div> </td> 
>    <td style="width:171px;"> 
>     <div> 
>      <span style="color:#333333;"><strong>插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响</strong></span> 
>     </div> </td> 
>   </tr> 
>   <tr> 
>    <td style="width:41px;"> 
>     <div> 
>      <span style="color:#333333;"><strong>使 </strong></span> 
>     </div> 
>     <div> 
>      <span style="color:#333333;"><strong>用 </strong></span> 
>     </div> 
>     <div> 
>      <span style="color:#333333;"><strong>场 </strong></span> 
>     </div> 
>     <div> 
>      <span style="color:#333333;"><strong>景 </strong></span> 
>     </div> </td> 
>    <td style="width:287px;"> 
>     <div> 
>      <span style="color:#333333;"><strong>需要高效存储，支持随机访问，不关心插入删除效率</strong></span> 
>     </div> </td> 
>    <td style="width:171px;"> 
>     <div> 
>      <span style="color:#333333;"><strong>大量插入和删除操作，不关心随机访问</strong></span> 
>     </div> </td> 
>   </tr> 
>  </tbody> 
> </table>

> list底层实现关键是迭代器的实现。我们要清楚的是， **list的迭代器底层就是一个对节点进行封装的类**。初学可能会感觉有点难以理解。但是，应多看几遍理解整体结构就很容易清楚了。本篇文章的讲解就到这里，感谢观看ovo~

[a518bd4c19214f9bb3c98fd6f6ef8796.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/0a7f6346f0e04ea6a9ded8358b21d2ba.gif
[27194d7384804799a5a468422891bff4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/253d028e0696424e92c0042494b41a08.png
[3e2108a410aa418daf05b89937b31803.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/96ebbaacb4374074850f008cc9d286b6.png
[151a7d74187842d2897e767aa1c56672.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/b1104677152b443a9f80a49d2348350b.png
[608bf97bdda24cf185f1c7d9b55e2b8f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/78bd2b9141a44cdd914b32e3c2a40bd9.png