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指向的是head
		Node* 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;
		else
			head = 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;
			else
				head = NULL;
			size--;
		}
	}

	void pop_front()
	{
		if (size > 0)
		{
			Node* newHead = head->next;
			delete head;
			head = newHead;
			if (head)
				head->prev = NULL;
			else
				tail = NULL;
			size--;
		}
	}
	
	Node* getNode(const T& val)
	{
		//遍历,用while
		Node* 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;
}