STL02——手写简单版本的list

手写一个简单版本的list

设计一个名为 List 的 List 类，该类具有以下功能和特性：

1、基础成员函数

• 构造函数：初始化 List 实例
• 析构函数：清理资源，确保无内存泄露

2、核心功能

• 在 List 末尾添加元素
• 在 List 开头添加元素
• 获取 List 中节点的数量
• 删除 List 末尾的元素
• 删除 List 开头的元素
• 删除 List 中指定值的节点

3、迭代与遍历

• 打印链表中的元素

4、辅助功能

• 重载[]运算符以对链表进行索引访问
• 重载<<运算符以打印链表

输入描述

题目的包含多行输入，第一行为正整数 N, 代表后续有 N 行命令序列。

接下来 N 行，每行包含一个命令，命令格式为 [operation] [parameters] ，具体命令如下：

push_back 命令：

• 格式：push_back [value]
• 功能：在链表末尾添加值为 value 的元素

push_front 命令：

• 格式：push_front [value]
• 功能：在链表开头添加值为 value 的元素

pop_back 命令：

• 格式：pop_back
• 功能：删除链表末尾的元素

pop_front 命令：

• 格式：pop_front
• 功能：删除链表开头的元素

remove 命令：

• 格式：remove [value]
• 功能：删除链表中值为 value 的元素

clear 命令：

• 格式：clear
• 功能：清空链表

size 命令：

• 格式：size
• 功能：获取链表中节点的数量

get 命令：

• 格式：get [index]
• 功能：获取链表中索引为 index 的节点的值

print 命令：

• 格式：print
• 功能：打印链表中的元素

输出描述

输出为每行命令执行后的结果，具体输出格式如下：

**push_back 命令：**无输出

**push_front 命令：**无输出

**pop_back 命令：**无输出

**pop_front 命令：**无输出

**remove 命令：**无输出

**clear 命令：**无输出

**size 命令：**输出一个整数，独占一行，代表当前 List 中元素的数量

**get 命令：**输出一个整数，独占一行，代表 List 中索引为 index 的元素，如果索引无效，则输出 -1

**print 命令：**按照顺序打印当前 List 包含的所有元素，每个元素后都跟一个空格，打印结果独占一行；如果当前的 vector 为空，则打印 empty

#include <iostream>
#include <stdexcept>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
using namespace std;
template <typename T>
class List
{
public:template<typename L>friend ostream& operator<<(ostream& os, const List<L>& pt);
private://定义链表结点struct Node{T data;Node* next;Node* prev;//含参的默认构造函数Node(const T&value, Node* nextNode = nullptr,Node* prevNode = nullptr){data = value;next = nextNode;prev = prevNode;}};//头尾结点指针Node* head;Node* tail;//结点数量size_t size;public:List(){head = NULL;tail = NULL;size = 0;}~List(){clear();//把链表空间释放}//前插void push_front(const T& value){//创造新节点，next指向的是headNode* newNode = new Node(value, head, NULL);if (head != NULL)//如果链表非空{head->prev = newNode;}else{//如果链表是空的，则首尾都要指向这个独苗tail = newNode;}head = newNode;//头结点前移size++;}//尾插void push_back(const T& value){Node* newNode = new Node(value, NULL, tail);if (tail != NULL)tail->next = newNode;elsehead = newNode;tail = newNode;//尾结点后移size++;//链表长度加1}size_t getSize() const{return size;}//访问:循环index次，然后返回当前结点的值即可T& operator[](size_t index){Node* cur = head;//head相当于是下标为0的元素while (index--){if (cur == NULL)throw out_of_range("index out of range");cur = cur->next;}return cur->data;}const T& operator[](size_t index) const{Node* cur = head;//head相当于是下标为0的元素while (index--){if (cur == NULL)throw out_of_range("index out of range");cur = cur->next;}return cur->data;}//删除链表末尾元素：// 首先直接获取尾结点的前一个结点，// 然后尾结点prev指向null,然后尾结点前移，// 最后将新尾结点的next指向null，size--//void pop_back()//{//	if (tail == NULL)//		cout << "empty" << endl;//	else//	{//		Node* tailPre = tail->prev;//tailPre可能为空//		tail->prev = NULL;//		tail = tailPre;//		if (tail)//			tail->next = NULL;//		else//			head = NULL;//		size--;//	}	//}//标准(此方法更好，释放了tail的内存，没有造成内存遗失)void pop_back(){if (size > 0){Node* newTail = tail->prev;//直接把尾结点删了，简单粗暴。//结点delete之后，它的prev和next指针都自动消失了delete tail;//虽然空间没了，但是Node*tail这个指针本身还在健在的tail=newTail;if (tail)tail->next = NULL;elsehead = NULL;size--;}}void pop_front(){if (size > 0){Node* newHead = head->next;delete head;head = newHead;if (head)head->prev = NULL;elsetail = NULL;size--;}}Node* getNode(const T& val){//遍历,用whileNode* node = head;while (node!=NULL){if (node->val == val)return node;node = node->next;}return NULL;}//删除结点void remove(const T& val){Node* node = head;while (node != NULL){if (node->data == val){if (node == head && node == tail){node = NULL;}else if (node == head){head = head->next;head->prev = NULL;}else if (node == tail){tail = tail->prev;tail->next = NULL;}else{node->prev->next = node->next;node->next->prev = node->prev;}size--;}node = node->next;}}bool empty(){return size == 0;}void clear(){//每次都设置一个指针指向要被删除的元素while (head!=NULL){Node* node = head;//从头开始head = head->next;//头不断后移delete node;}tail = NULL;size = 0;}Node* begin(){return head;}Node* end(){return NULL;}void printElements() const{Node* node = head;while (node != NULL){cout << node->data << " ";node = node->next;}cout << endl;}};//重载<<运算符
template<typename T>
ostream& operator<<(ostream& os, const List<T>& pt)
{for (typename List<T>::Node* cur = pt.head; cur != NULL; cur = cur->next){os << cur->data << " ";}os << endl;return os;
}int main() {// 创建一个 List 对象List<int> myList;int N;std::cin >> N;// 读走回车getchar();std::string line;// 接收命令for (int i = 0; i < N; i++) {std::getline(std::cin, line);std::istringstream iss(line);std::string command;iss >> command;int value;if (command == "push_back") {iss >> value;myList.push_back(value);}if (command == "push_front") {iss >> value;myList.push_front(value);}if (command == "pop_back") {myList.pop_back();}if (command == "pop_front") {myList.pop_front();}if (command == "remove") {iss >> value;myList.remove(value);}if (command == "clear") {myList.clear();}if (command == "size") {std::cout << myList.getSize() << std::endl;}if (command == "get") {iss >> value;std::cout << myList[value] << std::endl;}if (command == "print") {if (myList.getSize() == 0) {std::cout << "empty" << std::endl;}else {myList.printElements();}}}return 0;
}