当前位置：首页 > java >正文

模拟实现STL中的list容器

java 2025/9/2 14:02:10

list

前言
- 一、list的节点结构设计
- 二、迭代器设计
- 三、list类的实现
- - 3.1 类的成员变量和类型定义
  - 3.2 构造函数与析构函数
  - 3.3 元素访问与迭代器接口
  - 3.4 插入与删除操作
  - 3.5 其他常用操作
- 四、总结
每文推荐

前言

在C++ STL中，list是一个非常常用的容器，它基于双向循环链表实现，具有高效的插入和删除操作。本文将详细介绍如何模拟实现一个简易版的STL list容器，包括节点结构、迭代器设计以及list类的核心功能实现。

一、list的节点结构设计

list的底层是双向循环链表，因此首先需要设计链表的节点结构。每个节点应包含数据域和两个指针域（前驱和后继）：

template<class T>
struct ListNode
{typedef ListNode<T> Node;ListNode(const T& val = T());~ListNode();Node* _next;  // 指向后继节点Node* _prev;  // 指向前驱节点T _val;       // 节点存储的数据
};template<class T>
ListNode<T>::ListNode(const T& val):_next(nullptr), _prev(nullptr), _val(val)
{}template<class T>
ListNode<T>::~ListNode()
{_next = nullptr;_prev = nullptr;_val = T();
}

二、迭代器设计

list的迭代器与vector不同，它不能是简单的指针，因为list的节点在内存中不是连续存储的。我们需要设计一个迭代器类，通过重载运算符来模拟指针的行为。

template<class T, class value_type>
struct ListIterator
{typedef ListNode<T> Node;Node* _node;  // 指向当前节点ListIterator(Node* node = nullptr);// 重载各种运算符ListIterator<T, value_type>& operator=(const ListIterator<T, value_type>& it);ListIterator<T, value_type>& operator++();       // 前置++ListIterator<T, value_type> operator++(int);     // 后置++ListIterator<T, value_type>& operator--();       // 前置--ListIterator<T, value_type> operator--(int);     // 后置--value_type& operator*();                         // 解引用value_type* operator->();                        // 箭头运算符bool operator==(const ListIterator<T, value_type>& it);bool operator!=(const ListIterator<T, value_type>& it);
};

迭代器的核心运算符实现：

// 前置++
template<class T, class value_type>
ListIterator<T, value_type>& ListIterator<T, value_type>::operator++()
{_node = _node->_next;return *this;
}// 后置++
template<class T, class value_type>
ListIterator<T, value_type> ListIterator<T, value_type>::operator++(int)
{ListIterator<T, value_type> tmp = *this;_node = _node->_next;return tmp;
}// 解引用运算符
template<class T, class value_type>
value_type& ListIterator<T, value_type>::operator*()
{return _node->_val;
}// 箭头运算符
template<class T, class value_type>
value_type* ListIterator<T, value_type>::operator->()
{return &(_node->_val);
}

三、list类的实现

list类需要维护一个双向循环链表，我们使用一个头节点（哨兵节点）来简化边界条件的处理。

3.1 类的成员变量和类型定义

template<class T>
class list
{
public:typedef ListNode<T> Node;// 定义迭代器类型，普通迭代器和const迭代器typedef ListIterator<T, T> iterator;typedef ListIterator<T, const T> const_iterator;// ... 成员函数声明
private:Node* _head;  // 头节点（哨兵节点）
};

3.2 构造函数与析构函数

// 默认构造函数
template<class T>
list<T>::list()
{_head = new Node;_head->_next = _head;  // 循环指向自身_head->_prev = _head;
}// 范围构造函数
template<class T>
template <class InputIterator>
list<T>::list(InputIterator first, InputIterator last)
{_head = new Node;_head->_next = _head;_head->_prev = _head;while (first != last){push_back(*first);first++;}
}// 析构函数
template<class T>
list<T>::~list()
{Node* cur = _head->_next;while (cur != _head){Node* next = cur->_next;delete cur;cur = next;}delete _head;_head = nullptr;
}

3.3 元素访问与迭代器接口

// 迭代器接口
template<class T>
typename list<T>::iterator list<T>::begin()
{return iterator(_head->_next);  // 第一个元素是头节点的下一个
}template<class T>
typename list<T>::iterator list<T>::end()
{return iterator(_head);  // 尾后迭代器指向头节点
}// 元素访问
template<class T>
T& list<T>::front()
{assert(!empty());return _head->_next->_val;  // 第一个元素
}template<class T>
T& list<T>::back()
{assert(!empty());return _head->_prev->_val;  // 最后一个元素
}

3.4 插入与删除操作

list的插入和删除操作是其核心优势，时间复杂度为O(1)：

// 头插
template<class T>
void list<T>::push_front(const T& val)
{Node* new_node = new Node(val);// 插入到头节点和第一个元素之间new_node->_prev = _head;new_node->_next = _head->_next;_head->_next->_prev = new_node;_head->_next = new_node;
}// 尾插
template<class T>
void list<T>::push_back(const T& val)
{Node* new_node = new Node(val);// 插入到最后一个元素和头节点之间new_node->_prev = _head->_prev;new_node->_next = _head;_head->_prev->_next = new_node;_head->_prev = new_node;
}// 指定位置插入
template<class T>
typename list<T>::iterator list<T>::insert(iterator position, const T& val)
{Node* new_node = new Node(val);// 插入到position之前new_node->_prev = position._node->_prev;new_node->_next = position._node;position._node->_prev->_next = new_node;position._node->_prev = new_node;return iterator(new_node);  // 返回指向新节点的迭代器
}// 指定位置删除
template<class T>
typename list<T>::iterator list<T>::erase(iterator position)
{// 调整前后节点的指针关系position._node->_prev->_next = position._node->_next;position._node->_next->_prev = position._node->_prev;iterator ret = position._node->_next;  // 记录下一个位置delete position._node;  // 释放节点内存return ret;  // 返回下一个位置的迭代器
}

3.5 其他常用操作

// 清空链表
template<class T>
void list<T>::clear()
{Node* cur = _head->_next;while (cur != _head){Node* next = cur->_next;delete cur;cur = next;}// 恢复头节点的循环指向_head->_prev = _head;_head->_next = _head;
}// 反转链表
template<class T>
void list<T>::reverse()
{Node* cur = _head->_next;while (cur != _head){Node* tmp = cur->_next;std::swap(cur->_prev, cur->_next);  // 交换前后指针cur = tmp;}// 交换头节点的前后指针std::swap(_head->_prev, _head->_next);
}// 移除所有值为val的元素
template<class T>
void list<T>::remove(const T& val)
{iterator cur = begin();while (cur != end()){if (*cur == val){cur = erase(cur);  // 删除后自动移动到下一个元素}else{++cur;}}
}