[数据结构与算法]简单模拟list容器

本人小白一枚，在这里和大家分享一些编程日常，希望大佬们多多支持！！！??????

容器

容器（Containers）：用来管理某类对象的集合。各种数据结构，如vector、list、deque、set、map等,用来存放数据，从实现角度来看，STL容器是一种class template。

迭代器

迭代器（Iterators）：用来在一个对象集合的元素上进行遍历动作。扮演了容器与算法之间的胶合剂，共有五种类型，从实现角度来看，迭代器是一种将operator* , operator-> , operator++, operator–等指针相关操作予以重载的class template。所有STL容器都附带有自己专属的迭代器，只有容器的设计者才知道如何遍历自己的元素。原生指针(native pointer)也是一种迭代器。

List

List 由双向链表（doubly linked list）实现而成，元素也存放在堆中，每个元素都是放在一块内存中，它的内存空间可以是不连续的，通过指针来进行数据的访问，这个特点使得它的随机存取变得非常没有效率，因此它没有提供 [] 操作符的重载。
但是由于链表的特点，它可以很有效率的支持任意地方的插入和删除操作。
访问开始和最后两个元素最快，其他元素的访问时间一样。

优缺点和适用场景
优点：内存不连续，动态操作，可在任意位置插入或删除且效率高。
缺点：不支持随机访问。
适用场景：适用于经常进行插入和删除操作并且不经常随机访问的场景。

源代码：

#include<iostream>
using namespace std;
template <class T>
struct Node {
public:
	Node(T data):data(data){}//构造
	Node(T data,Node<T>* next):data(data),next(next){}//构造
	T& getdata() {//获取data
		return data;
	}
	Node<T>* &getnext() {//获取next
		return next;
	}
protected:
	T data;//数据域
	Node<T>* next;//指针域
};
template <class T>
class List {
public:
	List() {//构造
		headNode =tailNode = nullptr;
		cursize = 0;
	}
	~List() {//析构
		Node<T>* pmove = headNode;
		while (!empty()) {
			delete pmove;
		}
	}
	void push_front(T data) {//头插法
			headNode = new Node<T>(data, headNode);
			cursize++;
	}
	void push_back(T data) {//尾插法
		Node<T>* newNode = new Node<T>(data);
		tailNode->getnext() = newNode;
		tailNode = newNode;
		cursize++;
	}
	void pop_front() {//头删除
		Node<T>* tempNode = headNode->getnext();
		delete headNode;
		headNode = tempNode;
		cursize--;
	}
	void pop_back() {//尾删除
		Node<T>* leftNode = headNode;
		Node<T>* rightNode = headNode;
		while (leftNode->getnext()) {
			leftNode = rightNode;
			rightNode = rightNode->getnext();
		}
		delete tailNode;
		tailNode = leftNode;
		tailNode->getnext() = nullptr;
		cursize--;
	}
	int size() {//获取结点数量
		return cursize;
	}
protected:
	Node<T>* headNode;//头节点
	Node<T>* tailNode;//尾结点
	int cursize;//结点数目
public:
	class iterator {//内置迭代器
	public:
		iterator() {//构造
			pmove = nullptr;
		}
		iterator(Node<T>* move):pmove(move){}//构造
		iterator operator=(Node<T>* move) {
			pmove = move;
			return iterator(pmove);
		}
		bool operator!=(Node<T>* move) {//重载！=
			return pmove != move;
		}
		void operator++(int) {//重载++
			pmove = pmove->getnext();
		}
		T operator*() {//重载*
			return pmove->getdata();
		}
	protected:
		Node<T>* pmove;//移动指针
	};
	Node<T>* begin() {//获取头节点
		return headNode;
	}
	Node<T>* end() {//获取尾节点
		return tailNode;
	}
	bool empty() {//判断是否有结点
		return cursize == 0;
	}
};

测试代码：

void test() {
	const int arraySize = 4;
	string Man[arraySize] = { "何美人1号","何美人2号" ,"何美人3号","何美人4号" };
	List<string> list;
	for (int i = 0; i < arraySize; i++) {
		list.push_front(Man[i]);
	}
	List<string>::iterator iter;
	for (iter = list.begin(); iter != list.end(); iter++)
		cout << *iter << endl;
	cout << "......................"<<endl;
	list.pop_front();
	for (iter = list.begin(); iter != list.end(); iter++)
		cout << *iter << endl;
	cout << "......................"<<endl;
	list.pop_back();
	for (iter = list.begin(); iter != list.end(); iter++)
		cout << *iter << endl;
	return 0;
}

运行效果：