list
list是一种基于双向链表的数据结构，适用于需要在序列中执行频繁插入和删除操作的场景
特性
- 本质上是一个双向链表，允许在序列的两端和中间执行插入和删除操作
- 只能通过迭代器访问元素，即访问元素的时间复杂度为\(O(n)\)
- 动态内存管理，内部通过类似指针的节点实现元素存储，一个节点存储了当前元素和前后节点的指针
- 迭代器在增加和删除之后仍然有效
基础成员变量
头指针，尾指针以及List大小三个变量
对于list内部每个元素即一个节点，其具有当前元素值，前指针(第一个元素指向最后一个元素)，后指针(最后一个元素指向第一个元素)
//整个成员变量
//节点结构体
struct Node
{
T data;
Node* prev;
Node* next;
Node(const T& value,Node* prevnode = nullptr,Node* nextnode = nullptr):data(value),prev(prevdata),next(nextdata){}
};
Node* head;
Node* tail;
size_t size;
相关操作的实现
<<运算符重载
template <typename T>
friend std::ostream& operator<<(std::ostream& os,const List<T>& pt)
{
for(typename List<T>::Node *cur = pt.head,cur;cur = cur->next)
{
os << " " << cur->data;
}
os << std::endl
return os;
}
压入头部和尾部
需要考虑原始list为空的情况
//在末尾添加元素，变换tail节点
void push_back(const T& value)
{
//创建新的节点
Node* newnode = new Node(value,nullptr,tail);
//如果tail指针指向的不为空
if(tail)
{
tail->next = newnode;
}
//如果tail为空，说明链表为空
else
{
head = newnode;
}
tail = newnode;
size++;
}
//在头部添加元素,变换head节点
void push_front(const T& value)
{
Node* newnode = new Node(value,head,nullptr);
if(head)
{
head->prev = newnode;
}
else
{
tail = newnode;
}
head = newnode;
size++;
}
从头部和尾部弹出元素
只需要考虑size >0 的情况，利用delete删除节点
void pop_back()
{
if(size > 0)
{
Node* temp = tail->prev;
delete tail;
tail = temp;
if(tail)
{
tail->next = nullptr;
}
else
{
head = nullptr;
}
size--;
}
}
//删除头部元素，改变head节点
void pop_front()
{
if(size > 0)
{
Node* temp = head->next;
delete head;
head = temp;
if(head)
{
head->prev = nullptr;
}
else
{
tail = nullptr;
}
size--;
}
}
根据值删除节点
需要考虑当前list为空，或者当前节点为头节点尾节点的情况
void remove(const T& value)
{
Node* node = getNode(value);
if(!node) return ;
else if(node!=head && node != tail)
{
Node* prevnode = node->prev;
Node* nextnode = node->next;
prevnode->next = nextnode;
nextnode->prev = prevnode;
}
else if(node == head && node == tail)
{
head = nullptr;
tail = nullptr;
}
else if(node == head)
{
head = node->next;
head->prev = nullptr;
}
else
{
tail = node->prev;
tail->next = nullptr;
}
size--;
}
总结
删除list中的特定元素
list中元素不是连续存储的，而且插入和删除不会导致迭代器失效
通过遍历，利用erase实现
template <typename T>
void removeins(std::list<T>& lst, const T& value)
{
for(auto it = lst.begin();it!=lst.end();)
{
if(*it == value)
{
it = lst.erase(it);
}
else
{
it++;
}
}
}
list迭代器失效的情况
在插入操作时不会导致任何迭代器失效，而删除操作会导致指向被删除元素的迭代器失效，而其他迭代器不会失效
与vector的关系
内部实现
- list是双向链表，不支持随机访问
- vector是一个动态数组，支持随机访问
性能特点
- list 常数时间内进行插入和删除操作，但访问为\(O(n)\)，每个元素存放在单独的内存块中，用指针连接，不需要重新分配整个容器的内存空间
- vector 常数时间内进行访问，但插入和删除为\(O(n)\)，在内存中连续，超出容量，需要进行扩容操作
内存开销
- list 每个元素都多存储了指向前面和后面的节点指针
- vector 较小的内存开销